How many qubits could it take to break RSA-2048? A 2025 estimate

Short answer: A 2025 paper by Craig Gidney estimates that a 2048-bit RSA integer could be factored in under a week by a quantum computer with fewer than one million noisy qubits, down from a 2019 estimate of 20 million qubits and eight hours. It is a resource estimate under stated assumptions, not a prediction. No machine of that size exists.

How much has the required qubit count decreased?

In 2019, an estimate suggested that a quantum computer would need 20 million noisy qubits to factor a 2048-bit RSA integer within eight hours. The paper streamlines an algorithm proposed by Chevignard, Fouque and Schrottenloher to reduce this overhead. By optimizing the logical qubit requirements and improving the efficiency of the underlying arithmetic operations, the estimated physical qubit count drops to less than one million. The estimate suggests the resource requirement is lower than the 2019 figure, but it is still far beyond any machine that exists today.

What assumptions underpin this estimate?

The estimate relies on a specific set of physical and algorithmic assumptions that define the boundary of the calculation. The model assumes a square grid of qubits with nearest-neighbor connections, which dictates the topology of the quantum processor. It presumes a uniform gate error rate of 0.1%, a metric that determines how frequently operations fail and require correction. The surface code cycle time is assumed to be 1 microsecond, setting the pace at which error correction can be applied. Additionally, the control system reaction time is fixed at 10 microseconds, representing the latency in managing the quantum operations. These parameters are identical to those used in the 2019 estimate, ensuring that the reduction in qubit count is attributable to algorithmic and architectural improvements rather than optimistic assumptions about faster or more reliable hardware. If actual hardware deviates from these error rates or timing constraints, the required qubit count could differ. The estimate is therefore a conditional projection based on current theoretical limits of error correction performance.

How does approximate residue arithmetic reduce the cost?

The primary driver of the qubit count reduction is the use of approximate residue arithmetic. Previous methods required precise arithmetic operations that demanded high logical qubit overhead. By employing approximate techniques, the algorithm can perform the necessary modular multiplications and exponentiations with fewer logical qubits. This approach was originally proposed by Chevignard, Fouque, and Schrottenloher, and the recent work streamlines their algorithm to further minimize the Toffoli gate count. The Toffoli count is a critical metric because it determines the complexity of the circuit and the associated error correction overhead. By reducing the Toffoli count by more than a factor of 100, the physical resources required for the computation drop dramatically. This efficiency gain allows the algorithm to fit within a smaller physical footprint while maintaining the necessary accuracy for factoring large integers. The technique trades off some precision for significant resource savings, which is viable for the specific task of RSA factoring where exact intermediate results are not required until the final factorization step.

What other techniques contribute to the efficiency?

Beyond approximate residue arithmetic, two additional techniques contribute to the reduced qubit count. The first involves storing idle logical qubits using yoked surface codes. In many quantum algorithms, not all logical qubits are active at every step. Previously, these idle qubits still consumed physical resources. By using yoked surface codes, the physical overhead for storing these inactive qubits is minimized. The second technique involves allocating less space for certain operations, though the specific details of this allocation are part of the broader streamlining of the algorithm. These optimizations work in concert with the arithmetic improvements to lower the total physical qubit requirement. The combination of these methods allows the estimate to reach the sub-million threshold. It is important to note that these are theoretical optimizations; no quantum computer of this scale exists to validate the estimate in practice. The figures represent a research-stage projection of what is possible under idealized conditions, not a description of currently available technology.

FAQ

What does the 2025 paper estimate?

That a 2048-bit RSA integer could be factored in less than a week by a quantum computer with fewer than one million noisy qubits.

How does that compare with the 2019 estimate?

Gidney and Ekera estimated 20 million noisy qubits and eight hours in 2019. The new paper cuts the qubit count substantially but takes longer.

Are the hardware assumptions more optimistic this time?

The author says he makes the same assumptions as in 2019: a square grid with nearest-neighbour connections, a uniform gate error rate of 0.1%, a 1 microsecond surface code cycle and a 10 microsecond control system reaction time.

Where does the saving come from?

Mainly from approximate residue arithmetic, storing idle logical qubits with yoked surface codes, and allocating less space for certain operations. The paper also reports a Toffoli count reduced by more than 100 times.

Does this mean RSA-2048 can be broken now?

No. This is a theoretical estimate. No quantum computer of this size exists, and the estimate depends on the assumptions above.