Abstract
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 2000Q 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.
Similar content being viewed by others
References
S. S. Wagstaff, Am. Math. Soc. 68, 293 (2013).
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.
M. A. Nielsen, I. Chuang, and L. K. Grover, Am. J. Phys. 70, 558 (2002).
S. J. Wei, T. **n, and G. L. Long, Sci. China–Phys. Mech. Astron. 61, 070311 (2018), ar**v: 1706.08080.
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), ar**v: 1612.02886.
T. **n, S. Huang, S. Lu, K. Li, Z. Luo, Z. Yin, J. Li, D. Lu, G. Long, and B. Zeng, Sci. Bull. 63, 17 (2018).
J. Zhou, B. J. Liu, Z. P. Hong, and Z. Y. Xue, Sci. China–Phys. Mech. Astron. 61, 010312 (2018), ar**v: 1705.08852.
P. W. Shor, SIAM Rev. 41, 303 (1999).
L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang, Nature 414, 883 (2001).
E. Martín–López, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O’Brien, Nat. Photon 6, 773 (2012), ar**v: 1111.4147.
J. A. Smolin, G. Smith, and A. Vargo, Nature 499, 163 (2013), ar**v: 1301.7007.
M. R. Geller, and Z. Zhou, Sci. Rep. 3, 3023 (2013), ar**v: 1304.0128.
C. Gidney, ar**v: 1706.07884v2
A. Cho, Science 359, 141 (2018).
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science 292, 472 (2001).
T. Albash, and D. A. Lidar, Rev. Mod. Phys. 90, 015002 (2018), ar**v: 1611.04471.
N. Xu, X. Peng, M. Shi, and J. F. Du, ar**v: 65.062310
T. Wang, Z. Zhang, L. **ang, Z. Gong, J. Wu, and Y. Yin, Sci. China–Phys. Mech. Astron. 61, 047411 (2018), ar**v: 1712.10089.
W. H. Wang, H. X. Cao, Z. L. Chen, and L. Wang, Sci. China–Phys. Mech. Astron. 61, 070312 (2018).
C. J. C. Burges, Factoring As Optimization, Technical Report (Microsoft Research, 2002).
X. Peng, Z. Liao, N. Xu, G. Qin, X. Zhou, D. Suter, and J. Du, Phys. Rev. Lett. 101, 220405 (2008), ar**v: 0808.1935.
N. Xu, J. Zhu, D. Lu, X. Zhou, X. Peng, and J. Du, Phys. Rev. Lett. 108, 130501 (2012).
S. Pal, S. Moitra, V. S. Anjusha, A. Kumar, and T. S. Mahesh, ar**v: 1611.00998
R. Dridi, and H. Alghassi, Sci. Rep. 7, 43048 (2017), ar**v: 1604.05796.
Z. Yin, and Z. Wei, Sci. Bull. 62, 741 (2017).
T. **n, 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).
I. Hen, ar**v: 1612.06012
H. Li, Y. Liu, and G. L. Long, Sci. China–Phys. Mech. Astron. 60, 080311 (2017), ar**v: 1703.10348.
B. X. Wang, T. **n, X. Y. Kong, S. J. Wei, D. Ruan, and G. L. Long, Phys. Rev. A 97, 042345 (2018), ar**v: 1802.01420.
C. Wang, and H. G. Zhang, Inf. Secur. Commun. Priv. 2, 31 (2012).
C. Wang, Y. J. Wang, and F. Hu, Chin. J. Netw. Inf. Secur. 2, 17 (2016).
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, ar**v: 1706.08061
S. X. Jiang, K. A. Britt, A. J. McCaskey, T. S. Humble, and S. Kais, ar**v: 1804.02733
E. Boros, and P. L. Hammer, Discret Appl. Math. 123, 155 (2001).
P. A. Parrilo, and B. Sturmfels, ar**v: math/0103170
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), ar**v: 1402.4848.
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.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Peng, W., Wang, B., Hu, F. et al. Factoring larger integers with fewer qubits via quantum annealing with optimized parameters. Sci. China Phys. Mech. Astron. 62, 60311 (2019). https://doi.org/10.1007/s11433-018-9307-1
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11433-018-9307-1