Fault-Tolerant Gate Constructions

Encoding a logical qubit protects information that merely sits still; the moment you compute on it, the protection can turn into a liability. A logical gate is a circuit acting on the physical qubits of a code block, and a careless circuit lets a single physical fault spread — one broken component seeds errors on several qubits of the same block, blowing past the correction budget $t=\lfloor (d-1)/2\rfloor$ and flipping the encoded qubit for good. A fault-tolerant gate construction is a circuit that refuses to let this happen: any single component fault — a bad gate, a mismeasurement, a noisy idle location, a corrupted ancilla — produces at most one error per code block, so the residual damage stays inside the correction radius and the next round of syndrome extraction cleans it up. The cleanest way to buy this guarantee is transversality: apply operations qubit-by-qubit, pairing qubit $i$ of one block only with qubit $i$ of another, never two qubits inside the same block. A single faulty gate then damages a single qubit per block, automatically. For CSS codes the Clifford generators — Hadamard, phase, and CNOT — are transversal by the code's symmetry. But transversality alone can never finish the job: the Eastin–Knill theorem proves that the transversal logical gates of any code form a finite group, and a finite group cannot approximate the continuum of rotations universal computing needs. Something non-transversal must supply the missing angle — magic-state distillation, lattice surgery, or gauge fixing — each engineered to obey the same single-fault-single-error discipline. This article is the toolbox of the fault-tolerant processor.

Key takeaways

A logical gate is fault tolerant if any single fault in its circuit produces at most one error per code block, keeping the damage inside the correction radius $t=\lfloor(d-1)/2\rfloor$ rather than letting it cascade into a logical error.
Transversal gates — single-qubit or pairwise-aligned operations applied physical-qubit-by-physical-qubit — are fault tolerant for free, because no gate ever couples two qubits within the same block.
The Eastin–Knill theorem forbids any code from having a transversal universal gate set: the transversal logical gates always form a finite group, so at least one gate must come from another mechanism.
Magic-state distillation supplies the non-Clifford $T$ gate by purifying noisy resource states and injecting them by teleportation; the 15-to-1 protocol drives the error as $p_{\text{out}}=35\,p^3$ .
Lattice surgery realizes logical Clifford operations on the surface code by merging and splitting patches to measure joint logical operators, using only local 2D interactions.
Key idea: fault tolerance is a property of the circuit, not of the code — a gadget is fault tolerant when one fault makes at most one error per block; transversality guarantees this cheaply, and everything non-transversal (distillation, surgery, gauge fixing) is built to preserve the same invariant.

The core insight

Fault tolerance is a circuit-level property, not a code property: a gadget is fault tolerant if any single fault produces at most one error per code block, so the error stays within the code's correction radius. Transversality is the simplest way to guarantee this; everything non-transversal — distillation, lattice surgery, gauge fixing — is engineered to preserve the same invariant.

Where this lives today

Fault-tolerant gate constructions are no longer theory — they are the instruction set of the machines now being built. Superconducting and neutral-atom surface-code processors run their logical Clifford operations almost entirely by lattice surgery: patches merge and split to enact CNOTs and joint measurements with only nearest-neighbor 2D coupling, and the recommended Pauli corrections are tracked in software as a Pauli frame rather than applied physically. The non-Clifford $T$ gate, forbidden transversally by Eastin–Knill on the surface code, is supplied by magic-state factories that distill and inject $|T\rangle$ ; because each $T$ costs a distilled state while Cliffords are cheap, compilers for Shor's algorithm and quantum chemistry now optimize almost entirely for $T$ -count and $T$ -depth. In 2024 Google's surface-code experiment demonstrated the exponential error suppression these constructions promise, with the logical error rate falling by a factor of roughly $\Lambda\approx2.14$ for each increase of the code distance by two. The complementary, distillation-free route is alive too: gauge fixing between the 2D color code (transversal Clifford, including $H$ and $S$ ) and the 3D gauge color code (transversal $T$ ) yields a universal fault-tolerant set by measuring gauge operators to switch codes, and neutral-atom platforms have begun running transversal logical gates and code-switching primitives that make this concrete. Every one of these rests on the single invariant Shor imposed: one fault, at most one error per block.

The physical picture

Picture a code block as a sealed vault: the information is smeared across many qubits so that touching any one of them reveals nothing and ruins nothing. A transversal gate reaches into two vaults at once but only ever wires qubit $i$ of one vault to qubit $i$ of the other — never qubit $i$ to qubit $j$ of the same vault. So if a gate misfires, exactly one qubit per vault goes wrong, which is precisely the failure the code was designed to shrug off. The whole art of fault tolerance is preserving this discipline: keep every wire between blocks, none inside a block, and a lone fault can never grow.

Figure

Transversal CNOT between two Steane blocks: each vertical wire pairs qubit i of block A only with qubit i of block B, so a single faulty gate (qubit 4) corrupts exactly one qubit per block — weight ≤ 1 ≤ t = 1 for a distance d = 3 code, still correctable

The Eastin–Knill theorem says you cannot do everything this gently. The transversal gates form a finite group — a discrete set of symmetries — but universal computation needs a continuum of rotations. Something has to give: you import the missing angle from outside via a purified resource state (a magic state), or you temporarily morph the code into a sibling code (gauge fixing) whose easy gates are exactly the ones the first code found hard. The dominant modern route is the first: prepare noisy encoded $|T\rangle$ states, distill many into one much cleaner copy, and inject it by teleportation to enact the non-Clifford $T$ gate. The second figure is the quantity an architect actually budgets — how fast distillation cleans a magic state.

Figure

The 15-to-1 magic-state distillation map p_out = 35 p³ (Bravyi–Kitaev, log-log): below the crossover p⋆ = 1/√35 ≈ 0.17 the output is cleaner than the input, so an input T-gate error of 10⁻² is purified to 35 × (10⁻²)³ = 3.5×10⁻⁵ in one round, and repeating drives the error toward zero

Lattice surgery is the plumber's alternative to teleportation for the Clifford part. Rather than swimming two logical surface-code patches around each other to entangle them, you knock down the wall between two adjacent patches for a few rounds — measuring the joint logical operator $\bar Z\otimes\bar Z$ along the seam — then rebuild the wall. The merge/split sequence enacts a logical measurement and, with an ancilla patch, a logical CNOT, all using the same local stabilizer measurements the idle code already runs. Gauge fixing, finally, treats a subsystem code's extra freedom as a dial: measuring a gauge operator fixes its value, promotes it to a stabilizer, and morphs one code into a sibling whose transversal gates are complementary — so alternating between the pair recovers universality with no distillation at all.

The core equations

Fault tolerance starts with a single inequality, the contract every gadget must sign. A gate is fault tolerant exactly when one fault cannot push the per-block error weight above what the code can correct.

\text{1 fault} \;\Longrightarrow\; \text{weight} \le 1 \ \text{error per block} \;\le\; t=\Big\lfloor \tfrac{d-1}{2}\Big\rfloor \qquad (1)

where: $d$ — the code distance; $t$ — the number of arbitrary single-qubit errors the code corrects. Reading: the criterion is about propagation, not about the logical map — many circuits implement the right logical unitary yet violate this contract by letting one fault become a weight-2 error, which is then uncorrectable. The simplest way to satisfy the contract is a transversal gate: a tensor product of operations acting independently on corresponding physical qubits, with no coupling between two qubits of the same block.

\bar U = \bigotimes_{i=1}^{n} u_i \quad\text{(single block)},\qquad \overline{U} = \prod_{i=1}^{n} V^{(i)}\ \text{across blocks} \qquad (2)

where: $\bar U$ — the logical operation induced on the encoded qubit(s); $u_i$ — a single-qubit gate on physical qubit $i$ ; $V^{(i)}$ — a gate coupling qubit $i$ of one block to qubit $i$ of another block only; $n$ — physical qubits per block. Reading: because every qubit meets at most one gate, and that gate reaches at most one partner in another block, a single fault lands on at most one qubit per block — equation (1) holds automatically. Which logical gate a transversal circuit produces is decided by how Cliffords conjugate Paulis. These four identities are the entire multiplication table needed to track a Clifford through a stabilizer code.

H X H = Z,\quad H Z H = X,\quad S X S^{\dagger}=Y,\quad S Z S^{\dagger}=Z \qquad (3)

where: $H$ — Hadamard gate; $S=\mathrm{diag}(1,i)$ — phase gate; $X,Y,Z$ — the Pauli operators. Reading: a bitwise $H$ swaps the code's $X$ -type and $Z$ -type structure, so on a self-dual CSS code it implements logical $\bar H$ ; bitwise $S$ likewise implements logical $\bar S$ up to a Pauli — these are the transversal Clifford generators. The two-block generator is the transversal CNOT, whose fault tolerance and logical action both follow from how it copies Paulis between control and target.

\mathrm{CNOT}\,(X\otimes I)\,\mathrm{CNOT}=X\otimes X,\qquad \mathrm{CNOT}\,(I\otimes Z)\,\mathrm{CNOT}=Z\otimes Z \qquad (4)

where: $\mathrm{CNOT}$ — controlled-NOT with control on the first qubit. Reading: $X$ copies forward (control → target) and $Z$ copies backward (target → control); applied qubit-wise between two CSS blocks this sends $\bar X_A\mapsto\bar X_A\bar X_B$ and $\bar Z_B\mapsto\bar Z_A\bar Z_B$ , exactly the logical CNOT. Transversality can never finish the universal set, and the reason is a theorem. The logically nontrivial transversal gates of any code form a finite group.

\mathcal{T}=\{\,\bar U : \bar U \text{ transversal and preserves the code space}\,\}\ \text{is a finite group} \qquad (5)

where: $\mathcal{T}$ — the group of transversal logical gates of a code with distance $d\ge 2$ . Reading: a finite group is discrete, so it cannot be dense in $SU(2)$ — no transversal set approximates arbitrary rotations, and universality demands at least one non-transversal gate. This is the Eastin–Knill obstruction. Lattice surgery supplies the multi-qubit Cliffords non-transversally but still locally. Merging two surface-code patches for a few rounds measures a joint logical operator whose value is read off the new seam stabilizers.

\bar Z_1\bar Z_2 \;\xrightarrow{\ \text{merge}\ }\; \text{stabilizer of the merged patch} \;\xrightarrow{\ \text{split}\ }\; m\in\{0,1\} \qquad (6)

where: $\bar Z_1,\bar Z_2$ — the logical $Z$ operators of two adjacent patches; $m$ — the $\pm1$ outcome of the joint $\bar Z_1\bar Z_2$ measurement, equal to the product of the seam stabilizer outcomes. Reading: the merge measures $\bar Z_1\bar Z_2$ without measuring either $\bar Z$ alone, so it entangles the logical qubits while leaving each one's superposition intact — the ingredient a measurement-based CNOT needs. The non-Clifford gate itself is injected by teleportation through a magic state, converting a purified resource into a logical $T$ .

|T\rangle=\tfrac{1}{\sqrt2}\big(|0\rangle+e^{i\pi/4}|1\rangle\big),\qquad T|\psi\rangle = S^{m}\,\big[\text{CNOT-teleport}(|\psi\rangle,|T\rangle)\big] \qquad (7)

where: $|T\rangle$ — the magic state carrying the $\pi/4$ phase; $m\in\{0,1\}$ — a measurement outcome; $S^m$ — a Clifford (phase-gate) correction applied only when $m=1$ . Reading: the hard, continuous $\pi/4$ rotation is precomputed into the offline state $|T\rangle$ ; the online circuit is pure Clifford plus a classically conditioned Clifford correction, so all the non-transversal difficulty is quarantined in preparing $|T\rangle$ — which distillation makes fault tolerant.

Derivation ATransversal CNOT is fault tolerant for every CSS code

The goal is to prove that applying CNOT qubit-by-qubit between two blocks of the same CSS code does two things at once: it implements the logical CNOT, and it propagates any single fault to at most one error per block, so it satisfies the fault-tolerance contract of equation (1). We take a CSS code with $X$ -type stabilizer generators and $Z$ -type generators, logical operators $\bar X,\bar Z$ built from physical Paulis, and two identical blocks $A$ (control) and $B$ (target), then track both the code space and a lone fault through the bitwise gate $\overline{\mathrm{CNOT}}=\bigotimes_i \mathrm{CNOT}_{A_i\to B_i}$ .

Step 1. Check that $X$ -type stabilizers stay in the group. A generator $g=\prod_{i\in K}X_i$ on block $A$ propagates under the bitwise CNOT to $\prod_{i\in K}X_i^{A}X_i^{B}$ , using $X$ copies forward from equation (4). Because both blocks are the same code, $\prod_{i\in K}X_i^{B}$ is itself a stabilizer of $B$ , so the image is the product of two stabilizers and remains in the joint stabilizer group. Why: preserving the stabilizer group is what guarantees the gate maps the code space to itself rather than leaking amplitude out of it.

Step 2. Check the $Z$ -type generators the same way. A generator $h=\prod_{i\in K}Z_i$ on block $B$ propagates to $\prod_{i\in K}Z_i^{A}Z_i^{B}$ , since $Z$ copies backward. Again the extra factor $\prod_{i\in K}Z_i^{A}$ is a stabilizer of $A$ , so the image stays in the group. Why: CSS codes keep $X$ and $Z$ checks separate, so the two Pauli-copy directions of CNOT act on the two check types independently and neither is spoiled.

Step 3. Read off the logical action. The same propagation applied to the logical Paulis gives $\bar X_A\mapsto\bar X_A\bar X_B$ and $\bar Z_B\mapsto\bar Z_A\bar Z_B$ , while $\bar X_B$ and $\bar Z_A$ are left unchanged. This is exactly the defining conjugation of the logical CNOT with $A$ the control and $B$ the target. Why: a stabilizer gate is fully specified by its action on logical Paulis, so matching all four generators of the logical Pauli algebra confirms the gadget really is the logical CNOT.

Step 4. Follow a single fault. A fault on the physical gate $\mathrm{CNOT}_{A_i\to B_i}$ can leave a Pauli error on qubit $i$ of $A$ and qubit $i$ of $B$ — one qubit in each block. No physical gate ever couples qubit $i$ to qubit $j$ inside the same block, so the intra-block weight can never exceed 1. Why: this is the geometric heart of fault tolerance — the absence of intra-block wires caps the damage at weight 1, independent of what the fault actually is.

Step 5. Close the contract. A weight-1 error per block satisfies $1\le t$ for any $d\ge 3$ , so the next round of syndrome extraction and decoding removes it. The gadget therefore meets the single-fault-single-error criterion and is fault tolerant. Why: the correction radius $t=\lfloor(d-1)/2\rfloor$ is exactly the budget the propagation stays within, so no accumulation of one fault ever becomes a logical error.

Go deeper · Derivation B · 2 minEastin–Knill: no code has a transversal universal gate set

Derivation BEastin–Knill: no code has a transversal universal gate set

The goal is to show that the transversal logical gates of any code with distance $d\ge 2$ form a finite (hence non-universal) group, which forces every universal fault-tolerant scheme to include at least one non-transversal gate. The engine of the proof is a collision between two facts: a continuous gate family must be generated by a Hermitian operator, while a transversal gate's generator is a sum of single-qubit terms — and a distance-2 code, by the Knill–Laflamme conditions, cannot let any single-qubit operator act nontrivially on the logical information. We suppose a continuum exists and derive a contradiction.

Step 1. Assume a one-parameter transversal family. Suppose $\bar U(\theta)=e^{-i\theta\bar K}$ is a continuous family of transversal logical gates connected to the identity. Because each $\bar U(\theta)$ is a tensor product $\bigotimes_i u_i(\theta)$ , its generator is a sum of single-qubit terms, $\bar K=\sum_i K_i$ with each $K_i$ Hermitian and supported on one qubit. Why: transversality is exactly the statement that the gate factorizes qubit-by-qubit, and differentiating a product of single-qubit unitaries produces a sum of single-qubit generators.

Step 2. Project onto the code space. Let $P$ be the projector onto the code. The logical rotation the family induces is generated by $P\bar K P=\sum_i P K_i P$ . Why: only the action inside the code space carries logical meaning, so the relevant generator is the compression $P\bar K P$ , not $\bar K$ on the full Hilbert space.

Step 3. Kill the single-qubit pieces. For a code of distance $d\ge 2$ that detects every weight-1 error, the Knill–Laflamme conditions give $P K_i P = c_i\,P$ for scalars $c_i$ : any single-qubit operator acts on the code space as a multiple of the identity. Summing, $P\bar K P=(\sum_i c_i)\,P$ . Why: error correction of weight-1 errors is precisely the demand that low-weight operators carry no logical information, and that is exactly what forbids a single-qubit generator from rotating the logical qubit.

Step 4. Conclude discreteness. The induced logical generator is proportional to the identity, so $\bar U(\theta)$ acts as a global phase on the code — no nontrivial continuous logical rotation exists. The transversal logical group therefore has no one-parameter subgroups: it is discrete, and modulo global phase it is finite. Why: a Lie group with trivial Lie algebra is discrete, so the transversal gates cannot fill out $SU(2)$ and cannot be universal — universality must come from elsewhere.

Go deeper · Derivation C · 2 minLogical CNOT by lattice surgery

Derivation CLogical CNOT by lattice surgery

The goal is to construct a fault-tolerant logical CNOT between two surface-code patches using only merge/split joint measurements and one logical ancilla, with nothing but nearest-neighbor 2D interactions — the operation that lets a planar chip compute without ever moving or braiding qubits. The tool is the measurement-based identity that a CNOT can be assembled from a joint $ZZ$ measurement, a joint $XX$ measurement, an ancilla prepared in $|+\rangle$ , and Pauli corrections; lattice surgery realizes each joint measurement by merging patches along a boundary.

Step 1. Place an ancilla. Prepare a logical ancilla patch $a$ in $|+\rangle_a$ sitting between the control patch $c$ and the target patch $t$ . Why: the ancilla is the intermediary that carries entanglement from control to target so the two data patches never need to touch directly.

Step 2. Merge for $\bar Z\bar Z$ . Merge $c$ and $a$ along their rough boundary for about $d$ rounds; the new seam stabilizers multiply to $\bar Z_c\bar Z_a$ , so the merge measures $\bar Z_c\bar Z_a$ with outcome $m_1$ , and splitting restores two patches. Why: measuring the joint $\bar Z\bar Z$ without measuring either $\bar Z$ alone entangles $c$ and $a$ while preserving each logical superposition — the first half of the CNOT.

Step 3. Merge for $\bar X\bar X$ . Merge $a$ and $t$ along the complementary smooth boundary to measure $\bar X_a\bar X_t$ with outcome $m_2$ , then split. Why: the two joint measurements are in complementary bases, which is exactly the pair the measurement-based CNOT identity requires.

Step 4. Read out the ancilla and correct. Measure the ancilla $a$ in the $Z$ basis with outcome $m_3$ . The three outcomes $m_1,m_2,m_3$ determine a Pauli correction on $c$ and $t$ , which is not applied physically but tracked in the classical Pauli frame. Why: Pauli corrections commute cleanly through later Clifford operations, so bookkeeping them in software is free and avoids injecting fresh gate faults.

Step 5. Confirm fault tolerance. Each merge is $\sim d$ rounds of the same local stabilizer measurement the idle code already performs, so a single fault flips one seam syndrome bit and is corrected by the standard decoder — no error spreads across the logical qubit. Why: reusing idle-storage error correction as the mechanism for the gate means the gate inherits the code's fault tolerance for free, with no new failure mode.

Limiting cases

Each construction occupies a regime defined by what it can do and what it costs; laid side by side they are the menu a fault-tolerant architect chooses from.

Case	Result	Meaning
Transversal Clifford (CSS)	$\mathrm{CNOT},\,H,\,S$ transversal	generates the whole Clifford group with zero qubit overhead beyond the blocks; fault tolerant by construction but not universal
Eastin–Knill obstruction	$\mathcal{T}$ is a finite group	no code admits a transversal universal set — at least one gate must use distillation, surgery, or gauge fixing
Magic-state injection	$T\|\psi\rangle$ via $\|T\rangle=\tfrac{1}{\sqrt2}(\|0\rangle+e^{i\pi/4}\|1\rangle)$	supplies the non-Clifford gate; cost is many noisy states per distilled one, dominating the overhead
Lattice surgery (2D)	$\bar M_{ZZ}=\bar Z_1\bar Z_2$ by merge/split	realizes Clifford operations with only nearest-neighbor 2D coupling and a strip of ancillas; time cost $\sim d$ rounds per merge
Gauge fixing (subsystem)	$\mathcal{G}\to\mathcal{S}'=\langle\mathcal{S},S_{\text{gauge}}\rangle$	switches between codes with complementary transversal sets (e.g. 3D color code) to recover universality; needs a larger or higher-dimensional code
Perfect single fault ( $d=3$ )	weight-1 error, $t=1$	one fault, one error per block, always inside the correction radius — the tightest nontrivial fault-tolerant regime

Common trapConfusing a logical gate that exists with a logical gate that is fault tolerant

Any encoded operation can be written as some circuit on physical qubits — existence is never the problem. The trap is assuming that circuit is safe to run. Most naive circuits couple two qubits inside one block at some point, and a single fault there spreads into a weight-2-or-more error that the code cannot correct, silently flipping the logical qubit even though the circuit implements the correct logical unitary on a perfect device. Fault tolerance is a statement about how faults propagate, not about the target unitary. Transversality is one sufficient guarantee, but it is never universal (Eastin–Knill); conversely, a gate built from local-but-coupled operations within a block is generically not fault tolerant. And a subtler version bites even careful designers: a gadget can be fault tolerant for storage yet not for the specific gate, if its ancillas or measurements introduce a correlated fault path — which is why fault-tolerant designs verify preparations and measurements, not just the unitary skeleton.

Worked examples

1 · How fast 15-to-1 distillation cleans a magic state (fully worked)

The Bravyi–Kitaev 15-to-1 protocol uses the $[[15,1,3]]$ Reed–Muller code to distill 15 noisy $|T\rangle$ states into one, with output error $p_{\text{out}}=35\,p^3$ to leading order. Suppose your raw magic states have error $p=10^{-2}$ . Find the crossover error below which distillation helps, the output after one round, and the output after two rounds.

Step 1. Find the crossover. Distillation improves a state when $p_{\text{out}}<p$ , i.e. $35\,p^3<p$ , i.e. $35\,p^2<1$ . Solving gives the crossover $p_\star=1/\sqrt{35}=\mathbf{0.169}$ . Any raw error below $\approx0.17$ gets cleaner; above it, distillation makes things worse, so this is effectively the distillation threshold for the $T$ gate. Our raw error $10^{-2}$ sits comfortably below it.

Step 2. One round. Substitute $p=10^{-2}$ : $p_{\text{out}}=35\,(10^{-2})^3=35\times10^{-6}=\mathbf{3.5\times10^{-5}}$ . A single round has improved the magic state by nearly three orders of magnitude, at a cost of 15 raw states (plus the Clifford circuit and its own error correction) per output.

Step 3. Two rounds. Feed the round-1 output back in as the new raw error: $p_{\text{out}}^{(2)}=35\,(3.5\times10^{-5})^3=35\times4.29\times10^{-14}=\mathbf{1.5\times10^{-12}}$ . The cubic map is doubly exponential in the number of rounds — each round roughly cubes the error — so two rounds reach $10^{-12}$ , deep enough for a large algorithm, using $15^2=225$ raw states per final magic state.

Step 4. Read the cost. The overhead is set by the distance from raw error to target: because the map is $p\mapsto 35p^3$ , reaching error $\varepsilon$ needs only $O(\log\log(1/\varepsilon))$ rounds but a raw-state count that grows as a power of $1/\varepsilon$ . Distillation converts a modest, above-hardware-threshold $T$ -gate error into an arbitrarily small one, and its state count — not the Clifford part — is what dominates fault-tolerant resource estimates. This is why compiling an algorithm reduces to counting its $T$ gates.

2 · The fault ledger of a transversal CNOT on the Steane code

The Steane $[[7,1,3]]$ code has $d=3$ , so $t=1$ . Run a transversal CNOT between two Steane blocks and audit whether one fault can ever become uncorrectable.

Step 1. Fix the budget. With $d=3$ , the correction radius is $t=\lfloor(3-1)/2\rfloor=\mathbf{1}$ : the code corrects any single-qubit error on each block independently. A logical error requires a residual weight $\ge d=3$ (a minimum-weight logical operator has weight 3) that survives decoding.

Step 2. Enumerate the fault locations. The gadget is 7 physical CNOTs, $\mathrm{CNOT}_{A_i\to B_i}$ for $i=1,\dots,7$ . A single fault is one faulty CNOT. Its worst-case output is a two-qubit Pauli on that gate's control and target — qubit $i$ of $A$ and qubit $i$ of $B$ .

Step 3. Tally per-block weight. That worst-case fault deposits at most one Pauli on block $A$ (qubit $i$ ) and at most one on block $B$ (qubit $i$ ): weight $\le\mathbf{1}$ in each block. No physical CNOT touches two qubits of the same block, so there is no wire along which the error could grow to weight 2 within a block.

Step 4. Compare to the budget. Weight $1\le t=1$ in each block, so the single fault is correctable by one round of Steane syndrome extraction on each block. A single fault anywhere in the transversal CNOT is always correctable on the $[[7,1,3]]$ code — the gadget passes the ledger, which is the concrete meaning of fault tolerance. The same audit fails for a hypothetical circuit that entangled two qubits of one block: there a single fault could reach weight 2, exceed $t=1$ , and cause a logical error.

Physics of the portrait

Fault-tolerant gate constructions have a clear point of origin: before 1996 it was not even certain that computing on encoded qubits without amplifying errors was possible. One paper turned the question into an engineering discipline.

Origins · 1 minPeter Shor and how this was discovered

Peter Shor

born 1959 · fault-tolerant quantum computation

Peter Shor is best known for the 1994 factoring algorithm that made quantum computing a threat and a promise at once, but his contribution to fault tolerance is just as foundational. In 1995 he wrote down the first quantum error-correcting code, the nine-qubit code, proving that quantum information could be protected at all. The deeper problem remained: a stored qubit is useless if you cannot compute on it without the error correction itself spreading faults. In his 1996 paper "Fault-Tolerant Quantum Computation," Shor introduced the constructions this article is about — transversal gates, fault-tolerant syndrome extraction using verified ancillas ("Shor states"), and the discipline that a single fault must produce at most one error per block. That single-fault-single-error principle is the invariant every later scheme, from lattice surgery to gauge fixing, is built to preserve. Combined with the threshold theorem proved soon after by Aharonov and Ben-Or, Kitaev, and Knill, Laflamme and Zurek, Shor's constructions showed that arbitrarily long quantum computations are possible below a constant error rate. The Eastin–Knill no-go theorem (2009) later marked the exact boundary of the transversal approach, and magic-state distillation, lattice surgery, and gauge fixing grew up to cross it — but all of them still answer to the fault-propagation bookkeeping Shor first imposed.

History

1996

— Shor constructs the first fault-tolerant gates from transversal operations and verified ancillas

1998

— Gottesman casts fault tolerance in the stabilizer and Heisenberg-picture language

2005

— Bravyi and Kitaev introduce magic-state distillation for the non-Clifford gate

2009

— Eastin and Knill prove no code has a transversal universal gate set

2012

— Horsman, Fowler, Devitt and Van Meter formalize lattice surgery for the surface code

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, Ch. 10.6 (fault-tolerant quantum computation) · Preskill, Lecture Notes on Quantum Computation, Ch. 7 · Gottesman, Stabilizer Codes and Quantum Error Correction (PhD thesis, Caltech, 1997) · Eastin & Knill, Restrictions on Transversal Encoded Quantum Gate Sets, PRL 102, 110502 (2009) · Bravyi & Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas, PRA 71, 022316 (2005) · Horsman, Fowler, Devitt & Van Meter, Surface code quantum computing by lattice surgery, NJP 14, 123011 (2012) · Bombín, Gauge color codes, NJP 17, 083002 (2015) · Kitaev, Shen & Vyalyi, Classical and Quantum Computation. The key checkpoints in this article are: the Clifford–Pauli conjugations $HXH=Z$ , $SXS^\dagger=Y$ , and the CNOT identities of equation (4); the fact that a transversal CNOT on a CSS code preserves the stabilizer group, implements the logical CNOT, and keeps one fault to weight ≤ 1 per block; the Eastin–Knill statement and its local-generator plus Knill–Laflamme proof skeleton; the lattice-surgery merge/split measurement of joint logical operators; and the 15-to-1 distillation map $p_{\text{out}}=35\,p^3$ with crossover $p_\star=1/\sqrt{35}=0.169$ and the worked values $10^{-2}\to3.5\times10^{-5}\to1.5\times10^{-12}$ . The magic state $|T\rangle=\tfrac{1}{\sqrt2}(|0\rangle+e^{i\pi/4}|1\rangle)$ and the criterion $t=\lfloor(d-1)/2\rfloor$ are standard textbook values; no hardware threshold is quoted as a universal number, as thresholds are model-dependent.

Prerequisites. Stabilizer Formalism · Pauli Group and Clifford Group · CSS Codes · Code Distance and Logical Operators · Syndrome Measurement and Decoding. Leads to. Magic-State Distillation · Threshold Theorem · Surface Codes.

Ask the tutor: Want to walk through the fault ledger of a specific gadget, or see exactly how code switching between the Steane and Reed–Muller codes assembles a universal fault-tolerant set?

What exactly does "fault tolerant" mean — is it the same as "error correcting"?

No, they are different layers. Error correction is about the code: it says a stored logical qubit can survive up to $t$ physical errors between correction rounds. Fault tolerance is about the circuit: it says the operations you run — gates, preparations, measurements, and even the error-correction circuitry itself — do not amplify a single fault into more errors than the code can handle. A perfect code run with careless gadgets is not fault tolerant, because one broken gate can spread into a weight-2 error the code cannot fix. The formal contract is the single-fault-single-error rule: any one component failure leaves at most one error per block. Fault tolerance is what lets error correction actually be applied continuously during a computation rather than only to idle memory.

Why is a transversal gate automatically fault tolerant?

Because of its geometry. A transversal gate acts qubit-by-qubit: each physical qubit meets at most one elementary gate, and that gate reaches at most one partner qubit — always in a different block, never a second qubit of the same block. So if any one gate misfires, the damage lands on a single qubit of each block involved, which is a weight-1 error per block. Since no wire ever couples two qubits inside one block, there is simply no path along which a single fault could grow to weight 2 within a block. A weight-1 error is inside the correction radius of any distance-3-or-better code, so the next syndrome round removes it. Fault tolerance here is not something you check gate-by-gate; it follows structurally from the absence of intra-block coupling.

What does the Eastin–Knill theorem actually forbid, and how do people get around it?

It forbids a single code from having a transversal implementation of a universal gate set. Concretely, the transversal logical gates of any code form a finite group, and a finite group is discrete, so it can never approximate the continuous set of rotations a universal computer needs — there is always at least one gate you cannot do transversally. It is a no-go, not a dead end. The standard escapes all give up transversality for one gate while keeping the fault-tolerance contract by other means: magic-state distillation prepares the hard gate offline and injects it by teleportation; gauge fixing switches to a sibling code whose transversal set includes the missing gate; code concatenation and pieceable fault tolerance build the gate from carefully verified non-transversal pieces. The theorem is what tells architects where the expensive part of the machine has to be.

Why is the non-Clifford T gate so much more expensive than a CNOT?

Because the CNOT is transversal (or realizable by lattice surgery) at essentially the cost of the code blocks themselves, while the $T$ gate is forbidden transversally by Eastin–Knill and must be manufactured. The standard route prepares many noisy copies of the magic state $|T\rangle$ and distills them into one clean copy — the 15-to-1 protocol turns 15 states of error $p$ into one of error $35p^3$ — then teleports that state in to enact the gate. Each logical $T$ therefore consumes a whole distilled state produced by a magic-state factory, which can dominate the qubit and time budget of a fault-tolerant computer. This asymmetry is why resource estimates for algorithms count $T$ gates and $T$ -depth rather than total gate count: the Cliffords are nearly free, and the $T$ gates are where the cost lives.

How can lattice surgery do a CNOT without ever moving or braiding qubits?

It replaces motion with measurement. A CNOT can be built from a joint $ZZ$ measurement, a joint $XX$ measurement, an ancilla logical qubit in $|+\rangle$ , and Pauli corrections — an identity that needs no qubit to physically travel. Lattice surgery realizes each joint measurement by temporarily merging two adjacent surface-code patches along a boundary for about $d$ rounds: the new seam stabilizers multiply to the joint logical operator, so measuring them measures $\bar Z\bar Z$ or $\bar X\bar X$ without measuring either logical operator alone. Splitting rebuilds the separate patches. Because every step is a local stabilizer measurement — the same ones the idle code already runs — the operation needs only nearest-neighbor 2D coupling and inherits the code's fault tolerance directly. The Pauli corrections are tracked in classical software, so nothing is braided and no qubit is relocated.

What is gauge fixing, and how does it reach universality without distillation?

A subsystem code has extra operators — gauge operators — that commute with the logical operators but are not stabilizers; their values are free. Gauge fixing measures a chosen gauge operator, which fixes its value and promotes it to a stabilizer, shrinking the gauge group and transforming the code into a different code with a different transversal gate set. The trick to universality is to pair two codes with complementary transversal sets: for example, the 2D color code has transversal Clifford gates including $H$ and $S$ , while the 3D gauge color code has a transversal $T$ but lacks transversal $H$ . By gauge-fixing back and forth between them, every gate in a universal set is transversal in whichever code you are currently in, so the whole computation is fault tolerant with no magic states at all. The price is a larger, higher-dimensional code and the machinery to switch between them.

Does fault tolerance also cover state preparation and measurement, or only gates?

It has to cover all of them, or the guarantee is empty. A logical computation is preparations, gates, measurements, and idle waiting, and a single fault in any of these must still produce at most one error per block. Fault-tolerant preparation of a logical $|0\rangle$ or an ancilla cannot simply encode a physical state, because one fault during encoding could spread; instead one uses verified ancillas — Shor's original construction prepares a cat-state ancilla and checks it before use, discarding and retrying if a fault is detected. Fault-tolerant measurement likewise repeats or encodes the readout so a single mismeasurement does not force a wrong logical outcome. This is why fault-tolerant architecture is a systems discipline: the gates are only tolerant if the states they act on and the measurements that read them obey the same single-fault-single-error contract.