Paper 2024/636
Regev Factoring Beyond Fibonacci: Optimizing Prefactors
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
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
-
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} }