36. Fault-Tolerant Quantum Computing
36.1Physical vs logical qubits
Keep two numbers in your head. Best physical two-qubit gates today: error rate ~10⁻³ (superconducting), ~10⁻⁴ (trapped ions, at slower speed). What algorithms need: logical error rates of 10⁻⁹ to 10⁻¹² per operation — factoring RSA-2048 or running deep chemistry circuits fails at anything looser. The gap is six to nine orders of magnitude, and no physical qubit roadmap closes it directly. Error correction closes it by spending qubit count: 2d² physical qubits per logical qubit at distance d, with d chosen so the logical error rate meets the algorithm's budget. The ratio of physical to logical qubits is the master cost metric of the industry, and every plot in every roadmap is ultimately about driving it down.
36.2Fault tolerance
Fault tolerance (fault tolerance) is a property of constructions, not of codes: a gadget (preparation, gate, or measurement on encoded data) is fault-tolerant when any single component fault produces at most one correctable error per code block. Without this discipline, a physical fault inside a logical gate propagates into a multi-qubit error that no distance-3 code can absorb, and correction becomes the source of failure. The definition has teeth because faults and errors differ: faults are physical events (a bad pulse, a stray photon); errors are Pauli operators on the encoded state. Fault-tolerant design bounds what one fault can do. This constraint — not the codes themselves — is what multiplies resource counts, and it is non-negotiable at every scale.
36.3Threshold theorem
The threshold theorem (Aharonov–Ben-Or, Kitaev, Knill–Laflamme–Zurek, 1996–1998) is the result that makes the field possible: if the physical error rate p is below a threshold p_th, and noise is local and weakly correlated, then arbitrarily long quantum computation is possible, with overhead growing only polylogarithmically in the target accuracy. It converts "quantum computing is physically impossible" into "quantum computing is an engineering budget". For the surface code, p_th ≈ 1% under idealized noise models and roughly 0.5–0.7% under realistic circuit-level noise — which is why the community's ~10⁻³ gate fidelities matter so much. The theorem's assumptions (locality, below-threshold operation at scale) are exactly what 2024–2025 experiments began testing on real hardware.
36.4Error propagation
Two-qubit gates spread errors, and the spreading is directional. Through CNOT, X on the control propagates to both qubits and Z on the target propagates to both: X⊗I → X⊗X, I⊗Z → Z⊗Z. Inside a syndrome-extraction circuit this creates hook errors: one ancilla fault, propagated through the check's four CNOTs, can flip a line of data qubits if the gate order is naive. Fault-tolerant constructions order each check's CNOTs so that a single propagated fault stays within the correctable weight. This is why real syndrome circuits look over-constrained and why copying a circuit diagram from a paper without its gate ordering silently destroys the code's distance. Error propagation analysis is a core skill of QEC engineers.
36.5Fault-tolerant gates
A transversal gate — one single-qubit gate per physical qubit, no interaction between qubits of the same block — is automatically fault-tolerant, since one fault stays on one qubit. The Steane code famously implements H, S, and CNOT (between blocks) transversally: a full fault-tolerant Clifford group. The surface code is stingier: CNOT between two aligned patches is transversal, H comes from lattice rotation, and S costs a round of patch deformation. The real workhorse is lattice surgery: merging and splitting patches of the code surface to induce logical measurements and CNOTs, spending space and time instead of extra structure. With these, all Clifford gates run on encoded data; the T gate does not — which forces 36.6.
36.6Magic states
The Eastin–Knill theorem (2009) forbids any code from having a universal transversal gate set, so non-Clifford gates must come from somewhere else. The answer is magic states (magic states): special resource states prepared and purified offline, consumed online. The canonical one is |T⟩ = T|+⟩ = (|0⟩ + e^(iπ/4)|1⟩)/√2. Injected through a gate-teleportation circuit built from Clifford operations and measurements, one copy implements one logical T gate on encoded data. The economics are brutal: algorithms consume T gates by the millions (Shor-scale circuits are T-gate dominated), each requiring a fresh high-quality state, and the state's infidelity must sit below the code's logical error rate or it poisons every computation it touches.
36.7Magic-state distillation
No physical process prepares |T⟩ well enough, so states are purified: distillation (distillation) consumes many noisy magic states and emits few clean ones. The Bravyi–Kitaev 15-to-1 protocol uses the [[15,1,3]] Reed–Muller code: fifteen input states, distillation circuits, one output with error squared; iterate to reach 10⁻¹². These distillation factories are typically the majority of a fault-tolerant machine's physical qubit budget. The 2024–2025 movement is aggressive cost reduction: cultivation — growing a T state inside a small surface-code patch, checking it, and discarding failures — plus new distillation protocols cut the per-T cost by roughly an order of magnitude. This is where much of the field's current resource-count progress comes from.
36.8Resource overhead
Concrete anchor: factoring RSA-2048. Gidney and Ekerå's 2019 estimate: ~20 million physical qubits running 8 hours. Gidney's 2025 revision: under 1 million qubits running about a week — a 20× overhead reduction from cheaper logical qubits, cultivation, and arithmetic reorganization, at surface-code distances in the mid-20s (so ~1,200+ physical qubits per logical qubit for memory). These numbers come from simulation, but from validated, open-source simulation (37.9), and their trajectory is the honest summary of the field's progress: the estimate keeps falling, it remains enormous, and every sub-quarter of it — codes, decoders, distillation, compilation (Part XII) — is an active engineering front with hiring behind it.
36.9Why fault tolerance is so expensive
Sum the costs. Qubit count: 2d² per logical qubit with d in the 20s–30s for serious algorithms. Factories: distillation and cultivation can consume the large majority of the machine. Time: every logical operation is interleaved with syndrome rounds, so the ~1 μs cycle time of superconducting hardware sets the wall clock; a week-long computation is ~10¹² rounds, each needing decode. I/O: every physical qubit wants its own control and readout line at millikelvin temperatures — wiring, not qubits, is often the harder systems problem. None of these is a single big fix; all are compounding constants. That is why "error-correction overhead" is named in Part I as the field's defining engineering problem, and why it hires.