Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise

Abstract

We consider Shor's quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form $pq$ when the noise exceeds a vanishingly small level in terms of $n$ -- the number of bits of the integer to be factored, where $p$ and $q$ are from a well-defined set of primes of positive density. We further prove that with probability $1-o(1)$ over random prime pairs $(p,q)$, Shor's factoring algorithm does not factor numbers of the form $pq$, with the same level of random noise present.

References in corpus (9)

• Quantum Computing in the NISQ era and beyond
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Multiple Particle Interference and Quantum Error Correction
• Quantum Computing with Very Noisy Devices
• Maintaining coherence in Quantum Computers
• Scalability of Shor's algorithm with a limited set of rotation gates
• Quantum computing with trapped ions, atoms and light
• Scaling laws for Shor's algorithm with a banded quantum Fourier transform
• Time Quantization and q-Deformations

Cited by in corpus (3)

• Noise-induced shallow circuits and absence of barren plateaus
• Simon's Period Finding on a Quantum Annealer
• Quantum Algorithms for Discrete Log Require Precise Rotations