Simple Algorithm
Quantum Computing · Rydberg State · 28 min

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.

QuantityFormula for nn-bit RSAn=2048n=2048
Logical qubits3n+0.002 nlg⁡n3n+0.002\,n\lg n≈6.2×103\approx6.2\times10^3
Toffoli gates0.3 n3+0.0005 n3lg⁡n0.3\,n^3+0.0005\,n^3\lg n≈2.6×109\approx2.6\times10^9
Abstract-circuit costs reported by Gidney & Ekerå (2021), before distillation, routing and error-correction overheads.

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 p+qp+q, roughly n/2n/2 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-dd rotated surface-code patch uses d2d^2 data and d2−1d^2-1 measurement qubits, about 2d22d^2 in total. A common heuristic for its logical error rate per code cycle is

pL≈A(ppth)(d+1)/2,A≈0.1,pth≈1%,p_L\approx A\left(\frac{p}{p_{\mathrm{th}}}\right)^{(d+1)/2},\qquad A\approx0.1,\quad p_{\mathrm{th}}\approx1\%,

with pp the physical error rate. The estimates below assume p=10−3p=10^{-3}, so p/pth≈0.1p/p_{\mathrm{th}}\approx0.1: each increase of dd by 2 buys a factor of about 10.

Predict before you look

The computation occupies roughly 101410^{14} logical-qubit-cycles (thousands of logical qubits for about 101010^{10} cycles of 1 μ1\,\mus, i.e. hours). To keep the total failure probability around 10% you need pL≈10−15p_L\approx10^{-15}. With pL≈0.1×10−(d+1)/2p_L\approx0.1\times10^{-(d+1)/2}, which odd code distance dd is required?

Show the answer

27

0.1×10−(d+1)/2=10−150.1\times10^{-(d+1)/2}=10^{-15} means (d+1)/2=14(d+1)/2=14, so d=27d=27. Every factor of 10 in the error budget costs two more units of distance.

DerivationFrom distance to qubits and hours (toy accounting)
  1. 2d2=2×272≈1.5×1032d^2=2\times27^2\approx1.5\times10^3

    Physical qubits per logical qubit at d=27d=27.

  2. 6.2×103×1.5×103≈9×1066.2\times10^3\times1.5\times10^3\approx9\times10^6

    Data patches alone, for the abstract circuit's logical qubits.

  3. ∼2×107\sim2\times10^7

    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.

  4. 2.6×109 Toffolis×10 μs≈2.6×104 s≈7 h2.6\times10^9\ \text{Toffolis}\times10\,\mu\mathrm{s}\approx2.6\times10^4\ \mathrm{s}\approx7\ \mathrm{h}

    If the Toffolis ran one after another, each waiting for one 10 μ10\,\mus 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 1 μ1\,\mus code cycle, sets the pace of such estimates.

From 20 million to under a million

QuantityGidney & Ekerå (2021)Gidney (2025)
Hardware assumptionsp=10−3p=10^{-3}, 1 μ1\,\mus cycle, 10 μ10\,\mus reaction time, planar nearest-neighbor grididentical
Physical qubitsabout 2×1072\times10^7fewer than 10610^6
Runtimeabout 8 hoursunder a week
Key ideasshort-DL formulation, windowed arithmetic, coset representation, carry runways, surface code with distillation factoriesapproximate 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 p/pth=0.1p/p_{\mathrm{th}}=0.1, each factor of 10 in pLp_L costs Δd=2\Delta d=2; at p/pth=0.5p/p_{\mathrm{th}}=0.5 it costs Δd≈6.6\Delta d\approx6.6. Since the footprint scales as d2d^2, 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 p=10−3p=10^{-3} running for days is large, but it is an engineering gap, not a known physical barrier.

Check your understanding

Keeping the algorithm fixed, which change most directly reduces the physical-qubit count of an estimate like Gidney–Ekerå's?

  1. Halving the surface-code cycle time
  2. Halving the reaction time
  3. Lowering the physical error rate further below threshold
  4. Adding more counting qubits
Show the answer

C. Lowering the physical error rate further below threshold

A smaller p/pthp/p_{\mathrm{th}} reaches the same pLp_L at a smaller distance dd, and the footprint scales as 2d22d^2 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 p/pthp/p_{\mathrm{th}} and the total space-time volume: pL≈0.1(p/pth)(d+1)/2p_L\approx0.1(p/p_{\mathrm{th}})^{(d+1)/2} must beat one over the volume, giving d≈27d\approx27 for RSA-2048 at p=10−3p=10^{-3} and about 2d22d^2 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.

Question 1

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?

  1. Physical error rate 10−410^{-4} with all-to-all connectivity
  2. Uniform physical error rate 10−310^{-3}, 1 μ1\,\mus surface-code cycle, 10 μ10\,\mus reaction time, planar nearest-neighbor grid
  3. Neutral-atom hardware with millisecond cycles
  4. The 2025 estimate assumes ten times better hardware than the 2021 one
Show the answer

B. Uniform physical error rate 10−310^{-3}, 1 μ1\,\mus surface-code cycle, 10 μ10\,\mus 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.

Question 2

With pL≈0.1 (p/pth)(d+1)/2p_L\approx0.1\,(p/p_{\mathrm{th}})^{(d+1)/2} and p/pth=0.1p/p_{\mathrm{th}}=0.1, going from d=25d=25 to d=29d=29 changes pLp_L by

  1. a factor of 4
  2. a factor of 10
  3. a factor of 2
  4. a factor of 100
Show the answer

D. a factor of 100

The exponent (d+1)/2(d+1)/2 grows from 13 to 15, so pLp_L falls by 0.12=10−20.1^2=10^{-2}.

Question 3

Why does the required code distance depend on the size of the computation and not only on the physical error rate?

  1. Because the total failure probability is roughly pLp_L times the space-time volume, so bigger computations need smaller pLp_L
  2. Because larger computations raise the threshold
  3. Because each logical qubit needs its own decoder
  4. Because the number of counting qubits sets the distance
Show the answer

A. Because the total failure probability is roughly pLp_L times the space-time volume, so bigger computations need smaller pLp_L

With about 101410^{14} logical-qubit-cycles, a 10% overall failure budget requires pL≈10−15p_L\approx10^{-15}. A shorter computation tolerates a larger pLp_L and a smaller dd.

Question 4

Why can 256-bit elliptic-curve cryptography be attacked with fewer logical qubits than RSA-3072, although both offer about 128-bit classical security?

  1. Because elliptic curves are not abelian groups
  2. Because Shor's algorithm does not apply to RSA-3072
  3. Because quantum costs grow with key length, and elliptic-curve keys are short since only generic r\sqrt r classical attacks are known for good curves
  4. 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 r\sqrt r classical attacks are known for good curves

Roughly 9n9n logical qubits for n=256n=256 (2330) beat about 2n2n for n=3072n=3072 (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).