Paper 2024/636

Regev Factoring Beyond Fibonacci: Optimizing Prefactors

Seyoon Ragavan, Massachusetts Institute of Technology
Abstract

In this note, we improve the space-efficient 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 space-efficient 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 qubits and multiplications of -bit integers. - A circuit that uses qubits and multiplications of -bit integers, for any . - A circuit that uses multiplications of -bit integers, and qubits, for any . In comparison, the original circuit by [Reg23] uses at least qubits and multiplications of -bit integers, while the space-efficient variant by [RV24] uses qubits and multiplications of -bit integers (although a very simple modification of their Fibonacci-based circuit uses qubits and only multiplications of -bit integers). The improvements proposed in this note take effect for sufficiently large values of ; it remains to be seen whether they can also provide benefits for practical problem sizes.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
factoringquantum algorithmsShor's algorithm
Contact author(s)
sragavan @ mit edu
History
2024-07-01: last of 2 revisions
2024-04-25: received
See all versions
Short URL
https://ia.cr/2024/636
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.