Breaking RSA: Resource Estimates
How many physical qubits and how much time, really?
"A quantum computer will break RSA" is a statement about asymptotics. Engineers need a bill of materials: how many physical qubits, at what error rate, for how long. The best published answer for 2048-bit RSA fell from about 20 million noisy qubits and 8 hours (2021) to under a million qubits and under a week (2025), on identical hardware assumptions. This lesson shows how such numbers are produced and how to read them.
What you’ll learn
- Describe the layers of a fault-tolerant resource estimate: algorithm, logical circuit, error-corrected layout, device model.
- Estimate the code distance and physical-qubit overhead from a logical error budget with a simple surface-code model.
- Summarize the Gidney–Ekerå (2021) and Gidney (2025) estimates for RSA-2048, their assumptions and the techniques behind them.
- Identify which assumptions dominate an estimate, and how far mid-2020s hardware is from them.
From O(L³) to a bill of materials
A resource estimate is a stack of translations. The algorithm fixes how the arithmetic is organized. Compiling it gives an abstract logical circuit, costed in logical qubits, Toffoli (or T) gates and measurement depth, the number of sequential rounds of measure, decode and react. An error-correction layout, here the surface code with lattice surgery and magic-state factories, turns this into a space-time volume of code patches. Finally a device model (error rate, cycle time, reaction time, connectivity) converts patches into physical qubits and seconds.
| Quantity | Formula for -bit RSA | |
|---|---|---|
| Logical qubits | ||
| Toffoli gates |
The 2021 construction combined several ideas, each attacking the dominant cost, modular exponentiation:
- Shorter exponent. Following Ekerå and Håstad, RSA factoring is recast as a short discrete logarithm (of a number about the size of , roughly bits), so fewer modular multiplications are needed than in plain order finding.
- Windowed arithmetic. Instead of one controlled multiplication per exponent bit, a quantum table lookup fetches a precomputed multiple for a whole window of exponent bits.
- Coset representation and oblivious carry runways. Approximate modular arithmetic that avoids expensive comparisons and lets long additions be split into parallel pieces.
- Semiclassical Fourier transform. The exponent register is processed a window at a time and measured immediately, so it never has to be stored in full.
Error-correction overhead: a back-of-the-envelope model
A distance- rotated surface-code patch uses data and measurement qubits, about in total. A common heuristic for its logical error rate per code cycle is
with the physical error rate. The estimates below assume , so : each increase of by 2 buys a factor of about 10.
The computation occupies roughly logical-qubit-cycles (thousands of logical qubits for about cycles of s, i.e. hours). To keep the total failure probability around 10% you need . With , which odd code distance is required?
Show the answer
27
means , so . Every factor of 10 in the error budget costs two more units of distance.
Physical qubits per logical qubit at .
Data patches alone, for the abstract circuit's logical qubits.
Add magic-state factories, routing space and buffers, and you land near the headline 20 million. This toy accounting is not the paper's detailed layout, but it shows where the number comes from.
If the Toffolis ran one after another, each waiting for one s decode-and-react cycle, the runtime would be about 7 hours. This sanity check suggests why the control system's reaction time, not just the s code cycle, sets the pace of such estimates.
From 20 million to under a million
| Quantity | Gidney & Ekerå (2021) | Gidney (2025) |
|---|---|---|
| Hardware assumptions | , s cycle, s reaction time, planar nearest-neighbor grid | identical |
| Physical qubits | about | fewer than |
| Runtime | about 8 hours | under a week |
| Key ideas | short-DL formulation, windowed arithmetic, coset representation, carry runways, surface code with distillation factories | approximate residue arithmetic (Chevignard, Fouque & Schrottenloher 2024), yoked surface codes for dense idle storage, magic-state cultivation |
The 2025 estimate trades time for space. The arithmetic works on compressed, approximate residues, so far fewer logical qubits are alive at once; idle logical qubits are stored more densely by adding an outer parity-check layer over surface-code patches (yoked codes); and magic states are grown cheaply in place (cultivation) instead of in large distillation factories. The runtime grows from hours to days, while the qubit count drops by more than an order of magnitude.
Reading estimates critically
Which assumptions matter most?
- Physical error rate. At , each factor of 10 in costs ; at it costs . Since the footprint scales as , operating close to threshold makes the overhead explode.
- Cycle and reaction times set the runtime more than the qubit count. Platforms whose error-correction cycles are, as of the mid-2020s, hundreds of microseconds to milliseconds (trapped ions, neutral atoms) would need much longer runs or more parallelism.
- Connectivity and codes. Long-range connectivity enables quantum LDPC codes with higher rate, such as the bivariate-bicycle codes (Bravyi et al. 2024), which could store logical qubits with several-fold fewer physical qubits than the surface code; turning that into a full factoring architecture is ongoing work.
- Algorithms. The 2019–2025 reductions came from better arithmetic and error-correction gadgets under fixed hardware assumptions.
As of the mid-2020s, the most advanced experiments operate surface-code memories just below threshold (for example a distance-7 memory on a superconducting processor, reported in 2024) on the order of a hundred physical qubits. The gap to about a million qubits at running for days is large, but it is an engineering gap, not a known physical barrier.
Keeping the algorithm fixed, which change most directly reduces the physical-qubit count of an estimate like Gidney–Ekerå's?
- Halving the surface-code cycle time
- Halving the reaction time
- Lowering the physical error rate further below threshold
- Adding more counting qubits
Show the answer
C. Lowering the physical error rate further below threshold
A smaller reaches the same at a smaller distance , and the footprint scales as per logical qubit. Cycle and reaction times mainly change the runtime.
Key takeaways
- Resource estimates stack algorithm, logical circuit (qubits, Toffolis, measurement depth), error-correction layout and device model (error rate, cycle time, reaction time, connectivity).
- The code distance is set by and the total space-time volume: must beat one over the volume, giving for RSA-2048 at and about physical qubits per logical qubit.
- Gidney–Ekerå (2021): about 20 million noisy qubits and 8 hours; Gidney (2025): under a million qubits and under a week, on identical assumptions. The gains came from algorithms and error-correction gadgets.
- These are model outputs, not measurements; mid-2020s hardware is far from the requirements. Mosca's inequality, not a prediction, motivates migrating now to the 2024 NIST post-quantum standards.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which assumptions underlie both the 2021 (about 20 million qubits, 8 hours) and the 2025 (under a million qubits, under a week) estimates for RSA-2048?
- Physical error rate with all-to-all connectivity
- Uniform physical error rate , s surface-code cycle, s reaction time, planar nearest-neighbor grid
- Neutral-atom hardware with millisecond cycles
- The 2025 estimate assumes ten times better hardware than the 2021 one
Show the answer
B. Uniform physical error rate , s surface-code cycle, s reaction time, planar nearest-neighbor grid
Both papers use the same device model, so the 20-fold qubit reduction comes from algorithms and error-correction gadgets, not from more optimistic hardware.
With and , going from to changes by
- a factor of 4
- a factor of 10
- a factor of 2
- a factor of 100
Show the answer
D. a factor of 100
The exponent grows from 13 to 15, so falls by .
Why does the required code distance depend on the size of the computation and not only on the physical error rate?
- Because the total failure probability is roughly times the space-time volume, so bigger computations need smaller
- Because larger computations raise the threshold
- Because each logical qubit needs its own decoder
- Because the number of counting qubits sets the distance
Show the answer
A. Because the total failure probability is roughly times the space-time volume, so bigger computations need smaller
With about logical-qubit-cycles, a 10% overall failure budget requires . A shorter computation tolerates a larger and a smaller .
Why can 256-bit elliptic-curve cryptography be attacked with fewer logical qubits than RSA-3072, although both offer about 128-bit classical security?
- Because elliptic curves are not abelian groups
- Because Shor's algorithm does not apply to RSA-3072
- Because quantum costs grow with key length, and elliptic-curve keys are short since only generic classical attacks are known for good curves
- Because point addition is cheaper than modular multiplication
Show the answer
C. Because quantum costs grow with key length, and elliptic-curve keys are short since only generic classical attacks are known for good curves
Roughly logical qubits for (2330) beat about for (about 6100). Each elliptic-curve operation is actually more expensive, but the key is twelve times shorter.
Further reading
- C. Gidney & M. Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", Quantum 5, 433 (2021).
- C. Gidney, "How to factor 2048 bit RSA integers with less than a million noisy qubits", preprint (2025).
- A. G. Fowler, M. Mariantoni, J. M. Martinis & A. N. Cleland, "Surface codes: Towards practical large-scale quantum computation", Phys. Rev. A 86, 032324 (2012).
- M. Roetteler, M. Naehrig, K. M. Svore & K. Lauter, "Quantum resource estimates for computing elliptic curve discrete logarithms", ASIACRYPT 2017.
- Google Quantum AI and collaborators, "Quantum error correction below the surface code threshold", Nature 638, 920 (2025).