Fault-Tolerant Architecture Design

A fault-tolerant architecture is the bridge between an algorithm written in perfect logical qubits and a machine whose every part — qubits, gates, measurements, resets, and even the classical control electronics — is noisy. The promise that makes the bridge buildable is the threshold theorem: if the physical error rate sits below a hardware-specific threshold, an arbitrarily long computation can be run to arbitrarily small error with an overhead that grows only polylogarithmically in the target. The catch is that "polylogarithmic" hides a large constant, and turning that theorem into a device is an engineering problem with four coupled budgets — code distance, magic-state distillation, ancilla routing, and classical decoding — that must be balanced at once. The dominant paradigm is the surface code: a topological stabilizer code on a 2D lattice with only nearest-neighbour weight-four checks, a circuit-level threshold near one percent, and a planar layout that superconducting, ion, and neutral-atom hardware can build. Its logical operations come from lattice surgery rather than fragile transversal gates, and — like every 2D topological code — it admits no transversal non-Clifford gate, so it must import its $T$ and Toffoli gates from magic-state factories. The result is a machine whose floorplan is dominated not by data qubits but by the distillation supply chain that feeds them. Resource estimation is the quantitative heart of the discipline: fix an error budget, count the logical qubits and $T$ -count of the compiled circuit, choose a distance so the per-operation error times the operation count stays under budget, then tile factories alongside the data and route ancillas between them. The figure of merit every choice competes to minimize is the space-time volume — physical qubits times physical clock cycles. This article assembles that pipeline from the threshold theorem, sizes a real machine end to end, and shows why the classical decoder is as much a part of the architecture as the qubits.

Key takeaways

Fault-tolerant architecture design maps an abstract quantum algorithm onto noisy hardware so the logical error rate falls exponentially in the code distance while the qubit, time, and control budgets stay finite.
The cornerstone is the threshold theorem: below a code-dependent threshold $p_{\mathrm{th}}$ , arbitrarily long computation succeeds with overhead only polylogarithmic in $1/\epsilon$ ; above it, adding redundancy makes things worse.
Surface-code machines dominate planning: a distance- $d$ patch costs $\sim 2d^2$ physical qubits and suppresses logical error as $p_L\sim A\,(p/p_{\mathrm{th}})^{\lfloor (d+1)/2\rfloor}$ , needing only 2D nearest-neighbour connectivity.
Clifford gates are cheap (lattice surgery and braiding), but the Eastin–Knill theorem forbids a transversal $T$ gate, so non-Clifford gates come from magic-state distillation — which usually dominates the qubit footprint and runtime.
The design juggles four coupled budgets: code distance (space versus error), distillation factories (space-time versus $T$ -count), routing buses (connectivity), and decoder latency (must keep pace with the syndrome clock).
Key idea: Below a hardware-specific threshold, error correction wins exponentially while overhead grows only polylogarithmically; the architect's job is to allocate the resulting finite space-time budget across distance, distillation, routing, and decoding so the total logical error stays below the algorithm's tolerance.

Where this lives today

Fault-tolerant architecture has crossed from theory into the defining benchmark of experimental quantum computing. The milestone every platform now chases is "going below threshold" — showing empirically that a larger code has a lower logical error rate. Google reached it convincingly in 2024: their Willow superconducting processor ran surface codes up to distance 7 and showed the logical error falling by a factor $\Lambda\approx2.14$ for each two-step increase in distance, the first clear exponential suppression in a real device, with real-time decoding inside the microsecond cycle. Neutral-atom arrays (Harvard, MIT, QuEra) have executed transversal logical operations across many code blocks at once, and trapped ions (Quantinuum) have run repeated error-correction cycles with high-fidelity gates. The open frontier is overhead. Full resource estimates for a useful algorithm — factoring a 2048-bit RSA key is the canonical yardstick — still land at millions of physical qubits running for hours, with the magic-state supply chain, not the data, dominating the count. Three programs attack it: high-rate quantum LDPC codes such as IBM's bivariate-bicycle "gross code," which pack many logical qubits into far fewer physical ones at the price of long-range connectivity and harder decoding; cheaper non-Clifford resources through magic-state cultivation and better distillation; and faster decoders — union-find, sparse blossom, and neural or belief-propagation matchers — that clear the syndrome stream without stalling the logical clock. Whichever mix wins, the architecture is a joint optimization of code, factory, routing, and decoder, exactly as the threshold theorem's polylogarithmic promise demands.

The physical picture

Think of a fault-tolerant computer as a factory with a strict defect budget. Each logical operation carries a tiny failure probability $p_L$ , and a computation with $N$ operations needs $N p_L\lesssim\epsilon$ . You buy reliability by spending physical qubits on code distance, but every extra qubit and cycle is itself a chance for a fault — so redundancy only pays once the physical rate is below threshold. Below $p_{\mathrm{th}}$ , adding distance suppresses errors exponentially; above it, adding distance adds more failure points than it corrects, and the machine gets worse the bigger you build it. Everything in architecture design is a consequence of being on the good side of that line and of spending the resulting margin wisely. The chip that results does not look like a register of qubits. It looks like a floorplan: blocks of data patches, large tracts of magic-state factories, and highways of ancilla qubits routing entanglement between them, all shadowed by a classical decoder that must clear the syndrome stream in real time. The first figure is that floorplan, and it carries the number that sets its scale — each logical patch costs about $2d^2$ physical qubits, and the factories that manufacture the non-Clifford resource routinely occupy as much of the die as the data they serve.

Figure

A surface-code machine floorplan: a data register of logical patches, each costing about 2d² physical qubits (d = 25 gives roughly 1250), an array of magic-state factories that manufacture T resources and often occupy as much area as the data, an ancilla routing bus that carries entanglement between them, and a classical decoder that must clear each syndrome round before the next arrives

Two asymmetries shape that floorplan. The first is between correctable and uncorrectable: a fault-tolerant gadget is engineered so a single physical fault produces at most one error per code block — the "one bad apple" principle — so a distance- $d$ code fails only when about $d/2$ independent faults conspire, a probability that scales as $p^{d/2}$ . The second is between Clifford and non-Clifford: Clifford operations are essentially free, but the Eastin–Knill no-go forbids any code from doing a universal set transversally, so the $T$ and Toffoli gates that make the machine universal must be distilled at great expense. The second figure shows the quantitative punchline that ties both asymmetries to hardware: the family of logical-error curves at increasing distance, all crossing at the threshold, with exponential suppression opening up only below it.

Figure

The threshold crossing that governs every architecture choice. Logical error per operation versus physical error rate p for code distances d = 15, 21, 27, all meeting at the circuit-level threshold p_th ≈ 1 percent. Below threshold a larger code wins exponentially — each two steps of distance multiply the logical error by about p over p_th — while above threshold a larger code is worse

The classical computer is not a peripheral — it is inside the architecture. Decoders must digest syndrome data faster than it is produced, or the undecoded backlog forces the logical clock to stall while physical errors accumulate past the code's correction capacity. Real designs co-optimize the quantum hardware with the latency and throughput of the classical control plane; a decoder a microsecond too slow can sink an otherwise sub-threshold device.

The core equations

The threshold theorem is cleanest in its concatenated form, where a small code is recursively used to build its own logical qubits. Each level of recursion squares the effective error, so once the physical rate is below threshold the logical error collapses doubly-exponentially in the number of levels.

\overline{\epsilon}(p)\ \le\ c\left(\frac{p}{p_{\mathrm{th}}}\right)^{2^{L}} \qquad (1)

where: $\overline{\epsilon}(p)$ — logical error per gate at the top level; $p$ — physical error per elementary fault location; $p_{\mathrm{th}}$ — accuracy threshold under the assumed noise model; $L$ — number of concatenation levels; $c$ — an $O(1)$ constant set by the number of fault locations in one gadget. Reading: the exponent $2^{L}$ is the signature of recursive simulation, and $p<p_{\mathrm{th}}$ is exactly the condition that raising $L$ helps rather than hurts. For a topological code the distance $d$ plays the role concatenation depth plays above: the logical error per cycle is set by how many independent faults it takes to fool the decoder, roughly $d/2$ .

p_L\ \approx\ A\left(\frac{p}{p_{\mathrm{th}}}\right)^{\lfloor (d+1)/2\rfloor} \qquad (2)

where: $p_L$ — logical error per code cycle; $d$ — code distance (minimum logical-operator weight); $A$ — an $O(1)$ prefactor, weakly $d$ -dependent; $\lfloor (d+1)/2\rfloor\approx d/2$ — the minimum number of faults that cause an undetected logical error. Reading: below threshold each increase of $d$ by two multiplies $p_L$ by about $p/p_{\mathrm{th}}$ , so distance buys suppression cheaply. The price of that distance is quadratic in qubits, because a distance- $d$ surface-code patch is a two-dimensional sheet of data and measure qubits.

n\ =\ 2d^{2}-2d+1\ \sim\ 2d^{2} \qquad (3)

where: $n$ — physical qubits (data plus measure) in one distance- $d$ planar patch; the rotated layout uses $d^2$ data plus $d^2-1$ ancilla qubits, likewise $\sim 2d^2$ . Reading: this quadratic cost per logical qubit is why lowering the required distance, or switching to a higher-rate code, is the biggest lever on total footprint. Combining the budget $N_{\mathrm{op}}p_L\le\epsilon$ with the scaling of equation (2) and solving for $d$ gives the master sizing formula of the whole field.

d\ \gtrsim\ \frac{2\,\ln\!\big(A\,N_{\mathrm{op}}/\epsilon\big)}{\ln\!\big(p_{\mathrm{th}}/p\big)} \qquad (4)

where: $N_{\mathrm{op}}$ — total number of logical operations (space-time volume in code cycles); $\epsilon$ — target total failure probability for the whole computation; $d$ — minimum distance meeting the budget. Reading: $d$ grows only logarithmically in $N_{\mathrm{op}}/\epsilon$ — the polylog overhead of the threshold theorem made concrete. The reason universality is expensive is a hard no-go theorem. The set of logical gates a code can perform transversally — the safe kind that cannot spread errors within a block — is always a finite group, and a finite group cannot be dense in the unitaries.

\mathcal{T}=\{\bar U:\bar U\ \text{transversal and logical}\}\ \Rightarrow\ |\mathcal{T}|<\infty\ \Rightarrow\ \mathcal{T}\ \text{not universal} \qquad (5)

where: $\bar U$ — a transversal logical gate, a tensor product $u_1\otimes\cdots\otimes u_n$ acting qubit-by-qubit; $\mathcal{T}$ — the group of all such gates for a code detecting single-qubit errors. Reading: this is Eastin–Knill; for the surface code $\mathcal{T}$ is Clifford, so the missing non-Clifford gate must come from outside — from distillation, code switching, or gauge fixing. The standard workaround is to distill the non-Clifford resource. The Bravyi–Kitaev 15-to-1 protocol consumes fifteen noisy magic states and outputs one whose error is cubically suppressed.

p_{\mathrm{out}}\ \approx\ 35\,p_{\mathrm{in}}^{3}\qquad(\text{15-to-1 } T\text{ distillation}) \qquad (6)

where: $p_{\mathrm{in}}$ — per-input magic-state error; $p_{\mathrm{out}}$ — output error after one round. Reading: cubic suppression means a couple of rounds take $p_{\mathrm{in}}\sim10^{-3}$ far below any realistic data-qubit $p_L$ , but each round costs qubits and time — the origin of the factory blocks on the floorplan. The figure of merit that all these choices trade against is the space-time volume: the total physical resource a computation consumes.

V\ =\ n_{\mathrm{phys}}\times T_{\mathrm{cycles}} \qquad (7)

where: $V$ — total cost in qubit-rounds; $n_{\mathrm{phys}}$ — all physical qubits including data, ancilla, factories, and routing; $T_{\mathrm{cycles}}$ — number of physical syndrome-extraction cycles to completion. Reading: block codes versus surface codes, distillation versus cultivation, braiding versus lattice surgery — every architectural contest is a fight to minimize this single product. Finally, the decoder imposes a real-time constraint that is easy to forget and fatal to ignore. Syndrome data arrives once per physical cycle, and the decoder must keep up on average or the backlog grows without bound.

t_{\mathrm{dec}}\ \lesssim\ \tau_{\mathrm{cycle}}\qquad(\text{per syndrome round, to avoid backlog}) \qquad (8)

where: $t_{\mathrm{dec}}$ — decoder processing time per round of syndrome data; $\tau_{\mathrm{cycle}}$ — physical measurement cycle time (about $1\ \mu\mathrm{s}$ for superconducting qubits). Reading: throughput, not just accuracy, is a hard design constraint — a slow optimal decoder can be worse than a fast approximate one.

Derivation AThe existence of an error threshold from recursive simulation

The goal is to show that fault tolerance is possible at all: if each logical gadget is built so a single physical fault is always caught, then recursively encoding the machine in itself drives the logical error toward zero for any physical rate below a finite, code-determined threshold, at a cost only polylogarithmic in the target. We model one logical gate as a gadget with $c$ fault locations, count how it fails, define the threshold as the fixed point of the resulting recursion, and read off the overhead.

Step 1. Model a level-1 logical gate as a gadget containing $c$ elementary locations (gates, preparations, measurements, idle steps), each failing independently with probability $p$ . Fault-tolerant design guarantees any single fault is detected and corrected, so the gadget fails only when two or more locations fail: $\overline{\epsilon}_1\le\binom{c}{2}p^2\le c^2p^2$ . Why: the whole point of a fault-tolerant gadget is to convert first-order failure into second-order failure, which is what makes recursion converge.

Step 2. Rewrite the bound as $\overline{\epsilon}_1\le (cp)^2 = p_{\mathrm{th}}(p/p_{\mathrm{th}})^2$ with the definition $p_{\mathrm{th}}=1/c$ . Then the rescaled error obeys $\overline{\epsilon}_1/p_{\mathrm{th}}=(p/p_{\mathrm{th}})^2$ , which is smaller than $p/p_{\mathrm{th}}$ if and only if $p<p_{\mathrm{th}}$ . Why: this is the crossover — below the threshold one level of encoding already lowers the effective error, above it the encoding amplifies it, and the sign of that comparison is the entire content of "threshold".

Step 3. Recurse. Treat each level-1 logical gate as the physical gate of a level-2 gadget; the same argument squares the rescaled error at every level, $\overline{\epsilon}_{k+1}/p_{\mathrm{th}}=(\overline{\epsilon}_k/p_{\mathrm{th}})^2$ , so after $L$ levels $\overline{\epsilon}_L/p_{\mathrm{th}}=(p/p_{\mathrm{th}})^{2^{L}}$ . Why: iterating a squaring map gives doubly-exponential decay, which is why finitely many levels reach astronomically small logical error once you are below threshold.

Step 4. Count the cost. To reach a target $\overline{\epsilon}$ we need $2^{L}\sim\ln(1/\overline{\epsilon})/\ln(p_{\mathrm{th}}/p)$ , hence $L\sim\log\log(1/\overline{\epsilon})$ , and each level multiplies the qubit count by a constant, so the overhead is $\sim c^{L}\sim\mathrm{polylog}(1/\overline{\epsilon})$ . Why: this polylogarithmic overhead is the celebrated efficiency of fault tolerance — arbitrarily reliable computation for a merely polylogarithmic price. *Note: the $p_{\mathrm{th}}=1/c$ form is schematic — real thresholds come from an optimized count of correlated faults rather than this leading-order bound.*

Go deeper · Derivation B · 1 minSizing the code distance from an error budget

Derivation BSizing the code distance from an error budget

The goal is to turn a compiled algorithm into a concrete machine size: given the number of logical operations and the target failure probability, derive the code distance that just meets the budget, show it grows only logarithmically in the demand, and convert it to a physical-qubit footprint. We start from a union bound over operations, insert the surface-code error scaling, solve for $d$ , and evaluate it on a representative large computation.

Step 1. Bound the total failure by a union bound: with $N_{\mathrm{op}}$ logical operations each failing with probability $p_L$ , the whole computation fails with probability at most $N_{\mathrm{op}}\,p_L$ , and we demand $N_{\mathrm{op}}\,p_L\le\epsilon$ . Why: correctness of the whole circuit means no operation fails, so the budget is naturally additive in the per-operation error.

Step 2. Insert the scaling $p_L\approx A(p/p_{\mathrm{th}})^{d/2}$ from equation (2), giving $N_{\mathrm{op}}\,A\,(p/p_{\mathrm{th}})^{d/2}\le\epsilon$ , then take logarithms: $\tfrac{d}{2}\ln(p_{\mathrm{th}}/p)\ge\ln(A\,N_{\mathrm{op}}/\epsilon)$ , i.e. $d\gtrsim 2\ln(A N_{\mathrm{op}}/\epsilon)/\ln(p_{\mathrm{th}}/p)$ . Why: the logarithm on the right is the key — the required distance grows only logarithmically in the demand $N_{\mathrm{op}}/\epsilon$ , which is the polylog overhead of the threshold theorem made quantitative.

Step 3. Evaluate it. Take $N_{\mathrm{op}}=10^{10}$ , $\epsilon=10^{-3}$ , $A=0.1$ , and $p/p_{\mathrm{th}}=0.1$ . Then $(0.1)^{d/2}\le\epsilon/(A N_{\mathrm{op}})=10^{-3}/10^{9}=10^{-12}$ , so $d/2\ge12$ and $d\gtrsim24$ . Why: a ten-billion-operation computation at part-per-thousand hardware needs a distance in the mid-twenties, not the thousands — the logarithm keeps the price sane.

Step 4. Convert to qubits. Each logical qubit then costs $\sim 2d^2=2(24)^2\approx 1150$ physical qubits, before any factories or routing. Why: the quadratic-in- $d$ patch cost is the multiplier that turns a modest distance into hundreds of physical qubits per logical qubit, and it is why the data register alone reaches $10^5$ – $10^6$ qubits for a useful algorithm. *Note: the numbers here are illustrative order-of-magnitude estimates, and the prefactor $A\approx0.1$ is a standard fitted value, not a universal constant.*

Go deeper · Derivation C · 2 minWhy a magic-state supply chain is unavoidable

Derivation CWhy a magic-state supply chain is unavoidable

The goal is to explain the single most consequential fact about a surface-code floorplan: a large fraction of the chip manufactures non-Clifford gates rather than computing. We show that no code supplies a universal gate set transversally, that the surface code's cheap gates are therefore exactly the classically simulable Clifford group, and that closing the gap to universality forces a distillation supply chain whose throughput must match the algorithm's non-Clifford demand.

Step 1. Establish the no-go. Transversal logical gates $\bar U=u_1\otimes\cdots\otimes u_n$ are the safe ones — a single-qubit fault cannot spread within a block — and Eastin–Knill prove that for any code detecting single-qubit errors the group $\mathcal{T}$ of such gates is finite. A finite group cannot be dense in $SU(2^k)$ , so transversality alone can never be universal. Why: this converts "we want cheap universal gates" into a proven impossibility, forcing every architecture to pay somewhere else for its non-Clifford gates.

Step 2. Identify what is cheap. For the surface code the locally implementable and lattice-surgery gates generate exactly the Clifford group, which by the Gottesman–Knill theorem is efficiently simulable classically — so a Clifford-only machine is not even quantum-advantageous. The missing ingredient is a single non-Clifford gate, conventionally the $T$ gate. Why: this pinpoints the gap precisely — everything is free except the one gate that makes the computer worth building.

Step 3. Import the gate by distillation and teleportation. Prepare many noisy copies of the magic state $|T\rangle=(|0\rangle+e^{i\pi/4}|1\rangle)/\sqrt2$ , run 15-to-1 distillation so $p_{\mathrm{out}}\approx35\,p_{\mathrm{in}}^3$ , and consume the purified state by gate teleportation to enact a $T$ on the data. Demand $p_{\mathrm{out}}\le p_L$ : starting at $p_{\mathrm{in}}=10^{-3}$ , one round gives $35(10^{-3})^3\approx3.5\times10^{-8}$ and two rounds reach $\approx1.5\times10^{-21}$ , below any realistic data $p_L$ . Why: cubic suppression per round means the fidelity problem is solved in one or two rounds, so the real cost is spatial and temporal, not a matter of principle.

Step 4. Size the supply chain. Each factory occupies $\sim10^4$ – $10^5$ physical qubits and produces one distilled state every several code cycles; the number of factories is fixed by matching aggregate $T$ -production to the algorithm's $T$ -consumption rate, typically a few to a few dozen running in parallel. Why: because factories are large and must be pipelined to feed the data, the magic-state supply chain frequently occupies as much of the die as the computation itself — the dominant lesson of the whole floorplan.

Limiting cases

The threshold is not one number — it is a family of numbers, one per noise model, and architecture trade-offs live in the gap between the optimistic and the honest ones.

Case	Result	Meaning
Code-capacity noise (data errors only)	$p_{\mathrm{th}}^{\mathrm{surf}}\approx 0.109$	Idealized i.i.d. bit/phase flips with perfect syndrome extraction; equals the 2D random-bond Ising Nishimori point. An optimistic upper bound, unreachable on hardware.
Phenomenological noise (noisy measurements)	$p_{\mathrm{th}}^{\mathrm{surf}}\approx 0.029$	Data plus measurement errors over $d$ rounds, a 3D matching problem; still omits gate-level error propagation.
Circuit-level noise (every operation faulty)	$p_{\mathrm{th}}^{\mathrm{surf}}\approx 0.005\text{–}0.01$	Faults on every gate, prep, measurement, and idle location — the realistic figure that sets hardware fidelity targets near or below $10^{-3}$ .
Concatenated codes (Steane, Bacon–Shor)	$p_{\mathrm{th}}\sim 10^{-4}\text{–}10^{-2}$	Strongly construction- and model-dependent; provable thresholds are low, but optimized concatenations can compete at the cost of long-range gates.
High-rate qLDPC codes	encoding rate $k/n$ up to $\sim 1/10$	Far lower qubit overhead than the surface code's $\sim 2d^2$ per logical qubit, but they demand long-range connectivity and harder Tanner-graph decoding.

Common trapThe threshold is one universal number that guarantees a small error rate

It is neither universal nor a guarantee of smallness. First, "the threshold" depends drastically on the noise model: the surface code's code-capacity figure is about $10.9\%$ , but the honest circuit-level number, charging errors to every gate and faulty measurement, is roughly ten times smaller, near $1\%$ . Quoting the optimistic figure as if it governed a real device understates the required physical fidelity by an order of magnitude. Second, being below threshold only fixes the sign of the trend — bigger codes help — it says nothing about how small $p_L$ actually is at a given size. Reaching an algorithm-grade $10^{-12}$ to $10^{-15}$ at a physical rate of $10^{-3}$ still demands distances in the mid-twenties and therefore over a thousand physical qubits per logical qubit, before a single magic-state factory is built. "Below threshold" is a licence to scale, not a finished computer.

Worked examples

1 · What one step of distance buys (confidence builder)

A superconducting chip runs at $p/p_{\mathrm{th}}=0.1$ (that is, $p=10^{-3}$ , $p_{\mathrm{th}}=10^{-2}$ ) with fitted prefactor $A=0.1$ . Compute the logical error per cycle and the patch cost at distances $d=15,17,19$ , and say what each two-step increase buys.

Step 1. Use $p_L\approx A(p/p_{\mathrm{th}})^{\lfloor(d+1)/2\rfloor}=0.1\,(0.1)^{\lfloor(d+1)/2\rfloor}$ . For $d=15$ the exponent is $\lfloor16/2\rfloor=8$ , so $p_L=0.1\times(0.1)^{8}=\mathbf{10^{-9}}$ .

Step 2. For $d=17$ the exponent is $9$ : $p_L=0.1\times(0.1)^{9}=\mathbf{10^{-10}}$ . For $d=19$ the exponent is $10$ : $p_L=0.1\times(0.1)^{10}=\mathbf{10^{-11}}$ . Each increase of $d$ by two lowers the logical error by exactly the factor $p/p_{\mathrm{th}}=0.1$ — one decade per two rows of the lattice.

Step 3. The cost of those decades is quadratic but gentle: $2d^2$ gives $\mathbf{450}$ physical qubits at $d=15$ , $\mathbf{578}$ at $d=17$ , and $\mathbf{722}$ at $d=19$ . Two extra decades of reliability (10⁻⁹ → 10⁻¹¹) cost only about 270 extra qubits per logical qubit — the exponential-in-d payoff that makes the surface code practical.

2 · A full resource estimate for an algorithm (fully worked)

A compiled algorithm needs $Q=100$ logical qubits and $N_T=10^{8}$ logical $T$ -gates, run to total failure probability $\epsilon=10^{-2}$ on hardware with $p=10^{-3}$ and circuit-level $p_{\mathrm{th}}=10^{-2}$ (so $p/p_{\mathrm{th}}=0.1$ , $A=0.1$ ). Find the code distance, the data footprint, and the distillation requirement.

Step 1. Count logical operations. A $T$ via lattice surgery takes about $d$ cycles and touches the working register, so the space-time operation count scales as $N_{\mathrm{op}}\approx Q\,d\,N_T$ . This couples the budget to the very distance we are solving for, so we iterate.

Step 2. Impose the budget $N_{\mathrm{op}}\,A\,(p/p_{\mathrm{th}})^{\lfloor(d+1)/2\rfloor}\le\epsilon$ . Testing odd distances: at $d=23$ , $N_{\mathrm{op}}=100\cdot23\cdot10^{8}=2.3\times10^{11}$ and the left side is $2.3\times10^{11}\cdot0.1\cdot(0.1)^{12}=2.3\times10^{-2}$ , which exceeds $10^{-2}$ — too small a code.

Step 3. Step up to $d=25$ : $N_{\mathrm{op}}=100\cdot25\cdot10^{8}=2.5\times10^{11}$ and the left side is $2.5\times10^{11}\cdot0.1\cdot(0.1)^{13}=2.5\times10^{-3}\le10^{-2}$ . So the minimum distance is $\mathbf{d=25}$ , with a per-cycle data logical error of $p_L\approx0.1\,(0.1)^{13}=\mathbf{10^{-14}}$ .

Step 4. Size the data register: $2d^2\,Q=2\cdot625\cdot100=\mathbf{1.25\times10^{5}}$ physical qubits.

Step 5. Size the factories. The distilled $T$ states must match the data, $p_{\mathrm{out}}\le p_L\approx10^{-14}$ . From $p_{\mathrm{in}}=10^{-3}$ , one 15-to-1 round gives $35(10^{-3})^3\approx3.5\times10^{-8}$ — not enough — but a second round gives $35(3.5\times10^{-8})^3\approx1.5\times10^{-21}$ , comfortably below $10^{-14}$ . So two rounds of 15-to-1 distillation suffice, and a handful of parallel factories at ~10⁴–10⁵ qubits each brings the total to a few ×10⁵ physical qubits — with the magic-state supply chain rivalling or exceeding the 1.25×10⁵-qubit data register, the defining lesson of architecture design.

Physics of the portrait

Fault-tolerant architecture design has one unmistakable origin point: the moment Peter Shor showed that quantum information could be protected at all, and then that it could be computed on while protected.

Origins · 1 minPeter Shor and how this was discovered

Peter Shor

born 1959 · quantum error correction and fault tolerance

Peter Shor is an American mathematician, now at MIT, whose two mid-1990s results created both the promise and the problem this article addresses. In 1994 his factoring algorithm made large-scale quantum computation worth wanting; the immediate objection was that a quantum state is too fragile to survive a long computation, and decoherence would wash out any answer. In 1995 Shor answered it with the first quantum error-correcting code — nine physical qubits protecting one logical qubit against an arbitrary single-qubit error — overturning the widespread belief that the no-cloning theorem forbade redundancy in the quantum setting. The deeper move came in 1996, when he showed how to compute on encoded data without ever decoding it, introducing fault-tolerant gate constructions, fault-tolerant syndrome measurement with verified ancillas, and the "one bad apple" discipline that keeps a single fault from cascading. Together with Steane's parallel work and the CSS construction, this set the stage for the threshold theorem — proved soon after by Aharonov and Ben-Or, by Kitaev, and by Knill, Laflamme, and Zurek — which established that arbitrarily reliable computation is possible below a finite error rate with only polylogarithmic overhead. Everything an architect does today, from choosing a distance to tiling factories, is an exercise in spending the margin those theorems opened. Kitaev's topological codes later gave the geometry, and Fowler and collaborators the concrete blueprint, but the conceptual foundation — that fault tolerance is achievable, not merely desirable — is Shor's.

History

1994

— Shor's factoring algorithm makes large-scale quantum computation worth building

1995

— Shor's nine-qubit code, the first quantum error-correcting code

1996

— Shor and Steane give the first fault-tolerant gate and syndrome constructions

1997

— the threshold theorem is proved (Aharonov–Ben-Or, Kitaev, Knill–Laflamme–Zurek)

2012

— Fowler, Mariantoni, Martinis and Cleland give the practical surface-code architecture

2024

— Google's Willow chip demonstrates below-threshold surface-code operation to distance 7

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, Ch. 10 (fault tolerance and the threshold theorem) · Preskill, Lecture Notes on Quantum Computation, Ch. 7 (fault-tolerant methods and topological codes) · Kitaev, Shen & Vyalyi, Classical and Quantum Computation (AMS, 2002) · Aharonov & Ben-Or, "Fault-tolerant quantum computation with constant error" (1997) · Fowler, Mariantoni, Martinis & Cleland, "Surface codes: towards practical large-scale quantum computation," Phys. Rev. A 86, 032324 (2012) · Bravyi & Kitaev, "Universal quantum computation with ideal Clifford gates and noisy ancillas," Phys. Rev. A 71, 022316 (2005) · Gottesman, "An introduction to quantum error correction and fault-tolerant quantum computation" (2009). Key reference values used throughout: the surface-code circuit-level threshold is $\approx0.5$ – $1\%$ and the code-capacity threshold is $\approx10.9\%$ (the random-bond Ising Nishimori point); the patch count scales as $\sim2d^2$ ; the 15-to-1 distillation output satisfies $p_{\mathrm{out}}\approx35\,p_{\mathrm{in}}^3$ . The worked resource numbers ( $d=25$ , $\sim1.25\times10^5$ data qubits, two distillation rounds) use the standard fitted prefactor $A\approx0.1$ and are illustrative order-of-magnitude estimates, not a benchmark for a fixed algorithm.

Prerequisites. Stabilizer Formalism · Quantum Error Correction · Toric Code and Topological Order · Magic-State Distillation. Leads to. Magic-State Distillation · Topological Quantum Computation · Measurement-Based Quantum Computation · Majorana Zero Modes.

Ask the tutor: Want to size a fault-tolerant machine for your own algorithm — plug in its qubit count, $T$ -count, and target error, and we will walk the distance, factory count, and full physical-qubit footprint together?

What exactly is a threshold, and why is the suppression called doubly-exponential?

The threshold $p_{\mathrm{th}}$ is the physical error rate at which encoding stops helping and starts hurting. Below it, wrapping your qubits in another layer of code lowers the effective error; above it, the extra components fail faster than the code corrects them. In the concatenated construction each level squares the rescaled error, $(p/p_{\mathrm{th}})\to(p/p_{\mathrm{th}})^2\to(p/p_{\mathrm{th}})^4\to\cdots$ , so after $L$ levels the exponent is $2^L$ — hence "doubly-exponential" in the number of levels. Because you only need $L\sim\log\log(1/\epsilon)$ levels to reach target error $\epsilon$ , and each level costs a constant factor in qubits, the total overhead is only polylogarithmic in $1/\epsilon$ . That combination — arbitrarily small error for a polylog price — is the whole promise of fault tolerance.

Why do magic-state factories dominate the qubit count of a big machine?

Because the surface code makes Clifford gates cheap and non-Clifford gates expensive, and useful algorithms are full of non-Clifford $T$ and Toffoli gates. Clifford operations come almost free from lattice surgery on the data patches, but Eastin–Knill forbids a transversal $T$ gate, so each one must be teleported in from a separately prepared, distilled magic state. Distillation is not cheap: a factory occupies tens of thousands to hundreds of thousands of physical qubits and outputs one purified state every several cycles, and an algorithm may consume billions of $T$ gates. To keep the data patches fed you pipeline many factories in parallel, and their combined footprint routinely equals or exceeds the data register. Reducing this overhead — through cheaper distillation, cultivation, or Toffoli-rich compilation — is a central architectural goal.

Is the surface code the only route to fault tolerance?

No — it is the current default, not a law. Its virtues are a high circuit-level threshold near $1\%$ and a strictly planar, nearest-neighbour layout, which is why most superconducting roadmaps target it. But its $\sim2d^2$ qubits per logical qubit are costly, and several alternatives trade that away. High-rate quantum LDPC codes encode many logical qubits in far fewer physical ones, at the price of long-range connectivity and harder decoding; measurement-based and fusion-based models recast computation as adaptive measurements on cluster states, natural for photonics; and topological quantum computation with non-Abelian anyons aims to make protection intrinsic to the hardware rather than actively corrected. A mature design chooses among these by jointly weighing threshold, overhead, connectivity demands, and decoder complexity — the surface code simply happens to sit at a convenient point for today's hardware.

What is the backlog problem, and why does it constrain the hardware?

Syndrome data is produced every physical cycle — about once per microsecond in superconducting qubits — and the decoder must, on average, process each round before the next arrives. If it cannot, undecoded rounds pile up, and because you cannot apply a logical gate until you know the current error frame, the logical clock must stall. While it stalls, physical errors keep accruing on the idle qubits, eventually overwhelming the code. This is the backlog problem, and it makes decoder throughput a hard architectural constraint alongside accuracy. It is why the field has invested in fast approximate decoders — union-find, sparse blossom, and hardware-accelerated or neural matchers — that accept a slight threshold penalty in exchange for staying inside the cycle time. A perfectly accurate decoder that runs too slow is useless.

Why does a single fault cause only one error in a fault-tolerant gadget?

Because the gadgets are deliberately built that way — it does not happen by default. A naive circuit shares qubits and gates freely, so one faulty two-qubit gate can copy an error onto both its qubits, and a single fault can grow into a weight-two or larger error that the code cannot correct. Fault-tolerant constructions forbid this by design: they use transversal operations where possible, verify ancilla states before use, and structure syndrome extraction so no single component touches two data qubits in a way that spreads a fault. The guarantee — one physical fault yields at most one error per code block, the "one bad apple" principle — is exactly what lets a distance- $d$ code survive until about $d/2$ independent faults coincide, giving the $p^{d/2}$ suppression that the whole threshold argument relies on.

Does being fault-tolerant mean the computer makes no errors?

No — it means the error rate can be driven as low as you are willing to pay for, not to zero. A fault-tolerant machine below threshold suppresses its logical error exponentially in the code distance, so you choose a distance large enough that the total failure probability of your specific algorithm sits under some tolerance, say $10^{-2}$ for the whole run. There is always a nonzero residual: a rare conspiracy of $\sim d/2$ faults can still cause an undetected logical error. The art is budgeting — picking a distance, a factory count, and a decoder so the summed logical error across all operations stays under budget without spending more qubits and cycles than you have. Fault tolerance buys arbitrarily good, not perfect, and the "arbitrarily" is limited only by finite resources.