Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms
<|reference_start|>Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms: 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.<|reference_end|>
@article{pilatte2024unconditional,
    title={Unconditional correctness of recent quantum algorithms for factoring and
  computing discrete logarithms},
    author={C'edric Pilatte},
    journal={arXiv preprint arXiv:2404.16450},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.16450},
    primaryClass={math.NT cs.CC quant-ph}
}