Fault-Tolerance Goals

Quantum error-correcting codes store one logical qubit inside many physical qubits, so that small errors can be detected and corrected by syndrome measurement. But correcting idle memory is not enough: a useful computer must also compute, and every logical gate we apply is itself made of physical operations that can fail. Fault tolerance is the discipline of designing those logical operations so that the errors they introduce stay correctable.

The failure we are afraid of

Encoding alone does not make a circuit safe. Imagine a code that can correct any single physical error. If one physical gate inside a logical operation fails and then spreads that fault to many qubits within the same code block, the block can end up with two or more errors — beyond what the code can correct. A single fault has become an uncorrectable logical error.

The whole point of a fault-tolerant gadget is to break this chain: one fault should cause at most one error per code block. A procedure with that property is called fault-tolerant. More precisely, a level-1 fault-tolerant gadget guarantees that if at most $t$ components fail (where the code corrects $t$ errors), the output still has at most $t$ errors per block.

What "fault-tolerant gate" means

A logical gate is fault-tolerant when:

No single physical fault causes more than one error in any code block. This rules out constructions where one faulty two-qubit gate couples many data qubits of the same block.
The procedure preserves the code space, mapping valid encoded states to valid encoded states (possibly after a correctable error).
Errors remain detectable by the usual syndrome extraction after the gate.

The simplest way to satisfy condition 1 is a transversal gate, where the logical operation is a tensor product of single-qubit gates acting on corresponding qubits of separate blocks — explored in the next lesson. Because each physical gate touches only one qubit per block, a fault in one gate can corrupt only one qubit of that block.

The threshold theorem

Why is all this worth the overhead? The threshold theorem states that if the physical error rate $p$ per gate is below a code-dependent constant $p_{\text{th}}$ , then by concatenating or scaling up the code we can make the logical error rate

p_L \sim \left(\frac{p}{p_{\text{th}}}\right)^{(d+1)/2}

as small as we like, with only polylogarithmic overhead in the size of the computation. Here $d$ is the code distance. The theorem only holds when every operation — state preparation, gates, measurement, and error correction itself — is performed fault-tolerantly. A single non-fault-tolerant gadget breaks the guarantee.

Reported surface-code thresholds sit near $p_{\text{th}} \approx 10^{-2}$ for circuit-level noise, which is one reason the surface code is the leading near-term architecture.

Goals for this module

With the "what" established, the rest of this module builds the toolkit:

Which logical gates are easy (transversal) and which are not.
The Clifford group: a large, fault-tolerant-friendly set of gates that is nonetheless not universal for quantum computation.
Adding the $T$ gate to reach universality, why $T$ is expensive, and how magic-state injection supplies it fault-tolerantly.
Synthesizing arbitrary rotations from the discrete Clifford+ $T$ set, and accounting for the cost in $T$ -count and $T$ -depth.

By the end you will be able to take a logical algorithm and compile it into a fault-tolerant Clifford+ $T$ circuit, reasoning quantitatively about its dominant cost.