Paper 2023/1501

Optimizing Space in Regev's Factoring Algorithm

Seyoon Ragavan, Massachusetts Institute of Technology
Vinod Vaikuntanathan, Massachusetts Institute of Technology
Abstract

We improve the space efficiency of Regev's quantum factoring algorithm [Reg23] while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. In contrast, Regev's circuit requires $O(n^{3/2})$ qubits, while Shor's circuit requires $O(n^2)$ gates. As with Regev, to factor an $n$-bit integer $N$, one runs this circuit independently $\approx \sqrt{n}$ times and apply Regev's classical post-processing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
factoringquantumShor's algorithm
Contact author(s)
sragavan @ csail mit edu
vinodv @ csail mit edu
History
2023-10-03: approved
2023-10-02: received
See all versions
Short URL
https://ia.cr/2023/1501
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1501,
      author = {Seyoon Ragavan and Vinod Vaikuntanathan},
      title = {Optimizing Space in Regev's Factoring Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1501},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1501}},
      url = {https://eprint.iacr.org/2023/1501}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.