Quantum Algorithms for Discrete Log Require Precise Rotations

Abstract

Recently, Cai showed that Shor's quantum factoring algorithm fails to factor large integers when the 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.

14 pages

References in corpus (10)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Semiclassical Fourier Transform for Quantum Computation
• Approximate Quantum Fourier Transform and Decoherence
• Scalability of Shor's algorithm with a limited set of rotation gates
• Quantum algorithms for computing short discrete logarithms and factoring RSA integers
• Quantum computation of discrete logarithms in semigroups
• Scaling laws for Shor's algorithm with a banded quantum Fourier transform
• Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise
• Extending Regev's factoring algorithm to compute discrete logarithms
• Effects of dynamical phases in Shor's factoring algorithm with operational delays