Streaming Regev's Quantum Factoring Algorithm
Abstract
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(n1.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(√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(√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.
Related
- Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups
- A Sharp Noise Threshold for Shor's Quantum Factoring and Discrete Log Algorithms
- Factoring six-digit integers with superconducting quantum circuits
- TandemQEC: Joint Provisioning of Streaming Quantum Error Correction in Tightly-Integrated Quantum-Classical Systems
- Streaming the partial-transpose moment hierarchy with order-independent quantum memory
BibTeX
@misc{kirk2026streaming,
title = {{Streaming Regev's Quantum Factoring Algorithm}},
author = {Katherine Van Kirk and Craig Gidney},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06733},
eprint = {2610.06733},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06733},
}
RIS
TY - UNPB
TI - Streaming Regev's Quantum Factoring Algorithm
AU - Katherine Van Kirk
AU - Craig Gidney
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06733
UR - https://arxiv.org/abs/2610.06733
AB - 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(√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(√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.
ER -