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, and , 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 of concatenated codes.
- Explain why Clifford gates are not enough, and how magic states and gate teleportation supply the 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 occurs just before a gate , then
| Gate | Error before | Error after |
|---|---|---|
| CNOT (control , target ) | : bit flips spread forward | |
| CNOT | : phase flips spread backward | |
| CNOT | or | unchanged |
| / | / | |
| / | / |
Phase errors flowing from target to control surprise most people. Test it: the two qubits below start in , 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.
An error hits the control of a CNOT just before the gate. What is the error just after it?
- on the control only
- on both control and target
- on the target
- on the target only
Show the answer
B. on both control and target
: 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, , or, between two blocks, couples qubit of one block only to qubit 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 does even better, with transversal and as well, and hence the whole Clifford group. Why not ?
is the even-weight half of the Hamming code: one word of weight 0 and seven of weight 4. So contains weights and weights .
and : every term of a codeword gets the same phase, so , a logical gate.
Within the terms now get different phases, so is no longer a codeword: transversal 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 locations and each fails with probability , then
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 .
Level treats level- gadgets as its physical components.
Multiply by and unroll the recursion.
Below the logical error falls doubly exponentially in , while the circuit size grows by at most a factor per level. Reaching error needs , so the overhead is only polylogarithmic in .
Take and . How many levels of concatenation are needed to push the logical error per gate below ?
Show the answer
4 levels
gives , , and for . 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 . Then with , and 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 . No transversal trick provides it, so we teleport it in from a resource state, the magic state
A data qubit and a magic state.
CNOT with the data as control and the magic qubit as target; regroup by the magic qubit's value.
Measure the magic qubit. Outcome 0 (probability ): the data holds . Outcome 1: it holds .
So on outcome 1 apply the Clifford correction . Only Clifford operations and a measurement touched the data; the non-Clifford part arrived inside .
Below, q0 is the data qubit, prepared in , and q1 holds the magic state . The composer cannot branch on measurement outcomes, so use the deferred-measurement trick: replace "measure q1, and if 1 apply to q0" by a controlled- 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 and outputs one with error about . Two rounds turn into about . 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 physical qubits each, Clifford gates by lattice surgery, 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 ; later algorithmic and architectural improvements brought published estimates below a million qubits (Gidney, 2025).
| Layer | Job | Main cost |
|---|---|---|
| Physical qubits | Store and manipulate quantum states | Error rate below threshold, ideally around |
| Code (surface code, distance ) | Suppress errors: | About qubits per logical qubit |
| Logical Clifford gates | Lattice surgery, transversal CNOT, Pauli-frame tracking | Time: about rounds per operation |
| Logical gates | Magic states plus distillation | Factories: many qubits and rounds |
| Decoder | Turn syndromes into corrections | Must keep pace with microsecond rounds |
Key takeaways
- Gates propagate errors: CNOT copies forward and backward. Fault-tolerant gadgets guarantee that faults cause at most 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 , concatenation gives at polylogarithmic overhead; surface codes achieve the same by growing .
- The non-Clifford gate is teleported from a magic state with a CNOT, a measurement and an correction; distillation (15-to-1, ) purifies the magic states.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A error hits the target of a CNOT just before the gate. Just after the gate, the error is…
- on the target only
- on both qubits
- on both control and target
- on the control only
Show the answer
C. on both control and target
. In the basis the roles of control and target swap, so phase flips travel from target to control.
Why is a transversal gate automatically fault tolerant?
- Each physical gate touches at most one qubit per code block, so one fault causes at most one error per block
- Transversal gates are noiseless
- Transversal gates are always Clifford gates
- 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.
At , what is the logical error rate after two levels of concatenation?
Show the answer
D.
. Level one gives , and level two squares the ratio again.
In the -injection gadget, the magic qubit is measured and gives 1, leaving on the data. Which correction completes the gate?
- Another gate
Show the answer
B.
. The correction is Clifford, which is the whole point: Cliffords are the cheap gates.
Go deeper
- Concatenation & the Threshold Theorem · Why errors below a threshold can be suppressed arbitrarily.
- Magic State Distillation · Buying non-Clifford gates with distilled resource states.
- Transversal Gates & Eastin–Knill · No code has a transversal universal gate set.
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).