Resource Estimation for Fault-Tolerant Algorithms
Raw qubit counts are weak evidence. This chapter turns a logical workload into numbers you can audit — logical qubits and depth, error-correction overhead, physical error rates, runtime — and then stress-tests the estimate by changing one assumption at a time.
A resource estimate is only as credible as its most sensitive assumption, so the sensitivity table matters more than the headline number.
By the end of this chapter you will be able to expand an algorithm's logical resource requirements into a physical-qubit and runtime budget, and to say which single assumption — overhead, error rate, or cycle time — dominates the conclusion.
Core concepts: resource estimation, logical qubits, circuit depth width.
From algorithm to hardware budget
A useful fault-tolerant estimate starts from the logical workload and expands outward through error-correction assumptions, physical error rates, cycle time, code distance, connectivity, and runtime targets. "How many qubits?" stops being a vibes question and becomes an auditable chain:
- the logical problem and its input size
- logical qubits required
- logical depth or gate counts
- target failure probability for the full run
- error-correction code and distance assumptions
- physical qubits per logical qubit
- runtime assumptions: cycle time and decoding reaction time
- sensitivity analysis over all of the above
Every link in that chain is a place where the estimate can be wrong — and a place diligence should dig.
The arithmetic that forces honesty
Two teaching formulas do most of the work. The overhead estimate: . The error budget: — every gate type multiplies the survival probability, so deep circuits need per-gate error rates that are exponentially better, not somewhat better.
Both models are simplifications. Their job is not accuracy; it is to force assumptions into the open where they can be argued with. Real estimates add code-specific overhead, magic-state factories, routing, and decoding, but they never escape the obligation to state assumptions explicitly.
Worked example: one assumption, triple the machine
Take a hypothetical workload of 100 logical qubits with a teaching overhead of 1,000 physical qubits per logical qubit. The estimate: roughly 100,000 physical qubits. Now change one assumption — the overhead rises to 3,000 per logical qubit because the target logical error rate tightened — and the same algorithm needs roughly 300,000 physical qubits.
Nothing about the algorithm changed. The estimate tripled because a reliability assumption did. That is the point of the exercise: the sensitivity tells you which assumption dominates diligence, and it is rarely the one in the press release.
Where estimates go wrong
The classic trap is comparing companies by raw physical qubit count. A device with more qubits is not closer to a fault-tolerant algorithm if its error rates, connectivity, control, and logical overhead are poor — it may just be a larger noisy system.
The second trap is treating a point estimate as a forecast. An estimate without sensitivity ranges, and without the conditions that would change the conclusion, is a number looking for confidence it has not earned.
The engineering view
Resource estimation is capacity planning under uncertainty — the same discipline as sizing a cloud deployment, except the failure modes include quantum error correction and analog control. The artifact should record:
- algorithm workload and logical resource model
- physical mapping assumptions
- the dominant sensitivity
- runtime estimate and validation path
- decision implication
Version the estimate like code: formula set, assumptions, data sources, date. An estimate is a snapshot, not a truth. When physical error rates improve or a compiler cuts logical depth, the estimate moves — which is why the sensitivity analysis outlives the headline number.
Separate the layers when numbers improve. An algorithmic change reduces logical depth. A hardware change reduces physical overhead. A better code changes the logical-to-physical mapping. Diligence should name which layer moved, because each carries a different evidence bar.
What this buys you in diligence
When a company reports a qubit number, ask what logical workload it enables. When a paper reports an algorithm, ask what physical assumptions would make it executable. Strong diligence connects both directions and checks that they meet in the middle.
The strongest claims show a path from today's evidence to the target workload: current physical metrics, required logical metrics, the scaling assumption, and proof gates along the way. If a step is missing, the honest response is usually monitor — not accept, not reject.
Exercise
Resource estimation sensitivity. Take one workload — your own or the book's resource-estimation lab — and change one assumption at a time.
- Record: logical qubits, physical-per-logical overhead, runtime assumption, target failure probability, and the resulting estimate.
- Check: the output is a sensitivity table, not a single number, and it names the dominant assumption explicitly.
- Submit: the table plus a decision — monitor, wait, build, partner, or avoid — justified from the dominant sensitivity.
- Repair: if your memo ranks opportunities by raw qubit count, rework it after Chapter 22 (Circuit Cost: Depth, Width, Gate Set, Connectivity), which builds the cost vocabulary this chapter assumes.
Check your understanding
Without notes: run a sensitivity analysis that varies physical-per-logical overhead across a factor of three and name the assumption that moves the conclusion most.
Oral defense: explain why two devices with identical physical qubit counts can be years apart in fault-tolerant usefulness.
If you get stuck
If your estimates cannot be reproduced, or your assumptions live only in your head, return to Chapter 41 (Noise Models and Noisy Simulation) for the rerun discipline, then Chapter 22 (Circuit Cost: Depth, Width, Gate Set, Connectivity) for the depth-and-width vocabulary the estimates are built from.