Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the significant space complexity of Regev's quantum factoring algorithm by enabling qubit recycling, a technique previously thought incompatible. The authors achieve this by introducing superposition masking to eliminate uncomputation and by adapting phase estimation to use Fibonacci powers of unitaries, thereby avoiding costly encoding conversions. The resulting algorithm achieves a space complexity of $n+M(n)+O(\sqrt{n})$ qubits, a substantial reduction that makes Regev's algorithm more practical.
Regev's quantum factoring algorithm's qubit requirements are slashed by enabling streaming, making it significantly more practical than previously believed.
A major practical obstacle to Regev's factoring algorithm is its large space usage. In particular, the algorithm was believed to be incompatible with "qubit recycling," which streams the control qubits in phase estimation rather than storing them all simultaneously. We show how to fix this streaming problem. We build on the construction of Ragavan and Vaikuntanathan, which used Fibonacci accumulators to reduce the qubit count from $O(n^{1.5})$ to $11.32n$. We make two key improvements. First, we use superposition masking to prevent unwanted information from entering the accumulators, removing the need for uncomputation. Second, we show how to perform phase estimation using Fibonacci powers of a unitary operation rather than powers of two. This avoids various encoding conversions required by the construction of Ragavan and Vaikuntanathan. After these improvements, the phase-estimation qubits are used only once in the circuit, allowing them to be streamed. Our improvements reduce the space usage of Regev's factoring algorithm to $n+M(n)+O(\sqrt{n})$, where $M(n)$ is the space required for an in-place multiplication. For example, using the in-place multiplier of Luo et al. (2026), Regev's algorithm can factor an $n$-bit integer using $4n+O(\sqrt{n})$ qubits. Although our construction still falls short of the $n/2+εn$ qubits sufficient for leading implementations of Shor's algorithm, it is the lowest-space instantiation of Regev's algorithm to date and suggests that Regev's algorithm is still far from fully optimized.