AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (2.5 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Deciphering a Million-Plus RSA Integer with Ultralow Local Field Coefficient h and Coupling Coefficient J of the Ising Model by D-Wave 2000Q

Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication, Shanghai University, Shanghai 200444, China
Show Author Information

Abstract

This work is the first to determine that a real quantum computer (including generalized and specialized) can decipher million-scale RSA relying solely on quantum algorithms, showing the real attack potential of D-Wave machines. The influence of different column widths on RSA factorization results is studied on the basis of a multiplication table, and the optimal column method is determined by traversal experiments. The traversal experiment of integer factorization within 10 000 shows that the local field and coupling coefficients are 75%–93% lower than the research of Shanghai University in 2020 and more than 85% lower than that of Purdue University in 2018. Extremely low Ising model parameters are crucial to reducing the hardware requirements, prompting factoring 1245407 on the D-Wave 2000Q real machine. D-Wave advantage already has more than 5000 qubits and will be expanded to 7000 qubits during 2023–2024, with remarkable improvements in decoherence and topology. This machine is expected to promote the solution of large-scale combinatorial optimization problems. One of the contributions of this paper is the discussion of the long-term impact of D-Wave on the development of post-quantum cryptography standards.

Keywords

post-quantum cryptographyquantum annealingRSAD-Wave 2000Q

References

[1]

R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, vol. 21, no. 2, pp. 120–126, 1978.
Crossref Google Scholar
[2]
P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in Proc. 35th Annual Symp. on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124–134.
[3]

E. Martín-López, A. Laing, T. Lawson, R. Alvarez, X. Q. Zhou, and J. L. O'Brien, Experimental realization of Shor’s quantum factoring algorithm using qubit recycling, Nat. Photonics, vol. 6, no. 11, pp. 773–776, 2012.
Crossref Google Scholar
[4]

M. R. Geller and Z. Zhou, Factoring 51 and 85 with 8 qubits, Sci. Rep., vol. 3, p. 3023, 2013.
Crossref Google Scholar
[5]

T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, and R. Blatt, Realization of a scalable shor algorithm, Science, vol. 351, no. 6277, pp. 1068–1070, 2016.
Crossref Google Scholar
[6]

D. Castelvecchi, Quantum computers ready to leap out of the lab in 2017, Nature, vol. 541, no. 7635, pp. 9–10, 2017.
Crossref Google Scholar
[7]
A. Cho, DOE pushes for useful quantum computing, Science, vol. 359, no. 6372, pp. 141–142, 2018.
Crossref
[8]

M. Dyakonov, When will useful quantum computers be constructed? Not in the foreseeable future, this physicist argues. Here’s why: The case against: Quantum computing, IEEE Spectr., vol. 56, no. 3, pp. 24–29, 2019.
Crossref Google Scholar
[9]
E. Gibney, Physics: Quantum computer quest, Nature 516, https://doi.org/10.1038/516024a, 2014.
Crossref
[10]
C. Gidney, Factoring with n+2 clean qubits and n−1 dirty qubits, arXiv preprint arXiv: 1706.07884, 2017.
[11]

C. Wang, H. Yao, B. Wang, F. Hu, H. Zhang, and X. Ji, Advances in cryptographic Attacks for quantum computing, (in Chinese), Chinese J. Comput., vol. 43, no. 9, pp. 1691–1707, 2020.
Google Scholar
[12]

N. Chancellor, Fluctuation-guided search in quantum annealing, Phys. Rev. A, vol. 102, no. 6, p. 062606, 2020.
Crossref Google Scholar
[13]

E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science, vol. 292, no. 5516, pp. 472–475, 2001.
Crossref Google Scholar
[14]

X. Peng, Z. Liao, N. Xu, G. Qin, X. Zhou, D. Suter, and J. Du, Quantum adiabatic algorithm for factorization and its experimental implementation, Phys. Rev. Lett., vol. 101, no. 22, p. 220405, 2008.
Crossref Google Scholar
[15]
C. J. C. Burges, Factoring as optimization, Microsoft Res MSR-TR-200, https://www.microsoft.com/en-us/research/publication/factoring-as-optimization/, 2002.
[16]

G. Schaller and R. Schutzhold, The role of symmetries in adiabatic quantum algorithms, Quantum Inf. Comput., vol. 10, nos. 1&2, pp. 109–140, 2010.
Crossref Google Scholar
[17]

N. Xu, J. Zhu, D. Lu, X. Zhou, X. Peng, and J. Du, Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system, Phys. Rev. Lett., vol. 108, no. 13, p. 130501, 2012.
Crossref Google Scholar
[18]

S. Jiang, K. A. Britt, A. J. McCaskey, T. S. Humble, and S. Kais, Quantum annealing for prime factorization, Sci. Rep., vol. 8, no. 1, p. 17667, 2018.
Crossref Google Scholar
[19]

W. Peng, B. Wang, F. Hu, Y. Wang, X. Fang, X. Chen, and C. Wang, Factoring larger integers with fewer qubits via quantum annealing with optimized parameters, Sci. China Phys. Mech. Astron., vol. 62, no. 6, pp. 1–8, 2019.
Crossref Google Scholar
[20]

C. Wang and H. G. Zhang, The impact of commercial quantum computer on cryptography, (in Chinese), Inf. Secur. Commun. Priv., vol. 2, pp. 31–32, 2012.
Google Scholar
[21]
N. S. Dattani and N. Bryans, Quantum factorization of 56153 with only 4 qubits, arXiv preprint arXiv: 1411.6758, 2014.
[22]

N. N. Hegade, K. Paul, F. Albarrán-Arriagada, X. Chen, and E. Solano, Digitized adiabatic quantum factorization, Phys. Rev. A, vol. 104, no. 5, p. L050403, 2021.
Crossref Google Scholar
[23]

B. Wang, H. Yao, F. Hu, and C. Wang, Quantum annealing distributed integer decomposition study of local field coefficient h and coupling coefficient J with stability Ising model, Sci. Sin.-Phys. Mech. Astron., vol. 50, no. 3, p. 030301, 2020.
Crossref Google Scholar
[24]

B. Wang, F. Hu, H. Yao, and C. Wang, Prime factorization algorithm based on parameter optimization of Ising model, Sci. Rep., vol. 10, no. 1, p. 7106, 2020.
Crossref Google Scholar
[25]

C. Gidney and M. Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, Quantum, vol. 5, p. 433, 2021.
Crossref Google Scholar
[26]
M. Mosca and M. Piani, Quantum threat timeline, https://globalriskinstitute.org/publication/quantum-threat-timeline/, 2019.
[27]

É. Gouzien and N. Sangouard, Factoring 2048-bit RSA integers in 177 days with 13436 qubits and a multimode memory, Phys. Rev. Lett., vol. 127, no. 14, p. 140503, 2021.
Crossref Google Scholar
[28]

F. X. Cui, B. Wang, Y. Liu, and Y. Li, Research status and prospect of quantum attack on public key cryptography, (in Chinese), Network Security and Data Governance, vol. 41, no. 3, pp. 3–12, 2022.
Google Scholar
[29]

S. Muthukrishnan, T. Albash, and D. A. Lidar, Tunneling and speedup in quantum optimization for permutation-symmetric problems, Phys. Rev. X, vol. 6, no. 3, p. 031010, 2016.
Crossref Google Scholar
[30]
B. Yan, Z. Tan, S. Wei, H. Jiang, W. Wang, H. Wang, L. Luo, Q. Duan, Y. Liu, W. Shi, et al., Factoring integers with sublinear resources on a superconducting quantum processor, arXiv preprint arXiv: 2212.12372, 2022.
[31]

D. A. Lidar, A. T. Rezakhani, and A. Hamma, Adiabatic approximation with exponential accuracy for many-body systems and quantum computation, J. Math. Phys., vol. 50, no. 10, p. 102106, 2009.
Crossref Google Scholar
[32]

V. Choi, Minor-embedding in adiabatic quantum computation: I. The parameter setting problem, Quantum Inf. Process., vol. 7, no. 5, pp. 193–209, 2008.
Crossref Google Scholar
[33]

W. L. Du, B. Li, and Y. Tian, Quantum annealing algorithms: State of the art, (in Chinese), J. Comput. Res. Dev., vol. 45, no. 9, pp. 1501–1508, 2008.
Google Scholar
[34]
D-Wave systems, D-wave initiates open quantum software environment, https://www.dwavesys.com/press-releases/d-wave-initiates-open-quantum-software-environment, 2017.
[35]

R. H. Warren, Factoring on a quantum annealing computer, Quantum Inf. Comput., vol. 19, nos. 3&4, pp. 252–261, 2019.
Crossref Google Scholar
[36]

Y. Q. Chen, Y. Chen, C. K. Lee, S. Zhang, and C. Y. Hsieh, Optimizing quantum annealing schedules with Monte Carlo tree search enhanced with neural networks, Nat. Mach. Intell., vol. 4, no. 3, pp. 269–278, 2022.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 29 Issue 3,
June 2024
Pages 874-882
DOI: 10.26599/TST.2023.9010059
Cite this article:
Wang C, Hu Q, Yao H, et al. Deciphering a Million-Plus RSA Integer with Ultralow Local Field Coefficient h and Coupling Coefficient J of the Ising Model by D-Wave 2000Q. Tsinghua Science and Technology, 2024, 29(3): 874-882. https://doi.org/10.26599/TST.2023.9010059

548

Views

140

Downloads

0

Crossref

0

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 26 March 2023
Revised: 12 May 2023
Accepted: 13 June 2023
Published: 04 December 2023
© The Author(s) 2024.

The articles published in this open access journal are distributed under the terms of theCreative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return