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.

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•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•17 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•11 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•5 citations

Shors Algorithm Using Efficient Approximate Quantum Fourier Transform

Kento Oonishi, Kunihiro Noboru

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 of the T-depth of the original. Finally, a T-scheduling method for running the circuit with the smallest KQ (where K is the number of logical qubits and Q is the circuit depth) is presented.

•Sep 25, 2023•0 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•17 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.
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 of T gates of the original. Moreover, it requires one-fourth of the T-depth of the original. Finally, a T-scheduling method for running the circuit with the smallest KQ (where K is the number of logical qubits and Q is the circuit depth) is presented.
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.