Current browse context:
math.NT
Change to browse by:
References & Citations
Mathematics > Number Theory
Title: Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms
(Submitted on 25 Apr 2024)
Abstract: In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multi-dimensional 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.
Link back to: arXiv, form interface, contact.