Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.24316

A Sharp Noise Threshold for Shor's Quantum Factoring and Discrete Log Algorithms

Jin-Yi Cai, Ben Young

quant-phSubmitted Sep 21, 2026• Announced Sep 22, 2026• 0 citations
arXivHTMLPDF

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.

No sign of AI-generated textOverclaimsIncrementalStrong assumptionsPossible error

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

Related papers

Quantum Algorithms for Discrete Log Require Precise Rotations

Jin‐Yi Cai, Ben Young

Recently, Cai [ 3 ] showed that Shor’s quantum factoring algorithm fails to factor large integers when algorithm’s quantum Fourier transform (QFT) is corrupted by a vanishing level of random noise on the QFT’s precise controlled rotation gates. We show that under the same error model, Shor’s quantum discrete log algorithm, and its various modifications, fail to compute discrete logs modulo P for a positive density of primes P and a similarly vanishing level of noise. We also show that the same noise level causes Shor’s algorithm to fail with probability \(1-o(1)\) to compute discrete logs modulo P for randomly selected primes P .

arXiv:2412.17269•ACM Transactions on Quantum Computing•May 17, 2025•1 citation

Shor’s algorithm does not factor large integers in the presence of noise

Jin‐Yi Cai

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.

arXiv:2306.10072•Science China Information Sciences•Jun 18, 2024•27 citations

The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers

Yoshinori Aono, Sitong Liu, Tomoki Tanaka +4 more

The discrete logarithm problem (DLP) is the basis for several cryptographic primitives. Since Shor’s work, it has been known that the DLP can be solved by combining a polynomial-size quantum circuit and a polynomial-time classical post-processing algorithm. The theoretical result corresponds the situation where a quantum device working with a medium number of qubits of very small errors can solve DLP. However, all the quantum devices that we can use have a limited number of noisy qubits, as of the noisy intermediate-scale quantum (NISQ) era. Thus, evaluating the instance size that the latest quantum device can solve, and give a future prediction of the size along the progress of quantum devices are emerging research topics. This paper contains two proposal to discuss the performance of quantum devices against DLP in the NISQ era. (1) A quantitative measure based on the success probability of the post-processing algorithm to determine whether an experiment on a quantum device (or a classical simulator) succeeded. (2) A procedure to modify bit strings observed from a Shor’s circuit to increase the success probability of a lattice-based post-processing algorithm. We conducted our experiments with theibm_kawasakidevice and discovered that the simplest circuit (7 qubits) from a 2-bit DLP instance achieves a sufficiently high success probability to proclaim the experiment successful. Experiments on another circuit from a slightly harder 2-bit DLP instance, on the other hand, did not succeed, and we determined that reducing the noise level by half is required to achieve a successful experiment. Finally, we give a near-term prediction based on required noise levels to solve some selected small DLP and integer factoring instances.

arXiv:2111.06102•IEEE Transactions on Quantum Engineering•Jan 1, 2022•13 citations

Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms

Cédric Pilatte

Abstract In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multidimensional version of Shor’s algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in $(\mathbb {Z}/N\mathbb {Z})^{\times }$ that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such as zero-density estimates. As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm and of subsequent variants.

arXiv:2404.16450•Forum of Mathematics Pi•Jan 1, 2026•13 citations

Shor's Algorithm Using Efficient Approximate Quantum Fourier Transform

Kento Oonishi, Noboru Kunihiro

Shor's algorithm solves the integer factoring and discrete logarithm problems in polynomial time. Therefore, the evaluation of Shor's algorithm is essential for evaluating the security of currently used public-key cryptosystems because the integer factoring and discrete logarithm problems are crucial for the security of these cryptosystems. In this article, a new approximate quantum Fourier transform is proposed, and it is applied to Rines and Chuang's implementation. The proposed implementation requires one-third the number of$T$gates of the original. Moreover, it requires one-fourth the$T$-depth of the original. Finally, a$T$-scheduling method for running the circuit with the smallest KQ is presented.

IEEE Transactions on Quantum Engineering•Jan 1, 2023•22 citations

Asymptotic Vanishing of the Success Probability in Shor's Algorithm

João Pires da Cruz

Shor's factoring algorithm guarantees a success probability of at least one half for any fixed modulus N = pq with distinct primes p and q. We show that this guarantee does not extend to the asymptotic regime. As N -> infinity, the multiplicative groups Omega_N = (Z/NZ)^x form a non-tight family of probability spaces, and the probability weight associated with successful bases, proportional to p(success | a', N) p(a' | N), decays as 1/phi(N). The ensemble of uniform measures {mu_N} therefore admits no weak limit, implying an asymptotic loss of ergodicity. Monte Carlo simulations up to N <= 10^6 confirm this decay and the absence of a stationary success probability. These results demonstrate that the "expected polynomial time" in order finding is only locally defined: no global expectation exists once the arithmetic domain expands. The asymptotic vanishing of success probability explains the empirical absence of large-N implementations of Shor's algorithm and sets a fundamental limit on the scalability of quantum factoring.

arXiv:2510.06271•Oct 6, 2025•0 citations
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.
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<bk<bk<b are exact; for k≥bk\ge bk≥b, the angle 2π2−k2\pi 2^{-k}2π2−k is multiplied by 1+ϵr1+\epsilon r1+ϵr, with independent r∼N(0,1)r\sim N(0,1)r∼N(0,1) for each gate. The analysis assumes b=O(log⁡n)b=O(\log n)b=O(logn) and no other noise.
It identifies a boundary at effective noise ϵ/2b≍log⁡n/n\epsilon/2^b\asymp\sqrt{\log n/n}ϵ/2b≍logn/n​. Below this scale, in the sense ϵ/2b=O(log⁡n/n)\epsilon/2^b=O(\sqrt{\log n/n})ϵ/2b=O(logn/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 P+(P−1)>P2/3\mathcal P^+(P-1)>P^{2/3}P+(P−1)>P2/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.
Recently, Cai [ 3 ] showed that Shor’s quantum factoring algorithm fails to factor large integers when algorithm’s quantum Fourier transform (QFT) is corrupted by a vanishing level of random noise on the QFT’s precise controlled rotation gates. We show that under the same error model, Shor’s quantum discrete log algorithm, and its various modifications, fail to compute discrete logs modulo P for a positive density of primes P and a similarly vanishing level of noise. We also show that the same noise level causes Shor’s algorithm to fail with probability 1−o(1)1-o(1)1−o(1) to compute discrete logs modulo P for randomly selected primes P .
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.
The discrete logarithm problem (DLP) is the basis for several cryptographic primitives. Since Shor’s work, it has been known that the DLP can be solved by combining a polynomial-size quantum circuit and a polynomial-time classical post-processing algorithm. The theoretical result corresponds the situation where a quantum device working with a medium number of qubits of very small errors can solve DLP. However, all the quantum devices that we can use have a limited number of noisy qubits, as of the noisy intermediate-scale quantum (NISQ) era. Thus, evaluating the instance size that the latest quantum device can solve, and give a future prediction of the size along the progress of quantum devices are emerging research topics. This paper contains two proposal to discuss the performance of quantum devices against DLP in the NISQ era. (1) A quantitative measure based on the success probability of the post-processing algorithm to determine whether an experiment on a quantum device (or a classical simulator) succeeded. (2) A procedure to modify bit strings observed from a Shor’s circuit to increase the success probability of a lattice-based post-processing algorithm. We conducted our experiments with theibm_kawasakidevice and discovered that the simplest circuit (7 qubits) from a 2-bit DLP instance achieves a sufficiently high success probability to proclaim the experiment successful. Experiments on another circuit from a slightly harder 2-bit DLP instance, on the other hand, did not succeed, and we determined that reducing the noise level by half is required to achieve a successful experiment. Finally, we give a near-term prediction based on required noise levels to solve some selected small DLP and integer factoring instances.
Abstract In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multidimensional version of Shor’s algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in (Z/NZ)×(\mathbb {Z}/N\mathbb {Z})^{\times }(Z/NZ)× that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such as zero-density estimates. As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm and of subsequent variants.
Shor's algorithm solves the integer factoring and discrete logarithm problems in polynomial time. Therefore, the evaluation of Shor's algorithm is essential for evaluating the security of currently used public-key cryptosystems because the integer factoring and discrete logarithm problems are crucial for the security of these cryptosystems. In this article, a new approximate quantum Fourier transform is proposed, and it is applied to Rines and Chuang's implementation. The proposed implementation requires one-third the number ofTTTgates of the original. Moreover, it requires one-fourth theTTT-depth of the original. Finally, aTTT-scheduling method for running the circuit with the smallest KQ is presented.
Shor's factoring algorithm guarantees a success probability of at least one half for any fixed modulus N = pq with distinct primes p and q. We show that this guarantee does not extend to the asymptotic regime. As N -> infinity, the multiplicative groups Omega_N = (Z/NZ)^x form a non-tight family of probability spaces, and the probability weight associated with successful bases, proportional to p(success | a', N) p(a' | N), decays as 1/phi(N). The ensemble of uniform measures {mu_N} therefore admits no weak limit, implying an asymptotic loss of ergodicity. Monte Carlo simulations up to N <= 10^6 confirm this decay and the absence of a stationary success probability. These results demonstrate that the "expected polynomial time" in order finding is only locally defined: no global expectation exists once the arithmetic domain expands. The asymptotic vanishing of success probability explains the empirical absence of large-N implementations of Shor's algorithm and sets a fundamental limit on the scalability of quantum factoring.