Case Study: Reading a Resource Estimate — 20 Million Qubits for RSA-2048
Executive Summary
"Twenty million physical qubits, eight hours" is the number everyone quotes for breaking RSA-2048. Few people who quote it know what assumptions it rests on, which is unfortunate, because the assumptions are where the forecasting uncertainty lives — and where the number has moved most over the past decade.
This case study reconstructs the estimate from its components, identifies which parameter each conclusion is most sensitive to, and shows how the headline figure fell from a billion qubits to twenty million without any hardware improvement at all — purely through better algorithms and better error-correction accounting.
Skills applied
- Decomposing a fault-tolerant resource estimate into its layers (§15.14).
- Relating physical error rate to surface-code distance and overhead.
- Performing sensitivity analysis on a forecast.
- Distinguishing algorithmic progress from hardware progress in timeline predictions.
Phase 1: The layers
Any estimate of this kind stacks four layers, each multiplying the one below:
$$\text{Algorithm} \to \text{Logical circuit} \to \text{Error correction} \to \text{Physical hardware}$$
| Layer | Quantity | Value for RSA-2048 |
|---|---|---|
| Algorithm | Modular exponentiations | $2n = 4{,}096$ |
| Logical circuit | Logical qubits | ~6,200 |
| Toffoli / $T$ gates | ~$3\times10^{9}$ | |
| Error correction | Code distance $d$ | 27–31 |
| Physical per logical | ~$2d^2 \approx 1{,}500$–1,900 | |
| Physical | Total physical qubits | ~$2\times10^{7}$ |
| Runtime | ~8 hours |
Phase 2: The algorithmic layer
Shor needs $\sim 2n$ modular multiplications, each on $n$-bit numbers. Naively, an $n$-bit modular multiplication costs $O(n^2)$ Toffolis, giving $O(n^3) \approx 10^{10}$ for $n=2048$.
The estimate's first major saving comes from windowed arithmetic: precompute a table of partial products and look them up in superposition, trading qubits for gates. This cuts the Toffoli count by roughly 3–5× at the cost of extra logical qubits — and it is a purely classical algorithmic idea applied to a quantum circuit.
Sensitivity: the total is roughly linear in Toffoli count, so a 2× arithmetic improvement is a 2× reduction in runtime (or in factory area). This is where most future improvement is likely to come from.
Phase 3: The error-correction layer
This is where the largest multiplier sits, and where the estimate is most sensitive.
The surface code suppresses logical error as
$$p_L \approx A\left(\frac{p}{p_{\text{th}}}\right)^{\lfloor (d+1)/2 \rfloor}$$
with threshold $p_{\text{th}} \approx 10^{-2}$. The circuit has $\sim3\times10^{9}$ Toffolis, so we need $p_L \lesssim 10^{-10}$ per operation for the whole computation to succeed with reasonable probability.
| Physical error $p$ | $p/p_{\text{th}}$ | Required $d$ | Physical per logical ($2d^2$) |
|---|---|---|---|
| $10^{-2}$ | 1.0 | ∞ — at threshold, no suppression | — |
| $10^{-3}$ | 0.1 | ~27 | ~1,460 |
| $10^{-4}$ | 0.01 | ~13 | ~340 |
| $10^{-5}$ | 0.001 | ~9 | ~160 |
A 10× improvement in physical gate error reduces the qubit requirement by roughly 4×. This is the single highest-leverage hardware parameter, and it is why hardware roadmaps emphasize fidelity over qubit count — a point that the "race to more qubits" framing in the press gets backwards.
Phase 4: Magic states
Toffoli and $T$ gates are not transversal, so they consume distilled magic states (Chapter 9). At $3\times10^{9}$ Toffolis, magic-state production is the runtime bottleneck, and factories occupy the majority of the chip.
The estimate assumes: - Two-level distillation reaching $\sim10^{-11}$ error per state. - Factories running in parallel with the main computation. - Roughly half to two-thirds of all physical qubits dedicated to factories rather than to data.
Sensitivity: improved distillation protocols and magic-state cultivation techniques have repeatedly cut this cost. This is an active research area where a 2–5× improvement is plausible without any hardware change.
Phase 5: Why the number fell 50×
The headline has moved substantially, and tracing why is the most useful part of this exercise:
| Year | Estimate | What changed |
|---|---|---|
| ~2012 | ~1 billion physical qubits | Early surface-code accounting, naive arithmetic |
| ~2017 | ~230 million | Better distillation, improved layouts |
| 2019 (Gidney–Ekerå) | 20 million, 8 hours | Windowed arithmetic, oblivious carry runways, efficient factories |
| Later refinements | Single-digit millions in some models | Continued algorithmic and code improvements |
None of this reduction came from hardware. It came from better quantum algorithms for arithmetic, better error-correcting-code layouts, and better magic-state protocols.
The forecasting lesson. Timelines for cryptographically relevant quantum computing are usually discussed as a hardware question — how many qubits, by when. Historically, the algorithmic side has moved the number more than the hardware side. A forecast that tracks only qubit counts is tracking the slower-moving variable.
Phase 6: Using the estimate responsibly
What it supports: RSA-2048 requires error-corrected hardware roughly four to five orders of magnitude beyond today's, and that hardware does not exist or nearly exist.
What it does not support: a specific date. The estimate is conditional on physical error rate, code choice, arithmetic implementation, and distillation protocol — every one of which is moving.
How to use it in planning: as a lower bound on difficulty, not a schedule. The correct planning response remains Mosca's inequality (Chapter 1): compare your data lifetime plus migration time against a plausible range for the machine's arrival, and note that the decision is insensitive to the exact date for any long-lived secret.
What to monitor: published resource estimates and logical-qubit demonstrations, not physical qubit-count records. A device with 100,000 physical qubits at $10^{-3}$ error is further from breaking RSA than a device with 10,000 at $10^{-5}$.
Discussion Questions
- A 10× improvement in physical error rate cuts the qubit requirement ~4×. Derive that from the surface-code scaling.
- The estimate fell 50× with no hardware improvement. What does that imply for forecasts based on qubit-count extrapolation?
- Magic-state factories occupy most of the chip. What algorithmic change would most reduce total cost, and why?
- Would you rather have 10× more qubits or 10× better gate fidelity? Justify quantitatively.
Your Turn: Extensions
- Recompute the required code distance for $p = 3\times10^{-4}$ and a $10^{10}$-gate circuit.
- Estimate resources for RSA-1024 and for a 256-bit elliptic curve; explain why ECC likely falls first.
- Read the Gidney–Ekerå paper and identify which single optimization contributed most.
- Build a spreadsheet model with $p$, Toffoli count, and distillation efficiency as inputs, and run a sensitivity analysis.
Key Takeaways
- The 20-million-qubit figure is a stack of four layers, each with its own assumptions; quoting it without them is quoting a conclusion without its premises.
- Physical error rate is the highest-leverage hardware parameter: 10× better fidelity buys ~4× fewer qubits.
- Magic-state factories dominate area and runtime, making $T$/Toffoli count the metric that matters.
- The estimate fell ~50× from algorithmic and error-correction advances alone, not from hardware.
- Track logical qubits, gate fidelity, and published resource estimates — not physical qubit-count headlines.