143
Part Three · D · Error correction and fault tolerance

Resource estimation: from algorithm to physical qubits

How many qubits does it take to break RSA-2048? In 2012 the estimate was about a billion. In 2019 Craig Gidney and Martin Ekerå brought it to 20 million, running for 8 hours. In May 2025 Gidney brought it below one million, running for under a week. The hardware assumptions barely changed. The savings came from arithmetic, compilation and error-correction tricks, and you can trace every factor with a short chain of reasoning. Resource estimation is the skill of turning an algorithm into a bill of materials.

On the plate: a resource estimator. Its defaults are Gidney’s 2025 assumptions.

The pipeline

Five steps. (1) Logical counts: how many logical qubits QQ and how many Toffoli or T gates NTN_T the algorithm needs, after compilation (Chapter 142). (2) Run time: non-Clifford gates are sequential steps, each limited by the code cycle time times the distance, or by the reaction time needed to decode and choose the next operation. (3) Distance: choose dd so that the total chance of any logical failure, about Q×(rounds)×pL(d)Q\times(\text{rounds})\times p_L(d), stays below 1%, with pL(d)≈0.1 (p/pth)(d+1)/2p_L(d)\approx0.1\,(p/p_\text{th})^{(d+1)/2} and pth≈1%p_\text{th}\approx1\%. (4) Footprint: about 2(d+1)22(d+1)^2 physical qubits per logical qubit in the surface code, plus magic-state factories. (5) Check against the assumptions. Established

Run the estimator

Physical error p=p = 10^-3.0, cycle time 1.0 µs, reaction time 10 µs, logical qubits 1400, Toffolis 10^9.8, storage in or .

With Gidney’s assumptions (0.1% error, 1 µs cycle, 10 µs reaction, about 1,400 logical qubits and 6.5×1096.5\times10^9 Toffolis) and dense storage, this simple model gives distance 31, about 1.2 million physical qubits and 2–3 days. Gidney’s detailed design, with yoked surface codes for idle qubits and magic-state cultivation (Chapter 140), lands under a million qubits and under a week. Halve the error rate and the footprint drops by almost half; double it and it doubles. Established for the method; the model is deliberately simplified.

Where the savings came from, and chemistry

From 20 million (2019) to under one million (2025): approximate modular arithmetic, which tolerates rare errors in the factoring computation; storing idle qubits in denser yoked codes; replacing distillation factories with cultivation; and accepting a longer run time. Michael Beverland and colleagues at Microsoft published in 2022 a systematic framework, now the Azure Quantum Resource Estimator, applying the same pipeline to chemistry and materials. Their conclusion: practical quantum advantage needs on the order of a million physical qubits with error rates near 10−410^{-4} to 10−310^{-3}, and fast gates. FeMoco, the iron–molybdenum cofactor of nitrogenase (Part 5), needs a few thousand logical qubits and billions of Toffolis in the best published estimates. Alexander Dalzell and colleagues’ 2023 survey collects end-to-end costs for many applications. Established for the estimates; Speculative for when hardware will meet them.

What you now have

The five-step estimation pipeline, how distance follows from a failure budget, the footprint and run-time formulas, the sensitivity to physical error, cycle and reaction times, and the history of RSA estimates.

· · ·

Three questions to carry with you.

Why does the reaction time matter?tap
Each non-Clifford step waits for decoding and classical feed-forward before the next can begin.
How does the footprint scale with distance?tap
As about 2(d + 1)² physical qubits per surface-code logical qubit.
What cut the RSA estimate by 20×?tap
Better arithmetic and compilation, denser storage codes, and magic-state cultivation; hardware assumptions stayed similar.

And one to work out. With pL=0.1 (p/0.01)(d+1)/2p_L = 0.1\,(p/0.01)^{(d+1)/2}, p=10−3p = 10^{-3} and d=25d = 25, what is log⁡10pL\log_{10}p_L?

log₁₀ p_L =

Sources: C. Gidney and M. Ekerå, Quantum 5, 433 (2021). C. Gidney, arXiv:2505.15917 (2025). M. E. Beverland et al., arXiv:2211.07629 (2022). A. M. Dalzell et al., arXiv:2310.03011 (2023). J. Lee et al., PRX Quantum 2, 030305 (2021). Checked by code: the plate’s model gives d = 31, 1.21 million qubits and 2.3 days for the default inputs with dense storage.

Next · Chapter 144
Superconducting qubits and circuit QED

An electrical circuit you could see under a microscope behaves like a single atom. That discovery won the 2025 Nobel Prize.

Turn the page