Simple Algorithm
Quantum Computing · Excited State · 24 min

Fault Tolerance & the Threshold Theorem

Computing reliably with unreliable parts.

Error correction assumes the correction itself is perfect. It never is: every syndrome measurement is built from the same faulty gates it is meant to police. Fault tolerance is the art of designing circuits in which a few faults stay few, and the threshold theorem promises that, below a critical error rate, this is enough to compute for as long as you like.

What you’ll learn

  • Track how Pauli errors propagate through CNOT, HH and SS, and identify when one fault grows into an uncorrectable error.
  • Define fault-tolerant gadgets, and explain why transversal gates are fault tolerant.
  • State the threshold theorem and derive the doubly exponential error suppression p(k)=pth(p/pth)2kp^{(k)}=p_{\mathrm{th}}(p/p_{\mathrm{th}})^{2^k} of concatenated codes.
  • Explain why Clifford gates are not enough, and how magic states and gate teleportation supply the TT gate.

Faults spread

A fault is any component that misbehaves: a noisy gate, a bad preparation, an idle qubit that decoheres, a flipped measurement outcome. The danger is not the fault itself but what the rest of the circuit does to it. Gates move errors around: if an error EE occurs just before a gate UU, then

U E=(UEU†) UU\,E = (UEU^\dagger)\,U
An error before UU is the same as the conjugated error UEU†UEU^\dagger after it. Clifford gates map Pauli errors to Pauli errors, so Pauli errors stay Pauli errors.
GateError beforeError after
CNOT (control cc, target tt)XcX_cXcXtX_cX_t: bit flips spread forward
CNOTZtZ_tZcZtZ_cZ_t: phase flips spread backward
CNOTZcZ_c or XtX_tunchanged
HHXX / ZZZZ / XX
SSXX / ZZYY / ZZ

Phase errors flowing from target to control surprise most people. Test it: the two qubits below start in ∣+⟩∣+⟩\ket{+}\ket{+}, a state the CNOT leaves unchanged.

Now the problem is clear. Syndrome extraction couples every data qubit of a check to the same ancilla. One fault on the ancilla midway through can spread to several data qubits of the same code block. A distance-3 code corrects one error, so a single fault that produces two errors defeats it.

Check your understanding

An XX error hits the control of a CNOT just before the gate. What is the error just after it?

  1. XX on the control only
  2. XX on both control and target
  3. ZZ on the target
  4. XX on the target only
Show the answer

B. XX on both control and target

CNOT (X⊗I) CNOT=X⊗X\mathrm{CNOT}\,(X\otimes I)\,\mathrm{CNOT}=X\otimes X: the flipped control flips the target too. Bit flips spread forward, from control to target; phase flips spread backward.

Transversal gates

The simplest fault-tolerant gates never let two qubits of the same block interact. A transversal gate acts qubit by qubit, Uˉ=U1⊗U2⊗⋯⊗Un\bar U=U_1\otimes U_2\otimes\cdots\otimes U_n, or, between two blocks, couples qubit jj of one block only to qubit jj of the other. A fault in one physical gate then damages at most one qubit per block, which the code corrects.

For every CSS code, transversal CNOT between two blocks implements the logical CNOT. The Steane code [[7,1,3]][[7,1,3]] does even better, with transversal HH and SS as well, and hence the whole Clifford group. Why not TT?

DerivationPhase gates on the Steane code
  1. ∣0ˉ⟩=18∑c∈Ceven∣c⟩,∣1ˉ⟩=X⊗7∣0ˉ⟩\ket{\bar0}=\frac{1}{\sqrt8}\sum_{c\in C_{\mathrm{even}}}\ket{c},\qquad \ket{\bar1}=X^{\otimes7}\ket{\bar0}

    CevenC_{\mathrm{even}} is the even-weight half of the [7,4,3][7,4,3] Hamming code: one word of weight 0 and seven of weight 4. So ∣0ˉ⟩\ket{\bar0} contains weights {0,4}\{0,4\} and ∣1ˉ⟩\ket{\bar1} weights {7,3}\{7,3\}.

  2. S⊗7∣c⟩=iwt⁡(c)∣c⟩ ⇒ S⊗7∣0ˉ⟩=∣0ˉ⟩,S⊗7∣1ˉ⟩=i3∣1ˉ⟩=−i∣1ˉ⟩S^{\otimes7}\ket{c}=i^{\operatorname{wt}(c)}\ket{c}\ \Rightarrow\ S^{\otimes7}\ket{\bar0}=\ket{\bar0},\quad S^{\otimes7}\ket{\bar1}=i^{3}\ket{\bar1}=-i\ket{\bar1}

    i0=i4=1i^0=i^4=1 and i3=i7=−ii^3=i^7=-i: every term of a codeword gets the same phase, so S⊗7=Sˉ†S^{\otimes7}=\bar S^\dagger, a logical gate.

  3. T⊗7∣c⟩=eiπwt⁡(c)/4∣c⟩:wt⁡=0↦1,wt⁡=4↦−1T^{\otimes7}\ket{c}=e^{i\pi\operatorname{wt}(c)/4}\ket{c}:\qquad \operatorname{wt}=0\mapsto1,\quad\operatorname{wt}=4\mapsto-1

    Within ∣0ˉ⟩\ket{\bar0} the terms now get different phases, so T⊗7∣0ˉ⟩T^{\otimes7}\ket{\bar0} is no longer a codeword: transversal TT leaves the codespace.

The threshold theorem

Suppose every gadget of a distance-3 code is fault tolerant, so a logical error requires at least two faults inside one gadget. If a gadget has AA locations and each fails with probability pp, then

p(1) ≤ (A2)p2 = c p2p^{(1)}\ \le\ \binom{A}{2}p^2\ =\ c\,p^2
One level of encoding turns the physical error rate pp into a logical error rate of at most cp2cp^2. That helps exactly when cp2<pcp^2<p, i.e. p<1/cp<1/c.

Now concatenate: encode each physical qubit of the code in another copy of the code, and repeat. Each level squares the error rate, up to the constant cc.

DerivationDoubly exponential suppression
  1. p(k)=c (p(k−1))2p^{(k)} = c\,\big(p^{(k-1)}\big)^2

    Level kk treats level-(k−1)(k-1) gadgets as its physical components.

  2. c p(k)=(c p(k−1))2=⋯=(c p)2kc\,p^{(k)} = \big(c\,p^{(k-1)}\big)^2 = \cdots = (c\,p)^{2^k}

    Multiply by cc and unroll the recursion.

  3. p(k)=pth(ppth)2k,pth=1cp^{(k)} = p_{\mathrm{th}}\left(\frac{p}{p_{\mathrm{th}}}\right)^{2^k},\qquad p_{\mathrm{th}} = \frac1c

    Below pthp_{\mathrm{th}} the logical error falls doubly exponentially in kk, while the circuit size grows by at most a factor AA per level. Reaching error ε\varepsilon needs 2k∼log⁡(1/ε)2^k\sim\log(1/\varepsilon), so the overhead AkA^k is only polylogarithmic in 1/ε1/\varepsilon.

Predict before you look

Take p=10−3p=10^{-3} and pth=10−2p_{\mathrm{th}}=10^{-2}. How many levels of concatenation are needed to push the logical error per gate below 10−1510^{-15}?

Show the answer

4 levels

p(k)=10−2⋅(10−1)2kp^{(k)}=10^{-2}\cdot(10^{-1})^{2^k} gives 10−410^{-4}, 10−610^{-6}, 10−1010^{-10} and 10−1810^{-18} for k=1,2,3,4k=1,2,3,4. Three levels miss the target, four overshoot it by a lot: doubly exponential suppression.

The surface code reaches the same conclusion by a different route: instead of concatenating, grow the distance dd. Then pL≈A(p/pth)(d+1)/2p_L\approx A(p/p_{\mathrm{th}})^{(d+1)/2} with pth≈1%p_{\mathrm{th}}\approx1\%, and d=O(log⁡(1/ε))d=\order{\log(1/\varepsilon)} suffices.

Universality: Clifford + T via magic states

In the surface code, Clifford operations have fault-tolerant implementations (transversal CNOT, lattice surgery, code deformation). But Clifford circuits alone are classically simulable (the Gottesman–Knill theorem), so a fault-tolerant computer also needs a non-Clifford gate, usually the T gate T=diag⁡(1,eiπ/4)T=\diag(1,e^{i\pi/4}). No transversal trick provides it, so we teleport it in from a resource state, the magic state

∣T⟩=T∣+⟩=12(∣0⟩+eiπ/4∣1⟩)\ket{T} = T\ket{+} = \tfrac{1}{\sqrt2}\big(\ket0+e^{i\pi/4}\ket1\big)
DerivationInjecting a T gate
  1. (a∣0⟩+b∣1⟩)⊗12(∣0⟩+ω∣1⟩),ω=eiπ/4\big(a\ket0+b\ket1\big)\otimes\tfrac{1}{\sqrt2}\big(\ket0+\omega\ket1\big),\qquad\omega=e^{i\pi/4}

    A data qubit ∣ψ⟩=a∣0⟩+b∣1⟩\ket{\psi}=a\ket0+b\ket1 and a magic state.

  2. → CNOT  12[(a∣0⟩+ωb∣1⟩)∣0⟩+(ωa∣0⟩+b∣1⟩)∣1⟩]\xrightarrow{\ \mathrm{CNOT}\ }\ \tfrac{1}{\sqrt2}\Big[\big(a\ket0+\omega b\ket1\big)\ket0+\big(\omega a\ket0+b\ket1\big)\ket1\Big]

    CNOT with the data as control and the magic qubit as target; regroup by the magic qubit's value.

  3. Measure the magic qubit. Outcome 0 (probability 12\tfrac12): the data holds a∣0⟩+ωb∣1⟩=T∣ψ⟩a\ket0+\omega b\ket1=T\ket{\psi}. Outcome 1: it holds ωa∣0⟩+b∣1⟩∝T†∣ψ⟩\omega a\ket0+b\ket1\propto T^\dagger\ket{\psi}.

  4. S T†=TS\,T^\dagger = T

    So on outcome 1 apply the Clifford correction SS. Only Clifford operations and a measurement touched the data; the non-Clifford part arrived inside ∣T⟩\ket{T}.

Below, q0 is the data qubit, prepared in ∣+⟩\ket{+}, and q1 holds the magic state T∣+⟩T\ket{+}. The composer cannot branch on measurement outcomes, so use the deferred-measurement trick: replace "measure q1, and if 1 apply SS to q0" by a controlled-SS from q1 to q0.

An injected magic state is only as good as the physical operations that made it. Magic state distillation fixes that with Clifford operations alone: the 15-to-1 protocol (Bravyi & Kitaev, 2005) consumes 15 noisy copies with error ε\varepsilon and outputs one with error about 35ε335\varepsilon^3. Two rounds turn ε=10−2\varepsilon=10^{-2} into about 1.5×10−121.5\times10^{-12}. These "magic state factories" can occupy a large share of a fault-tolerant machine.

The full stack

Put the pieces together and a fault-tolerant quantum computer looks like this: logical qubits stored in surface-code patches of about 2d22d^2 physical qubits each, Clifford gates by lattice surgery, TT gates fed by magic-state factories, and a classical decoder processing syndromes in real time. Resource estimates make the costs concrete. Gidney and Ekerå (2021) estimated that factoring a 2048-bit RSA modulus would take about 20 million noisy qubits for about 8 hours at p=10−3p=10^{-3}; later algorithmic and architectural improvements brought published estimates below a million qubits (Gidney, 2025).

LayerJobMain cost
Physical qubitsStore and manipulate quantum statesError rate below threshold, ideally around pth/10p_{\mathrm{th}}/10
Code (surface code, distance dd)Suppress errors: pL≈A(p/pth)(d+1)/2p_L\approx A(p/p_{\mathrm{th}})^{(d+1)/2}About 2d22d^2 qubits per logical qubit
Logical Clifford gatesLattice surgery, transversal CNOT, Pauli-frame trackingTime: about dd rounds per operation
Logical TT gatesMagic states plus distillationFactories: many qubits and rounds
DecoderTurn syndromes into correctionsMust keep pace with microsecond rounds

Key takeaways

  • Gates propagate errors: CNOT copies XX forward and ZZ backward. Fault-tolerant gadgets guarantee that ss faults cause at most ss errors per block.
  • Transversal gates are fault tolerant by construction. CSS codes have transversal CNOT and the Steane code all Cliffords, but no code has a universal transversal set (Eastin–Knill).
  • Threshold theorem: below pthp_{\mathrm{th}}, concatenation gives p(k)=pth(p/pth)2kp^{(k)}=p_{\mathrm{th}}(p/p_{\mathrm{th}})^{2^k} at polylogarithmic overhead; surface codes achieve the same by growing dd.
  • The non-Clifford TT gate is teleported from a magic state with a CNOT, a measurement and an SS correction; distillation (15-to-1, ε→35ε3\varepsilon\to35\varepsilon^3) purifies the magic states.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A ZZ error hits the target of a CNOT just before the gate. Just after the gate, the error is…

  1. ZZ on the target only
  2. XX on both qubits
  3. ZZ on both control and target
  4. ZZ on the control only
Show the answer

C. ZZ on both control and target

CNOT (I⊗Z) CNOT=Z⊗Z\mathrm{CNOT}\,(I\otimes Z)\,\mathrm{CNOT}=Z\otimes Z. In the ∣±⟩\ket{\pm} basis the roles of control and target swap, so phase flips travel from target to control.

Question 2

Why is a transversal gate automatically fault tolerant?

  1. Each physical gate touches at most one qubit per code block, so one fault causes at most one error per block
  2. Transversal gates are noiseless
  3. Transversal gates are always Clifford gates
  4. Transversal gates are applied before encoding
Show the answer

A. Each physical gate touches at most one qubit per code block, so one fault causes at most one error per block

Fault tolerance is about containment. A transversal gate never couples two qubits of the same block, so a fault cannot spread within a block, and one error per block is correctable.

Question 3

At p=pth/3p=p_{\mathrm{th}}/3, what is the logical error rate after two levels of concatenation?

  1. pth/9p_{\mathrm{th}}/9
  2. pth/6p_{\mathrm{th}}/6
  3. pth/27p_{\mathrm{th}}/27
  4. pth/81p_{\mathrm{th}}/81
Show the answer

D. pth/81p_{\mathrm{th}}/81

p(2)=pth(1/3)22=pth/81p^{(2)}=p_{\mathrm{th}}(1/3)^{2^2}=p_{\mathrm{th}}/81. Level one gives pth/9p_{\mathrm{th}}/9, and level two squares the ratio again.

Question 4

In the TT-injection gadget, the magic qubit is measured and gives 1, leaving T†∣ψ⟩T^\dagger\ket{\psi} on the data. Which correction completes the TT gate?

  1. Another TT gate
  2. SS
  3. ZZ
  4. XX
Show the answer

B. SS

ST†=diag⁡(1,i e−iπ/4)=diag⁡(1,eiπ/4)=TST^\dagger=\diag(1,i\,e^{-i\pi/4})=\diag(1,e^{i\pi/4})=T. The correction is Clifford, which is the whole point: Cliffords are the cheap gates.

Go deeper

Further reading

  • P. W. Shor, "Fault-tolerant quantum computation", Proc. 37th FOCS (1996).
  • D. Aharonov & M. Ben-Or, "Fault-tolerant quantum computation with constant error", Proc. STOC (1997); journal version in SIAM J. Comput. (2008).
  • D. Gottesman, "An introduction to quantum error correction and fault-tolerant quantum computation" (2009), arXiv:0904.2557.
  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §10.6 (Cambridge, 10th anniv. ed., 2010).