Regev Factoring Beyond Fibonacci: Optimizing Prefactors

ePrint Report: Regev Factoring Beyond Fibonacci: Optimizing Prefactors

Seyoon Ragavan

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 …

algorithm beyond bridge concrete efficiency eprint report factoring quantum report size space