Paper 2023/1501
Optimizing Space in Regev's Factoring Algorithm
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
-
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} }