arXiv:2609.24316
A Sharp Noise Threshold for Shor's Quantum Factoring and Discrete Log Algorithms
Jin-Yi Cai, Ben Young
Abstract
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.
AI Summary
The paper asks how independent Gaussian errors in QFT controlled rotations affect the asymptotic performance of Shor’s factoring and discrete-log algorithms. Gates with rotation index $k<b$ are exact; for $k\ge b$, the angle $2\pi 2^{-k}$ is multiplied by $1+\epsilon r$, with independent $r\sim N(0,1)$ for each gate. The analysis assumes $b=O(\log n)$ and no other noise. It identifies a boundary at effective noise $\epsilon/2^b\asymp\sqrt{\log n/n}$. Below this scale, in the sense $\epsilon/2^b=O(\sqrt{\log n/n})$, the noise-averaged probability of designated useful measurement outcomes is inverse-polynomial, yielding expected polynomial runtime. If the ratio to this scale diverges, that probability is superpolynomially small for factoring products of primes from a positive-density set, and for discrete logarithms over such primes for all but an exponentially small fraction of inputs. Although theorem statements describe exponential suppression, the proofs establish superpolynomial suppression under the stated general condition. The proofs expand squared Fourier amplitudes into pairwise interference terms. Gaussian averaging damps each term by an exponential of its phase-difference variance. Upper variance bounds establish the low-noise result; previously established binary-digit distribution estimates for primes satisfying $\mathcal P^+(P-1)>P^{2/3}$ supply high-noise lower bounds. The negative results concern specified useful-outcome sets in these implementations, not arbitrary quantum algorithms or postprocessing. The paper acknowledges that fault-tolerance thresholds permit suppression of independent noise below a constant physical threshold, but questions the physical accuracy of large tensor-product models; that concern is not established by the noise analysis.
Central claim may not hold: The negative proofs suppress only designated sufficient measurement outcomes, without establishing that other outcomes or polynomially many samples cannot solve the problems. The above-threshold condition yields superpolynomial suppression rather than the exponentially small success probabilities and exponentially high failure probabilities stated in the theorems and introduction. The formal threshold results require b = O(log n), and the discrete-log negative result excludes an exponentially small fraction of inputs y, qualifications omitted from the abstract. The factoring proof uses only n Fourier qubits for an n-bit N, unjustifiably discards its remaining ω/2^n term, and does not supply the claimed classical order-recovery guarantee at that Fourier resolution. The factoring calculation incorrectly replaces a sum over residue classes by ω times one contribution despite residue-class dependence in both progression lengths and noisy phases.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 21 pages