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 $$ 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.