Quantum Computing · Quantum-Safe
Google Quantum AI halves the qubits needed by Regev’s factoring algorithm
A preprint by Van Kirk and Gidney brings Regev's factoring algorithm down to about 4n qubits for n-bit numbers. It stays above Shor's and changes no timelines.
Key points
- Van Kirk and Gidney, of Google Quantum AI, bring Regev's factoring algorithm down to about 4n qubits, half the best previous implementation.
- They do it by recycling the control qubits of phase estimation, something thought to be incompatible with this algorithm.
- It stays above the n/2 qubits of the best variants of Shor's algorithm and does not change the estimates for breaking RSA-2048.
Katherine Van Kirk and Craig Gidney, of Google Quantum AI, posted a preprint on arXiv on 5 October, not yet peer reviewed, that reduces the number of qubits needed by Regev’s factoring algorithm. With the best available multiplier, the algorithm can factor an n-bit number with about 4n qubits, plus lower-order terms. According to the authors, this is half the space required by the best previous implementation.
What Regev’s algorithm is and what its problem was
In 2023, Oded Regev presented a variant of Shor’s algorithm that moves the period-finding step from one dimension to several. It performs fewer quantum multiplications in each run, but needs more runs. The authors warn against a common misunderstanding: this does not mean it uses fewer gates in total than Shor’s algorithm, because the per-run advantage is offset by the larger number of runs.
Its main practical drawback was the number of qubits. Regev’s original version used on the order of n1.5; Ragavan and Vaikuntanathan brought it down to 11.32n in 2024. The best variants of Shor’s algorithm need about n/2.
What they have done
The saving comes from qubit recycling: in phase estimation, the control qubits are used, measured and reused, instead of all being held at once. Until now, Regev’s algorithm was thought not to allow this, because previous implementations went over those qubits several times. The authors solve it with two techniques: masking in superposition, which keeps unwanted information out of the accumulators, and phase estimation with Fibonacci powers instead of powers of two, which saves conversions between representations. As a result, each control qubit is used only once.
| Algorithm and implementation | Qubits (leading order) |
|---|---|
| Shor, Chevignard et al. (2025) | n/2 |
| Regev, original version | 3n1.5 |
| Regev, Ragavan and Vaikuntanathan (2024) | 11.32n |
| Regev, Ragavan (2024) | 10.43n |
| Regev, this work, with the “dialog” multiplier | 6.33n |
| Regev, this work, with the multiplier by Luo et al. | 4n |
The quantum part has not been run on any processor. What they have simulated is the phase estimation procedure, with 1,000 trials for each of 21 sizes, from 4 to 4,096 bits. It needs about six measurements per Fibonacci level, and 99.676% of the trials produced an accurate, certified estimate.
Note · what this work does not say
It does not make Regev’s algorithm better than Shor’s: the authors themselves acknowledge that it stays above the n/2 qubits of the best variants of Shor’s algorithm. The figures are circuit qubits; the work does not estimate physical qubits or run time. And, like Regev’s algorithm itself, it relies on an unproven number-theoretic conjecture.
What changes for decision-makers
On its own, nothing in migration timelines. The reference estimate for RSA-2048 is still the one Gidney himself published in May 2025 using Shor’s algorithm: fewer than a million noisy physical qubits.
What matters is the trend. The authors write that they see no fundamental obstacle to reducing the cost of Regev’s algorithm further, and that Shor’s algorithm has had decades of optimisation while Regev’s is only a few years old. For anyone planning, it is one more reason not to assume that the resources needed to break RSA will stay where they are.