REVIEW
Streaming Regev's Quantum Factoring Algorithm
Quantum Physics · Submitted 5 Oct 2026 · 166 references
Pith's verdict: Streaming construction, superposition masking, and the analytic probe bound are solid and genuinely new; the six-probes-per-level and constant-probability claims do not survive a union bound at RSA scale.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Regev's quantum factoring algorithm can be streamed: superposition masking and Fibonacci-power phase probes make its control qubits recyclable, cutting space to $n+M(n)+O(\sqrt{n})$ qubits.
The reading
What carries the argument
The load-bearing objects are three. First, the multiplicative-group mask $|M_N\rangle$, the uniform superposition over units mod $N$; because multiplication by any invertible element merely permutes its terms, a garbage register left in this state carries no information about the control and can be measured and discarded. Second, the ladder of traveling eigenstates $|\tilde u_\theta^{(k)}\rangle = \mathrm{Fib}^{-(k-1)}(|M_N\rangle|u_\theta\rangle)$, built by running the Ragavan–Vaikuntanathan Fibonacci accumulator update $|x\rangle|y\rangle\mapsto|y\rangle|xy \bmod N\rangle$ backward; one backward step moves between levels, and the Fibonacci conjugation identity $\mathrm{Fib}^r \,\mathrm{Mul}_p^{(Y)}\,\mathrm{Fib}^{-r} = \mathrm{Mul}_{p^{F_r}}^{(X)} \,\mathrm{Mul}_{p^{F_{r+1}}}^{(Y)}$ is what turns a single multiplication of the aggregated product $p(c)$ into the required phase $e^{2\pi i F_k\langle\theta,c\rangle}$. Third, the classical inverse problem, solved by an adaptive Bayesian estimator that keeps a polynomial-size weighted cell grid on the phase circle, adaptively chooses measurement bases to maximize information gain, and certifies an estimate once an arc of width $2\varepsilon_R$ carries posterior mass at least $1-\delta_{\mathrm{final}}$; this is what turns a transcript of noisy Fibonacci-phase observations into the $w\approx\theta$ that Regev's postprocessing needs.
Extended reading notes
Core claim
On the paper's own terms, the central claim is that Regev's high-dimensional factoring algorithm can be recast as iterative quantum phase estimation with streaming control qubits, overturning the working assumption that qubit recycling is incompatible with it. The construction maintains two persistent $n$-qubit accumulators and steps backward along a ladder of traveling eigenstates, using a superposition mask $|M_N\rangle$ to absorb the arithmetic garbage that previously forced uncomputation, and probing phases at Fibonacci exponents $F_k$ rather than powers of two so that no binary/Zeckendorf conversions are needed. The claimed consequence (Cor. 5.8 and 5.9) is that a balanced semiprime is factored with $n+M(n)+O(\sqrt{n})$ qubits, which becomes $4n+O(\sqrt{n})$ with the measurement-uncomputed in-place multiplier of Luo et al., the lowest-space instantiation of Regev's algorithm to date. The rigorous asymptotic probe count is $O(\sqrt{n}\log n)$ per run (Cor. 4.4); a simulated adaptive Bayesian estimator averages about six probes per Fibonacci level, corresponding to roughly $30.25\sqrt{n}$ in-place multiplications per run, a figure the paper flags as an empirical estimate.
Load-bearing premise
The load-bearing premise for the headline numbers is the simulator's claim that about six phase probes per Fibonacci level suffice with 99.676% certified accuracy: the adaptive Bayesian estimator was only tested on uniformly sampled phases and never on the real circuit's correlated, superposition-branch accumulator values, its certification can falsely certify at large error through a Fibonacci-structured aliasing failure that is characterized empirically rather than bounded analytically, and the rigorous $O(\sqrt{n}\log n)$-probe guarantee does not reach the six-per-level figure; the factoring guarantee also inherits Regev's Conjecture 2.1 on short lattice vectors, for which the paper cites an unconditional variant of a modified construction.
Editorial extensions
If this is right
- Regev's algorithm can now be run with roughly half the qubits of the previous best implementation: $4n+O(\sqrt{n})$ with the Luo et al. multiplier, versus $11.32n$ for Ragavan–Vaikuntanathan (b8, b9, b35).
- The entangled Gaussian exponent-register input state assumed throughout earlier Regev-variant work is unnecessary; fresh $d$-qubit $|+\rangle^{\otimes d}$ control registers produce the same dual-lattice sample distribution (b143, Prop. 5.6).
- For balanced semiprimes, using the cheap approximate mask $|R_N\rangle$ in place of the exact $|M_N\rangle$ changes the transcript distribution by total variation distance $O(2^{-n/4})$ per run, so the practical mask-preparation shortcut is safe (Cor. 5.8).
- A worst-case guarantee holds independently of the numerics: $O(\sqrt{n}\log n)$ simultaneous phase probes per Regev run, via the slow-refinement analytic estimator of Theorem 4.3 (Cor. 4.4).
Reading between the lines
- Because the total space is $n+M(n)+O(\sqrt{n})$, the next meaningful reduction in Regev's footprint is delegated to the in-place modular multiplication subroutine rather than to the factoring structure itself; each qubit saved in $M(n)$ buys a full qubit in the total.
- The paper's own Appendix C.3 shows large-error false certifications cluster at Fibonacci-structured branch displacements ($F_K\,\mathrm{dist}(w,\theta)$ within $10^{-6}$ relative of $F_j$ or $2F_j$ for 27 of 37 aliased misses), which suggests an analytic anti-aliasing criterion might replace the soft transition guard, converting an empirical failure mode into a provable bound.
- If the six-probes-per-level behavior survives coupling to the real circuit's correlated, superposition-branch accumulator values (an untested regime), the practical per-run cost settles near $30.25\sqrt{n}$ multiplications; the gap between that heuristic and the proven $O(\sqrt{n}\log n)$ is where further theoretical work should concentrate.
Original 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(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+\epsilon 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.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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+\epsilon 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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | A major practical obstacle to Regev's factoring algorithm is its large space usage. | background 0.97 | 0.06 | 0.03 | asserted 1.00 |
| s1 | 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. | background 0.75 | 0.05 | 0.03 | asserted 0.59 |
| s2 | We show how to fix this streaming problem. | contribution 1.00 | 0.90 | 0.28 | asserted 1.00 |
| s3 | 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$. | background 0.74 | 0.09 | 0.04 | asserted 0.98 |
| s4 | We make two key improvements. | contribution 0.95 | 0.61 | 0.03 | asserted 0.83 |
| s5 | First, we use superposition masking to prevent unwanted information from entering the accumulators, removing the need for uncomputation. | method 0.62 | 0.94 | 0.05 | asserted 1.00 |
| s6 | Second, we show how to perform phase estimation using Fibonacci powers of a unitary operation rather than powers of two. | contribution 0.50 | 0.94 | 0.05 | asserted 1.00 |
| s7 | This avoids various encoding conversions required by the construction of Ragavan and Vaikuntanathan. | method 0.80 | 0.66 | 0.03 | asserted 1.00 |
| s8 | After these improvements, the phase-estimation qubits are used only once in the circuit, allowing them to be streamed. | result 0.49 | 0.88 | 0.14 | asserted 1.00 |
| s9 | 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. | result 0.98 | 0.95 | 0.74 | asserted 1.00 |
| s10 | 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. | result 0.99 | 0.63 | 0.13 | asserted 0.62 |
| s11 | Although our construction still falls short of the $n/2+\epsilon 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. | interpretation 0.64 | 0.68 | 0.37 | asserted 0.59 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2610.06733 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.