Factoring larger integers with fewer qubits via quantum annealing with optimized parameters
|
摘要
RSA cryptography is based on the difficulty of factoring large integers, which is an NP-hard(and hence intractable) problem for a classical computer. However, Shor's algorithm shows that its complexity is polynomial for a quantum computer, although technical difficulties mean that practical quantum computers that can tackle integer factorizations of meaningful size are still a long way away. Recently, Jiang et al. proposed a transformation that maps the integer factorization problem onto the quadratic unconstrained binary optimization(QUBO) model. They tested their algorithm on a D-Wave 2000 Q quantum annealing machine, raising the record for a quantum factorized integer to 376289 with only 94 qubits. In this study, we optimize the problem Hamiltonian to reduce the number of qubits involved in the final Hamiltonian while maintaining the QUBO coefficients in a reasonable range, enabling the improved algorithm to factorize larger integers with fewer qubits. Tests of our improved algorithm using D-Wave's hybrid quantum/classical simulator qbsolv confirmed that performance was improved, and we were able to factorize 1005973, a new record for quantum factorized integers, with only 89 qubits. In addition, our improved algorithm can tolerate more errors than the original one. Factoring 1005973 using Shor's algorithm would require about 41 universal qubits,which current universal quantum computers cannot reach with acceptable accuracy. In theory, the latest IBM Q System OneTM(Jan. 2019) can only factor up to 10-bit integers, while the D-Wave have a thousand-fold advantage on the factoring scale. This shows that quantum annealing machines, such as those by D-Wave, may be close to cracking practical RSA codes, while universal quantum-circuit-based computers may be many years away from attacking RSA.
RSA cryptography is based on the difficulty of factoring large integers, which is an NP-hard(and hence intractable) problem for a classical computer. However, Shor's algorithm shows that its complexity is polynomial for a quantum computer, although technical difficulties mean that practical quantum computers that can tackle integer factorizations of meaningful size are still a long way away. Recently, Jiang et al. proposed a transformation that maps the integer factorization problem onto the quadratic unconstrained binary optimization(QUBO) model. They tested their algorithm on a D-Wave 2000 Q quantum annealing machine, raising the record for a quantum factorized integer to 376289 with only 94 qubits. In this study, we optimize the problem Hamiltonian to reduce the number of qubits involved in the final Hamiltonian while maintaining the QUBO coefficients in a reasonable range, enabling the improved algorithm to factorize larger integers with fewer qubits. Tests of our improved algorithm using D-Wave's hybrid quantum/classical simulator qbsolv confirmed that performance was improved, and we were able to factorize 1005973, a new record for quantum factorized integers, with only 89 qubits. In addition, our improved algorithm can tolerate more errors than the original one. Factoring 1005973 using Shor's algorithm would require about 41 universal qubits,which current universal quantum computers cannot reach with acceptable accuracy. In theory, the latest IBM Q System OneTM(Jan. 2019) can only factor up to 10-bit integers, while the D-Wave have a thousand-fold advantage on the factoring scale. This shows that quantum annealing machines, such as those by D-Wave, may be close to cracking practical RSA codes, while universal quantum-circuit-based computers may be many years away from attacking RSA.
RSA cryptography is based on the difficulty of factoring large integers, which is an NP-hard(and hence intractable) problem for a classical computer. However, Shor's algorithm shows that its complexity is polynomial for a quantum computer, although technical difficulties mean that practical quantum computers that can tackle integer factorizations of meaningful size are still a long way away. Recently, Jiang et al. proposed a transformation that maps the integer factorization problem onto the quadratic unconstrained binary optimization(QUBO) model. They tested their algorithm on a D-Wave 2000 Q quantum annealing machine, raising the record for a quantum factorized integer to 376289 with only 94 qubits. In this study, we optimize the problem Hamiltonian to reduce the number of qubits involved in the final Hamiltonian while maintaining the QUBO coefficients in a reasonable range, enabling the improved algorithm to factorize larger integers with fewer qubits. Tests of our improved algorithm using D-Wave's hybrid quantum/classical simulator qbsolv confirmed that performance was improved, and we were able to factorize 1005973, a new record for quantum factorized integers, with only 89 qubits. In addition, our improved algorithm can tolerate more errors than the original one. Factoring 1005973 using Shor's algorithm would require about 41 universal qubits,which current universal quantum computers cannot reach with acceptable accuracy. In theory, the latest IBM Q System OneTM(Jan. 2019) can only factor up to 10-bit integers, while the D-Wave have a thousand-fold advantage on the factoring scale. This shows that quantum annealing machines, such as those by D-Wave, may be close to cracking practical RSA codes, while universal quantum-circuit-based computers may be many years away from attacking RSA.
引文
1 S.S.Wagstaff,Am.Math.Soc.68,293(2013).
2 A.K.Lenstra,H.W.Lenstra Jr,M.S.Manasse,and J.M.Pollard,in Theory of Computing 1990:Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing,edited by H.Ortiz(ACM,New York,1990),pp.564-572.
3 M.A.Nielsen,I.Chuang,and L.K.Grover,Am.J.Phys.70,558(2002).
4 S.J.Wei,T.Xin,and G.L.Long,Sci.China-Phys.Mech.Astron.61,070311(2018),arXiv:1706.08080.
5 H.L.Huang,Y.W.Zhao,T.Li,F.G.Li,Y.T.Du,X.Q.Fu,S.Zhang,X.Wang,and W.S.Bao,Front.Phys.12,120305(2017),arXiv:1612.02886.
6 T.Xin,S.Huang,S.Lu,K.Li,Z.Luo,Z.Yin,J.Li,D.Lu,G.Long,and B.Zeng,Sci.Bull.63,17(2018).
7 J.Zhou,B.J.Liu,Z.P.Hong,and Z.Y.Xue,Sci.China-Phys.Mech.Astron.61,010312(2018),arXiv:1705.08852.
8 P.W.Shor,SIAM Rev.41,303(1999).
9 L.M.K.Vandersypen,M.Steffen,G.Breyta,C.S.Yannoni,M.H.Sherwood,and I.L.Chuang,Nature 414,883(2001).
10 E.Martín-López,A.Laing,T.Lawson,R.Alvarez,X.Q.Zhou,and J.L.O’Brien,Nat.Photon 6,773(2012),arXiv:1111.4147.
11 J.A.Smolin,G.Smith,and A.Vargo,Nature 499,163(2013),arXiv:1301.7007.
12 M.R.Geller,and Z.Zhou,Sci.Rep.3,3023(2013),arXiv:1304.0128.
13 C.Gidney,.arXiv:1706.07884v2
14 A.Cho,Science 359,141(2018).
15 E.Farhi,J.Goldstone,S.Gutmann,J.Lapan,A.Lundgren,and D.Preda,Science 292,472(2001).
16 T.Albash,and D.A.Lidar,Rev.Mod.Phys.90,015002(2018),arXiv:1611.04471.
17 N.Xu,X.Peng,M.Shi,and J.F.Du,.arXiv:65.062310
18 T.Wang,Z.Zhang,L.Xiang,Z.Gong,J.Wu,and Y.Yin,Sci.ChinaPhys.Mech.Astron.61,047411(2018),arXiv:1712.10089.
19 W.H.Wang,H.X.Cao,Z.L.Chen,and L.Wang,Sci.China-Phys.Mech.Astron.61,070312(2018).
20 C.J.C.Burges,Factoring As Optimization,Technical Report(Microsoft Research,2002).
21 X.Peng,Z.Liao,N.Xu,G.Qin,X.Zhou,D.Suter,and J.Du,Phys.Rev.Lett.101,220405(2008),arXiv:0808.1935.
22 N.Xu,J.Zhu,D.Lu,X.Zhou,X.Peng,and J.Du,Phys.Rev.Lett.108,130501(2012).
23 S.Pal,S.Moitra,V.S.Anjusha,A.Kumar,and T.S.Mahesh,.arXiv:1611.00998
24 R.Dridi,and H.Alghassi,Sci.Rep.7,43048(2017),arXiv:1604.05796.
25 Z.Yin,and Z.Wei,Sci.Bull.62,741(2017).
26 T.Xin,B.X.Wang,K.R.Li,X.Y.Kong,S.J.Wei,T.Wang,D.Ruan,and G.L.Long,Chin.Phys.B 27,020308(2018).
27 I.Hen,.arXiv:1612.06012
28 H.Li,Y.Liu,and G.L.Long,Sci.China-Phys.Mech.Astron.60,080311(2017),arXiv:1703.10348.
29 B.X.Wang,T.Xin,X.Y.Kong,S.J.Wei,D.Ruan,and G.L.Long,Phys.Rev.A 97,042345(2018),arXiv:1802.01420.
30 C.Wang,and H.G.Zhang,Inf.Secur.Commun.Priv.2,31(2012).
31 C.Wang,Y.J.Wang,and F.Hu,Chin.J.Netw.Inf.Secur.2,17(2016).
32 Z.K.Li,N.S.Dattani,X.Chen,X.M.Liu,H.Y.Wang,R.Tanburn,H.W.Chen,X.H.Peng,and J.F.Du,.arXiv:1706.08061
33 S.X.Jiang,K.A.Britt,A.J.McCaskey,T.S.Humble,and S.Kais,.arXiv:1804.02733
34 E.Boros,and P.L.Hammer,Discret Appl.Math.123,155(2001).
35 P.A.Parrilo,and B.Sturmfels,.arXiv:math/0103170
36 R.Barends,J.Kelly,A.Megrant,A.Veitia,D.Sank,E.Jeffrey,T.C.White,J.Mutus,A.G.Fowler,B.Campbell,Y.Chen,Z.Chen,B.Chiaro,A.Dunsworth,C.Neill,P.O’Malley,P.Roushan,A.Vainsencher,J.Wenner,A.N.Korotkov,A.N.Cleland,and J.M.Martinis,Nature 508,500(2014),arXiv:1402.4848.
37 Z.J.Chen,Metrology of Quantum Control and Measurement in Superconducting Qubits,Dissertation for the Doctoral Degree(University of California Santa Barbara,Santa Barbara,2018),pp.200-201.
2 A.K.Lenstra,H.W.Lenstra Jr,M.S.Manasse,and J.M.Pollard,in Theory of Computing 1990:Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing,edited by H.Ortiz(ACM,New York,1990),pp.564-572.
3 M.A.Nielsen,I.Chuang,and L.K.Grover,Am.J.Phys.70,558(2002).
4 S.J.Wei,T.Xin,and G.L.Long,Sci.China-Phys.Mech.Astron.61,070311(2018),arXiv:1706.08080.
5 H.L.Huang,Y.W.Zhao,T.Li,F.G.Li,Y.T.Du,X.Q.Fu,S.Zhang,X.Wang,and W.S.Bao,Front.Phys.12,120305(2017),arXiv:1612.02886.
6 T.Xin,S.Huang,S.Lu,K.Li,Z.Luo,Z.Yin,J.Li,D.Lu,G.Long,and B.Zeng,Sci.Bull.63,17(2018).
7 J.Zhou,B.J.Liu,Z.P.Hong,and Z.Y.Xue,Sci.China-Phys.Mech.Astron.61,010312(2018),arXiv:1705.08852.
8 P.W.Shor,SIAM Rev.41,303(1999).
9 L.M.K.Vandersypen,M.Steffen,G.Breyta,C.S.Yannoni,M.H.Sherwood,and I.L.Chuang,Nature 414,883(2001).
10 E.Martín-López,A.Laing,T.Lawson,R.Alvarez,X.Q.Zhou,and J.L.O’Brien,Nat.Photon 6,773(2012),arXiv:1111.4147.
11 J.A.Smolin,G.Smith,and A.Vargo,Nature 499,163(2013),arXiv:1301.7007.
12 M.R.Geller,and Z.Zhou,Sci.Rep.3,3023(2013),arXiv:1304.0128.
13 C.Gidney,.arXiv:1706.07884v2
14 A.Cho,Science 359,141(2018).
15 E.Farhi,J.Goldstone,S.Gutmann,J.Lapan,A.Lundgren,and D.Preda,Science 292,472(2001).
16 T.Albash,and D.A.Lidar,Rev.Mod.Phys.90,015002(2018),arXiv:1611.04471.
17 N.Xu,X.Peng,M.Shi,and J.F.Du,.arXiv:65.062310
18 T.Wang,Z.Zhang,L.Xiang,Z.Gong,J.Wu,and Y.Yin,Sci.ChinaPhys.Mech.Astron.61,047411(2018),arXiv:1712.10089.
19 W.H.Wang,H.X.Cao,Z.L.Chen,and L.Wang,Sci.China-Phys.Mech.Astron.61,070312(2018).
20 C.J.C.Burges,Factoring As Optimization,Technical Report(Microsoft Research,2002).
21 X.Peng,Z.Liao,N.Xu,G.Qin,X.Zhou,D.Suter,and J.Du,Phys.Rev.Lett.101,220405(2008),arXiv:0808.1935.
22 N.Xu,J.Zhu,D.Lu,X.Zhou,X.Peng,and J.Du,Phys.Rev.Lett.108,130501(2012).
23 S.Pal,S.Moitra,V.S.Anjusha,A.Kumar,and T.S.Mahesh,.arXiv:1611.00998
24 R.Dridi,and H.Alghassi,Sci.Rep.7,43048(2017),arXiv:1604.05796.
25 Z.Yin,and Z.Wei,Sci.Bull.62,741(2017).
26 T.Xin,B.X.Wang,K.R.Li,X.Y.Kong,S.J.Wei,T.Wang,D.Ruan,and G.L.Long,Chin.Phys.B 27,020308(2018).
27 I.Hen,.arXiv:1612.06012
28 H.Li,Y.Liu,and G.L.Long,Sci.China-Phys.Mech.Astron.60,080311(2017),arXiv:1703.10348.
29 B.X.Wang,T.Xin,X.Y.Kong,S.J.Wei,D.Ruan,and G.L.Long,Phys.Rev.A 97,042345(2018),arXiv:1802.01420.
30 C.Wang,and H.G.Zhang,Inf.Secur.Commun.Priv.2,31(2012).
31 C.Wang,Y.J.Wang,and F.Hu,Chin.J.Netw.Inf.Secur.2,17(2016).
32 Z.K.Li,N.S.Dattani,X.Chen,X.M.Liu,H.Y.Wang,R.Tanburn,H.W.Chen,X.H.Peng,and J.F.Du,.arXiv:1706.08061
33 S.X.Jiang,K.A.Britt,A.J.McCaskey,T.S.Humble,and S.Kais,.arXiv:1804.02733
34 E.Boros,and P.L.Hammer,Discret Appl.Math.123,155(2001).
35 P.A.Parrilo,and B.Sturmfels,.arXiv:math/0103170
36 R.Barends,J.Kelly,A.Megrant,A.Veitia,D.Sank,E.Jeffrey,T.C.White,J.Mutus,A.G.Fowler,B.Campbell,Y.Chen,Z.Chen,B.Chiaro,A.Dunsworth,C.Neill,P.O’Malley,P.Roushan,A.Vainsencher,J.Wenner,A.N.Korotkov,A.N.Cleland,and J.M.Martinis,Nature 508,500(2014),arXiv:1402.4848.
37 Z.J.Chen,Metrology of Quantum Control and Measurement in Superconducting Qubits,Dissertation for the Doctoral Degree(University of California Santa Barbara,Santa Barbara,2018),pp.200-201.