Algorithms for quantum computation: Discrete log and factoring

Peter W. Shor

Martin Ekerå, Johan Håstad

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 .

Jean Ettinger, M. Neergaard

We compute the number of gates and laser pulses required in Shor`s algorithm for finding {ital r} in the equation {ital g{sup r} = x(mod p)} where {ital p} is a prime, and {ital g} and {ital x} are given elements of the multiplicative group {ital Z{sup *}{sub p}}. Because the discrete logarithm algorithm is similar to the factoring algorithm we may utilize gates designed for use in factoring.

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.

Song Yuan Yan