Paper 2024/636
Regev Factoring Beyond Fibonacci: Optimizing Prefactors
Abstract
In this note, we improve the spaceefficient variant of Regev's quantum factoring algorithm [Reg23] proposed by Ragavan and Vaikuntanathan [RV24] by constant factors in space and/or size. This allows us to bridge the significant gaps in concrete efficiency between the circuits by [Reg23] and [RV24]; [Reg23] uses far fewer gates, while [RV24] uses far fewer qubits. The main observation is that the spaceefficient quantum modular exponentiation technique by [RV24] can be modified to work with more general sequences of integers than the Fibonacci numbers. We parametrize this in terms of a linear recurrence relation, and through this formulation construct three different circuits for quantum factoring:  A circuit that uses $\approx 10.4n$ qubits and $\approx 45.7n^{1/2}$ multiplications of $n$bit integers.  A circuit that uses $(9+\epsilon)n$ qubits and $O_\epsilon(n^{1/2})$ multiplications of $n$bit integers, for any $\epsilon > 0$.  A circuit that uses $(24+\epsilon)n^{1/2}$ multiplications of $n$bit integers, and $O_\epsilon(n)$ qubits, for any $\epsilon > 0$. In comparison, the original circuit by [Reg23] uses at least $\approx 3n^{3/2}$ qubits and $\approx 6n^{1/2}$ multiplications of $n$bit integers, while the spaceefficient variant by [RV24] uses $\approx 10.32n$ qubits and $\approx 129.6n^{1/2}$ multiplications of $n$bit integers (although a very simple modification of their Fibonaccibased circuit uses $\approx 11.32n$ qubits and only $\approx 86.4n^{1/2}$ multiplications of $n$bit integers). The improvements proposed in this note take effect for sufficiently large values of $n$; it remains to be seen whether they can also provide benefits for practical problem sizes.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 factoringquantum algorithmsShor's algorithm
 Contact author(s)
 sragavan @ mit edu
 History
 20240701: last of 2 revisions
 20240425: received
 See all versions
 Short URL
 https://ia.cr/2024/636
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/636, author = {Seyoon Ragavan}, title = {Regev Factoring Beyond Fibonacci: Optimizing Prefactors}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/636}, year = {2024}, url = {https://eprint.iacr.org/2024/636} }