79. Fault-Tolerant Algorithms
79.1Logical Gate Costs
The FTQ accounting unit: spacetime volume — physical qubits × time — consumed per logical operation. The price list (order-of-magnitude, surface-code era): Clifford logical gates via lattice surgery — hundreds-to-thousands of physical qubit-cycles, cheap; T gates — 10×–100× worse, magic-state-limited (79.3); logical measurement — cheap; logical memory — the standing cost of every idle qubit (Ch. 77.5's point: idling isn't free; a stored logical qubit spends cycles forever). The design consequence that rewires algorithmics: cost is no longer "how many gates" but "how many T gates, how much memory-time, how much traffic" — and algorithms optimize differently (T-count reduction, measurement-based strategies that trade T for memory, layout-aware synthesis). Ch. 46's fault-tolerant-compiler box was foreshadowing: compilation is the cost lever now.
79.2Surface-Code Overhead
The arithmetic every estimate starts from: a logical qubit with target logical error p_L needs code distance d ≈ (1/2)·log(p_L/p_phys)/log(Λ), and costs 2d² physical qubits (rotated surface code, data + ancilla) — so a 10⁻¹² logical error at p_phys=10⁻³, Λ=10 gives d≈7-9, ~100-150 physical qubits per logical, per operation window; algorithm-scale estimates (10⁻¹²–10⁻¹⁵ for long computations) push d=15–25, 500–1,200 physical per logical. Worked example to internalize: 100 logical qubits × 500 physical × (I/O overhead ~10×) ≈ 500,000 physical qubits — the Starling-class machine, for a small algorithm. The levers that move it: physical error rate (halving p_phys via better qubits beats any code trick), Λ (decoder quality — Ch. 37's work feeding directly into machine economics), and qubit-efficient codes (qLDPC — IBM's bet: encoding k logical in n physical with better rates than the surface code's 1-per-2d²; if qLDPC decoding matures, overheads drop 5–10× — the field's most consequential open engineering race).
79.3Magic-State Costs
The T-gate tax, precisely: Clifford+T universality means every non-Clifford operation consumes magic states — prepared ancillas (|T⟩ = T|+⟩) injected into the computation; they cannot be copied or cheaply made, only distilled: many noisy T-states → fewer better ones, via distillation circuits that are themselves the machine's biggest sub-computer. The numbers that shape everything: T distillation at useful error rates consumes 10³–10⁴ physical qubits per sustained T-gate-per-second — magic-state factories routinely occupy 50–90% of a fault-tolerant machine's footprint in resource estimates. The consequences: T-*count* is the algorithmic complexity metric (this is why qubitization and its 2010s descendants — Ch. 28.7 — mattered so much: they minimized T); T-*depth* and factory throughput set the machine's clock; and entire research programs (TOF-elimination, T-transparent protocols, cheaper distillation) exist purely to shave this tax. When a roadmap says "10⁶ qubits for chemistry," ask: how many are factories?
79.4Resource Estimation
The capstone skill — Ch. 28.9's whole-stack pipeline, now with FTQ's real constants: algorithm → logical circuit (T-count, T-depth, width, memory-time) → code parameters (d, overhead from 79.2) → factory sizing (T-rate needed vs. 79.3 cost) → routing/layout overhead (Ch. 46's traffic) → physical machine (qubits, cycle time, hours). The tools exist and are public: Microsoft's Azure Quantum Resource Estimator (the most usable), IBM/open-source RE frameworks — use them; hand-rolled estimates teach, tool-assisted ones publish. The discipline: every estimate is a scenario (state assumptions: p_phys, Λ, cycle time, algorithm version), never a single number; sensitivity analysis (which assumption moves the answer most — almost always p_phys and T-count) is the analysis; and estimates age — the canonical example: RSA-2048 factoring went from 20M noisy qubits (2019 Gidney–Ekerå era) to under 1M (2025 Gidney) on arithmetic and code improvements — a 20× swing in six years, all constants, no asymptotics. Estimation is a living craft.
79.5Algorithmic Practicality
The filter that separates FTQ-era winners from ornaments, applied to the canon: Shor (factoring 2048-bit: ~4×10³ logical, ~10¹⁰ T, hours-days on a 2030s-large machine — practical on the far side of the roadmap, and the reason PQC migration runs now); Grover (AES-key search: ~10³ logical but 2⁶⁴ sequential iterations = weeks-months of wall-clock — asymptotics fine, clock-speed-fragile; symmetric crypto survives in practice); chemistry/FeMoco-class (10²–10³ logical, 10⁹–10¹¹ T — the flagship application, cost-plausible on late-2030s machines, sensitivity analysis ongoing); QSVT/qubitization-era algorithms (the modern backbone — resource-optimized, T-lean); HHL (condition-number and precision caveats make most instantiations impractical — the cautionary tale); amplitude estimation for finance (Monte-Carlo √ speedup × 10⁶-shot costs = marginal economics — contested). The meta-lesson: practicality is three-sided — logical resources, wall-clock, and problem value — and the field's most useful reviewers (this is a real job — Ch. 60.9) hold all three at once.
79.6Million-Qubit-Scale Considerations
The systems engineering of machines that don't exist yet: cryogenics and I/O (a 10⁶-qubit superconducting machine needs ~10⁵-10⁶ coax lines or cryo-CMOS multiplexing — wiring is the wall before qubits are); control electronics (per-qubit waveform generation at scale — FPGA/ASIC economics, Ch. 60.6's field at industrial size); real-time decoding (10⁶ physical qubits at µs cycle = 10⁹+ syndrome bits/second to decode in real time — Ch. 37's problem multiplied to datacenter scale; decoder compute may exceed the quantum computer's footprint); calibration at scale (per-qubit tune-up doesn't human-scale — automated/ML calibration becomes mandatory infrastructure); yield and fabrication (10⁶ qubits at 99.9% gate fidelity means managing a 0.1% defect population — chip-scale binning strategies); and the compiler stack (scheduling 10⁹ logical operations across factories and memory — Ch. 46's research box, at operating-system scale; someone will write the FTQ era's first "quantum OS"). Every one of these is a software/systems problem wearing physics clothes — the career map of Part XVI drawn onto the 2030s.