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:2412.17269 · ACM Transactions on Quantum Computing

Quantum Algorithms for Discrete Log Require Precise Rotations

Jin‐Yi Cai, Ben Young

Published May 17, 2025• 1 citation
arXivHTMLPDF

Abstract

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 .

DOI
10.1145/3736421

Related papers

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

Jin-Yi Cai, Ben Young

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.

quant-pharXiv:2609.24316•Sep 22, 2026•0 citations

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

A simplification of the Shor quantum factorization algorithm employing a quantum Hadamard transform

Rupert C. D. Young, Philip M. Birch, Chris R. Chatwin

The Shor quantum factorization algorithm allows the factorization or large integers in logarithmic squared time whereas classical algorithms require an exponential time increase with the bit length of the number to be factored. The hardware implementation of the Shor algorithm would thus allow the factorization of the very large integers employed by commercial encryption methods. We propose some modifications of the algorithm by employing some simplification to the stage employing the quantum Fourier transform. The quantum Hadamard transform may be used to replace the quantum Fourier transform in certain cases. This would reduce the hardware complexity of implementation since phase rotation gates with only two states of 0 and π would be required.

Pattern Recognition and Tracking•Apr 27, 2018•5 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

Operator Imprecision and Scaling of Shor's Algorithm

Connie R. Hill, George F. Viamontes

Shor's algorithm (SA) is a quantum algorithm for factoring integers. Since SA has polynomial complexity while the best classical factoring algorithms are sub-exponential, SA is cited as evidence that quantum computers are more powerful than classical computers. SA is critically dependent on the Quantum Fourier Transform (QFT) and it is known that the QFT is sensitive to errors in the quantum state input to it. In this paper, we show that the polynomial scaling of SA is destroyed by input errors to the QFT part of the algorithm. We also show that Quantum Error Correcting Codes (QECC) are not capable of suppressing errors due to operator imprecision and that propagation of operator precision errors is sufficient to severely degrade the effectiveness of SA. Additionally we show that operator imprecision in the error correction circuit for the Calderbank-Shor-Steane QECC is mathematically equivalent to decoherence on every physical qubit in a register. We conclude that, because of the effect of operator precision errors, it is likely that physically realizable quantum computers will be capable of factoring integers no more efficiently than classical computers.

arXiv:0804.3076•Apr 18, 2008•0 citations

Approximate quantum Fourier transform with O(n log(n)) T gates

Yunseong Nam, Yuan Su, Dmitri A Maslov

Abstract The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an n-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of $$O(n\,{\mathrm{log}}^{2}\,(n))$$ O ( n log 2 ( n ) ) . In this paper, we show how to obtain approximate QFT with the T-count of $$O(n\,{\mathrm{log}}\,(n))$$ O ( n log ( n ) ) . For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.

arXiv:1803.04933•npj Quantum Information•Mar 13, 2020•122 citations
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 .
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.
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 Shor quantum factorization algorithm allows the factorization or large integers in logarithmic squared time whereas classical algorithms require an exponential time increase with the bit length of the number to be factored. The hardware implementation of the Shor algorithm would thus allow the factorization of the very large integers employed by commercial encryption methods. We propose some modifications of the algorithm by employing some simplification to the stage employing the quantum Fourier transform. The quantum Hadamard transform may be used to replace the quantum Fourier transform in certain cases. This would reduce the hardware complexity of implementation since phase rotation gates with only two states of 0 and π would be required.
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 (SA) is a quantum algorithm for factoring integers. Since SA has polynomial complexity while the best classical factoring algorithms are sub-exponential, SA is cited as evidence that quantum computers are more powerful than classical computers. SA is critically dependent on the Quantum Fourier Transform (QFT) and it is known that the QFT is sensitive to errors in the quantum state input to it. In this paper, we show that the polynomial scaling of SA is destroyed by input errors to the QFT part of the algorithm. We also show that Quantum Error Correcting Codes (QECC) are not capable of suppressing errors due to operator imprecision and that propagation of operator precision errors is sufficient to severely degrade the effectiveness of SA. Additionally we show that operator imprecision in the error correction circuit for the Calderbank-Shor-Steane QECC is mathematically equivalent to decoherence on every physical qubit in a register. We conclude that, because of the effect of operator precision errors, it is likely that physically realizable quantum computers will be capable of factoring integers no more efficiently than classical computers.
Abstract The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an n-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of O(n log2 (n))O(n\,{\mathrm{log}}^{2}\,(n))O(nlog2(n)) O ( n log 2 ( n ) ) . In this paper, we show how to obtain approximate QFT with the T-count of O(n log (n))O(n\,{\mathrm{log}}\,(n))O(nlog(n)) O ( n log ( n ) ) . For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.