International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Space-Efficient and Noise-Robust Quantum Factoring

Authors:
Seyoon Ragavan , MIT
Vinod Vaikuntanathan , MIT
Download:
DOI: 10.1007/978-3-031-68391-6_4 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
Abstract: We provide two improvements to Regev's recent quantum factoring algorithm (arXiv:2308.06572), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using O(nlog⁡n) qubits and O(n3/2log⁡n) gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires O(n3/2) qubits and O(n3/2log⁡n) gates, while Shor's circuit requires O(n2log⁡n) gates but only O(n) qubits. As with Regev, to factor an n-bit integer N, we run our circuit independently ≈n times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling \emph{in-place} quantum-quantum modular multiplication. This implementation works with only black-box access to any quantum circuit for \emph{out-of-place} modular multiplication, which we believe is yet another result of potentially broader interest. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all ≈n runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.
BibTeX
@inproceedings{crypto-2024-34305,
  title={Space-Efficient and Noise-Robust Quantum Factoring},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68391-6_4},
  author={Seyoon Ragavan and Vinod Vaikuntanathan},
  year=2024
}