Welcome to the resource topic for 2024/636
Title:
Regev Factoring Beyond Fibonacci: Optimizing Prefactors
Authors: Seyoon Ragavan
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 \approx 12.4n qubits and \approx 54.9n^{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 space-efficient variant by [RV24] uses \approx 10.32n qubits and \approx 138.3n^{1/2} multiplications of n-bit integers (although a very simple modification of their Fibonacci-based circuit uses \approx 11.32n qubits and only \approx 103.7n^{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.
ePrint: https://eprint.iacr.org/2024/636
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .