Large-Scale Simulation of Shor's Quantum Factoring Algorithm
arXiv:2308.05047 · doi: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 549755813701 = 712321 * 771781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.
arXiv commentdiffers from the published version in formatting and style; open source code available at https://jugit.fz-juelich.de/qip/shorgpu
References in corpus (47)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
- Quantum Networks for Elementary Arithmetic Operations
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- 1/f noise: implications for solid-state quantum information
- Defining and detecting quantum speedup
- Approaching Unit Visibility for Control of a Superconducting Qubit with Dispersive Readout
- From Classical to Quantum Shannon Theory
- Realization of a scalable Shor algorithm
- Shor's quantum factoring algorithm on a photonic chip
- Semiclassical Fourier Transform for Quantum Computation
- Qubit-photon interactions in a cavity: Measurement induced dephasing and number splitting
- Real-time quantum error correction beyond break-even
- Exponential suppression of bit or phase flip errors with repetitive error correction
- Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
- Experimental demonstration of Shor's algorithm with quantum entanglement
- Computing prime factors with a Josephson phase qubit quantum processor
- High-Fidelity Readout in Circuit Quantum Electrodynamics Using the Jaynes-Cummings Nonlinearity
- Demonstration of Shor's quantum factoring algorithm using photonic qubits
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- Coherent quantum annealing in a programmable 2000-qubit Ising chain
- Massive Parallel Quantum Computer Simulator
- Approximate Quantum Fourier Transform and Decoherence
- Fast Quantum Modular Exponentiation
- A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
- Quantum Algorithm Implementations for Beginners
- Quantum factoring, discrete logarithms and the hidden subgroup problem
- Efficient factorization with a single pure qubit and mixed qubits
- Pretending to factor large numbers on a quantum computer
- Improved Superconducting Qubit Readout by Qubit-Induced Nonlinearities
- Massively parallel quantum computer simulator, eleven years later
- Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory
- Benchmarking gate-based quantum computers
- Prime factorization using quantum annealing and computational algebraic geometry
- An Experimental Study of Shor's Factoring Algorithm on IBM Q
- Shor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers
- Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors
- Scalability of Shor's algorithm with a limited set of rotation gates
- Quantum algorithms for computing short discrete logarithms and factoring RSA integers
- GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
- Optimising Matrix Product State Simulations of Shor's Algorithm
- Faster Quantum Number Factoring via Circuit Synthesis
- A tree tensor network approach to simulating Shor's algorithm
- Efficient realization of quantum primitives for Shor's algorithm using PennyLane library
- Simulation of Quantum Computing on Classical Supercomputers
- Odd orders in Shor's factoring algorithm