A Sharp Noise Threshold for Shor's Quantum Factoring and Discrete Log Algorithms
In the authors' words
We study the asymptotic behavior of Shor's quantum factoring and discrete log algorithms when noise affects the precise controlled rotation gates in their quantum Fourier transforms. Improving the results of Cai (2024) and Cai and Young (2025), we identify a sharp and vanishingly small noise threshold. If the noise level lies below this threshold, then the two algorithms succeed in expected polynomial time. If the noise level exceeds this threshold, then the algorithms provably fail to solve their respective problems in expected polynomial time when the underlying primes belong to a set of positive density.
Main resultLimitation the authors admit
Appeared: Tuesday, September 22. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 21 pages