Large-Scale Simulation of Shor’s Quantum Factoring Algorithm

Dennis Willsch; Madita Willsch; Fengping Jin; Hans De Raedt; Kristel Michielsen

doi:10.3390/math11194222

journal article Open Access Oct 09, 2023

Large-Scale Simulation of Shor’s Quantum Factoring Algorithm

Dennis Willsch

Mathematics Vol. 11 No. 19 pp. 4222 · MDPI AG

View at Publisher Save 10.3390/math11194222

Abstract

Shor’s factoring algorithm is one of the most anticipated applications of quantum computing. However, the limited capabilities of today’s quantum computers only permit a study of Shor’s algorithm for very small numbers. Here, we show how large GPU-based supercomputers can be used to assess the performance of Shor’s algorithm for numbers that are out of reach for current and near-term quantum hardware. First, we study Shor’s original factoring algorithm. While theoretical bounds suggest success probabilities of only 3–4%, we find average success probabilities above 50%, due to a high frequency of “lucky” cases, defined as successful factorizations despite unmet sufficient conditions. Second, we investigate a powerful post-processing procedure, by which the success probability can be brought arbitrarily close to one, with only a single run of Shor’s quantum algorithm. Finally, we study the effectiveness of this post-processing procedure in the presence of typical errors in quantum processing hardware. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors. The largest semiprime that we have factored by executing Shor’s algorithm on a GPU-based supercomputer, without exploiting prior knowledge of the solution, is 549,755,813,701 = 712,321 × 771,781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.

Topics

No keywords indexed for this article. Browse by subject →

References

115

[1]

Bressoud, D.M. (1989). Factorization and Primality Testing, Springer. 10.1007/978-1-4612-4544-5

[2]

Lehman "Factoring large integers" Math. Comput. (1974) 10.1090/s0025-5718-1974-0340163-2

[3]

Lenstra, A.K., and Lenstra, H.W. (1993). The Development of the Number Field Sieve, Springer. Lecture Notes in Mathematics. 10.1007/bfb0091534

[4]

Micciancio, D., and Ristenpart, T. (2020, January 17–21). Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment. Proceedings of the Advances in Cryptology—CRYPTO 2020, Virtual.

[5]

Rabin, T. (2010, January 15–19). Factorization of a 768-Bit RSA Modulus. Proceedings of the Advances in Cryptology—CRYPTO 2010, Santa Barbara, CA, USA.

[6]

How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

Craig Gidney, Martin Ekerå

Quantum 2021 10.22331/q-2021-04-15-433

[7]

Biasse "Quantum algorithms for attacking hardness assumptions in classical and post-quantum cryptography" IET Inf. Secur. (2023) 10.1049/ise2.12081

[8]

Shor, P.W. (1994, January 20–22). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA.

[9]

Ekert "Quantum computation and Shor’s factoring algorithm" Rev. Mod. Phys. (1996) 10.1103/revmodphys.68.733

[10]

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Peter W. Shor

SIAM Journal on Computing 1997 10.1137/s0097539795293172

[11]

Itoh "Fast quantum modular exponentiation" Phys. Rev. A (2005) 10.1103/physreva.71.052320

[12]

Kitaev, A.Y. (1995). Quantum measurements and the Abelian Stabilizer Problem. arXiv.

[13]

Griffiths "Semiclassical Fourier Transform for Quantum Computation" Phys. Rev. Lett. (1996) 10.1103/physrevlett.76.3228

[14]

Parker "Efficient Factorization with a Single Pure Qubit and logN Mixed Qubits" Phys. Rev. Lett. (2000) 10.1103/physrevlett.85.3049

[15]

Experimental realization of Shor's quantum factoring algorithm using qubit recycling

Enrique Martín-López, Anthony Laing, Thomas Lawson et al.

Nature Photonics 2012 10.1038/nphoton.2012.259

[16]

Takita "Exploiting Dynamic Quantum Circuits in a Quantum Algorithm with Superconducting Qubits" Phys. Rev. Lett. (2021) 10.1103/physrevlett.127.100501

[17]

Peng "Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation" Phys. Rev. Lett. (2008) 10.1103/physrevlett.101.220405

[18]

Hegade "Digitized adiabatic quantum factorization" Phys. Rev. A (2021) 10.1103/physreva.104.l050403

[19]

Monz "Realization of a scalable Shor algorithm" Science (2016) 10.1126/science.aad9480

[20]

Amico "Experimental study of Shor’s factoring algorithm using the IBM Q Experience" Phys. Rev. A (2019) 10.1103/physreva.100.012305

[21]

Smolin "Oversimplifying quantum factoring" Nature (2013) 10.1038/nature12290

[22]

Gouzien "Factoring 2048-bit RSA Integers in 177 Days with 13 436 Qubits and a Multimode Memory" Phys. Rev. Lett. (2021) 10.1103/physrevlett.127.140503

[23]

(2023, September 18). shorgpu: Simulation of Shor’s Algorithm with the Semiclassical Fourier Transform Using Multiple GPUs and MPI. Available online: https://jugit.fz-juelich.de/qip/shorgpu.git.

[24]

Michielsen "Massively parallel quantum computer simulator" Comput. Phys. Commun. (2007) 10.1016/j.cpc.2006.08.007

[25]

Jin "Massively parallel quantum computer simulator, eleven years later" Comput. Phys. Commun. (2019) 10.1016/j.cpc.2018.11.005

[26]

Tankasala, A., and Ilatikhameneh, H. (2020). Quantum-Kit: Simulating Shor’s Factorization of 24-Bit Number on Desktop. arXiv.

[27]

Wang "Simulations of Shor’s algorithm using matrix product states" Quantum Inf. Process. (2017) 10.1007/s11128-017-1587-x

[28]

Dang "Optimising Matrix Product State Simulations of Shor’s Algorithm" Quantum (2019) 10.22331/q-2019-01-25-116

[29]

Dumitrescu "Tree tensor network approach to simulating Shor’s algorithm" Phys. Rev. A (2017) 10.1103/physreva.96.062322

[30]

Zhao "Simulation of quantum computing on classical supercomputers with tensor-network edge cutting" Phys. Rev. A (2021) 10.1103/physreva.104.032603

[31]

Ekerå, M. (2023, September 18). Qunundrum. Available online: https://github.com/ekera/qunundrum.git.

[32]

Nielsen, M.A., and Chuang, I.L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition, Cambridge University Press.

[33]

"On completely factoring any integer efficiently in a single run of an order-finding algorithm" Quantum Inf. Process. (2021) 10.1007/s11128-021-03069-1

[34]

Ekerå, M. (2022). On the success probability of quantum order finding. arXiv.

[35]

Quantum supremacy using a programmable superconducting processor

Frank Arute, Kunal Arya, Ryan Babbush et al.

Nature 2019 10.1038/s41586-019-1666-5

[36]

Defining and detecting quantum speedup

Troels F. Rønnow, Zhihui Wang, Joshua Job et al.

Science 2014 10.1126/science.1252319

[37]

Knill, E. (1995). On Shor’s Quantum Factor Finding Algorithm: Increasing the Probability of Success and Tradeoffs Involving the Fourier Transform Modulus, Los Alamos National Laboratory. Tech. Rep. LAUR-95-3350.

[38]

DiVincenzo "Quantum Computation" Science (1995) 10.1126/science.270.5234.255

[39]

Barenco "Approximate quantum Fourier transform and decoherence" Phys. Rev. A (1996) 10.1103/physreva.54.139

[40]

Vedral "Quantum networks for elementary arithmetic operations" Phys. Rev. A (1996) 10.1103/physreva.54.147

[41]

Naccache, D. (2001, January 8–12). Using Fewer Qubits in Shor’s Factorization Algorithm via Simultaneous Diophantine Approximation. Proceedings of the Topics in Cryptology—CT-RSA 2001, San Francisco, CA, USA. 10.1007/3-540-45353-9

[42]

McAnally, D. (2001). A Refinement of Shor’s Algorithm. arXiv.

[43]

Leander, G. (2002). Improving the Success Probability for Shor’s Factoring Algorithm. arXiv.

[44]

Coppersmith, D. (2002). An approximate Fourier transform useful in quantum factoring. arXiv.

[45]

Beauregard "Circuit for Shor’s algorithm using 2n+3 qubits" Quantum Inf. Comput. (2003)

[46]

Fowler "Scalability of Shor’s algorithm with a limited set of rotation gates" Phys. Rev. A (2004) 10.1103/physreva.70.032329

[47]

Kendon "Entanglement and its Role in Shor’s Algorithm" Quantum Inf. Comput. (2006)

[48]

Gerjuoy "Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers" Am. J. Phys (2005) 10.1119/1.1891170

[49]

Devitt "Robustness of Shor’s algorithm" Quantum Inf. Comput. (2006)

[50]

Zalka, C. (2016). Shor’s algorithm with fewer (pure) qubits. arXiv.

Showing 50 of 115 references

Metrics

25

Citations

115

References

Details

Published: Oct 09, 2023
Vol/Issue: 11(19)
Pages: 4222
License: View

Authors

D

Dennis Willsch

Jülich Supercomputing Centre, Institute for Advanced Simulation, Forschungszentrum Jülich, 52425 Jülich, Germany

M

Madita Willsch

Jülich Supercomputing Centre, Institute for Advanced Simulation, Forschungszentrum Jülich, 52425 Jülich, Germany; AIDAS, 52425 Jülich, Germany

F

Fengping Jin

Jülich Supercomputing Centre, Institute for Advanced Simulation, Forschungszentrum Jülich, 52425 Jülich, Germany

H

Hans De Raedt

Jülich Supercomputing Centre, Institute for Advanced Simulation, Forschungszentrum Jülich, 52425 Jülich, Germany; Zernike Institute for Advanced Materials, University of Groningen, Nijenborgh 4, 9747 AG Groningen, The Netherlands

K

Kristel Michielsen

Jülich Supercomputing Centre, Institute for Advanced Simulation, Forschungszentrum Jülich, 52425 Jülich, Germany; AIDAS, 52425 Jülich, Germany; Department of Physics, RWTH Aachen University, 52056 Aachen, Germany

Funding

Ministry of Culture and Science of the State of North Rhine-Westphalia

German Federal Ministry of Education and Research (BMBF)

Gauss Centre for Supercomputing e.V.

Jülich UNified Infrastructure for Quantum computing (JUNIQ)

Cite This Article

Dennis Willsch, Madita Willsch, Fengping Jin, et al. (2023). Large-Scale Simulation of Shor’s Quantum Factoring Algorithm. Mathematics, 11(19), 4222. https://doi.org/10.3390/math11194222

Large-Scale Simulation of Shor’s Quantum Factoring Algorithm

You May Also Like