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 and how many Toffoli or T gates 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 so that the total chance of any logical failure, about , stays below 1%, with and . (4) Footprint: about physical qubits per logical qubit in the surface code, plus magic-state factories. (5) Check against the assumptions. Established
Run the estimator
Physical error 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 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 to , 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.
And one to work out. With , and , what is ?
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.