Fault-Tolerant Gates

A fault-tolerant gate implements an operation on encoded information while keeping sufficiently small fault combinations recoverable. This is stronger than implementing the right logical unitary in a noiseless circuit. A gate can preserve the code space perfectly and still spread one ancilla fault into a logical error.

The essential questions are how errors propagate, which measurements distinguish their logical effects, and when a recovery or frame update is needed. We will use transversal CNOT as a concrete example, then explain why deformation, gauge fixing, intermediate correction and teleportation provide complementary ways to compute.

Required background. Why Quantum Error Correction Is Possible gives the recovery conditions; Stabilizer Formalism defines logical Paulis; Syndrome Measurement explains faulty check circuits; and Universal Gate Sets distinguishes Clifford operations from a universal gate set.

Fault propagation and correctable errors

A fault occurs at a circuit location, such as a preparation, gate, idle or measurement. An error is the disturbance that subsequently resides on the qubits. One faulty two-qubit gate may produce errors on both its outputs; later interactions may spread them further.

For an $[[n,k,d]]$ code, all errors supported on at most $t=\lfloor(d-1)/2\rfloor$ qubits are correctable. This is a useful sufficient set, not the full set of recoverable disturbances. Degeneracy, known erasure locations and biased noise can make other error sets correctable too.

For CNOT from control $c$ to target $q$, conjugation gives:

Incoming Pauli	Outgoing Pauli	Spreads?
$X_c$	$X_cX_q$	to target
$Z_c$	$Z_c$	no
$X_q$	$X_q$	no
$Z_q$	$Z_cZ_q$	to control

Thus an ancilla controlling many CNOTs can copy an $X$ error to many data qubits. With a common target ancilla, a $Z$ error can spread backward to many controls. Verified ancillas, flags, carefully ordered interactions and repeated checks address this problem in different ways. Their usefulness depends on the fault patterns the complete circuit can distinguish.

A precise input-error budget

Consider a gate involving several blocks. Let input block $i$ carry errors supported on at most $s_i$ qubits, and let $r$ internal locations be faulty. A common sufficient gate-gadget requirement applies when

$$\sum_i s_i+r\le t.$$

Under the specified local-fault model, the gadget should implement the correct logical operation and leave errors in a set that a final ideal recovery can correct. More detailed constructions use separate conditions for gate gadgets and correction gadgets; this simple inequality is not a substitute for those proofs.

The sum across input blocks matters. It is generally too strong to assume that a bare multi-block gate tolerates $t$ independent incoming errors in every block simultaneously. Those errors can meet in one output block even when the gate itself has no faults. Leading error correction is part of the reason a complete protected construction can be composed reliably.

Let $\mathcal E$ encode, $\mathcal N_{\rm in}$ describe an allowed incoming disturbance, $\mathcal G^{(r)}$ be a particular allowed faulty implementation, and $\mathcal D$ perform ideal recovery and decoding to logical space. The logical correctness condition is

$$\mathcal D\circ\mathcal G^{(r)}\circ \mathcal N_{\rm in}\circ\mathcal E =\mathcal U_L,$$

where $\mathcal U_L(\rho)=U_L\rho U_L^\dagger$. Syndrome registers are discarded by $\mathcal D$. The equality must hold for arbitrary logical inputs, including inputs entangled with another system. A separate spread condition ensures the outgoing disturbance remains suitable for subsequent gadgets.

This ideal decoder is a mathematical test of recoverability. The actual implementation still needs reliable syndrome extraction, inference and timely classical control. Aliferis, Gottesman, and Preskill (2006) formulate such gadget conditions for concatenated-code constructions.

Transversal CNOT and its limits

A transversal operation acts on corresponding positions of different blocks:

$$U_{\rm tr}=\bigotimes_{j=1}^{n}u_j.$$

Each $u_j$ touches at most one qubit per block. A fault confined to one factor can therefore affect one position in each participating block, but cannot directly reach another position of that same block.

For two identical CSS blocks, bitwise CNOT preserves the stabilizer and implements logical CNOT between corresponding logical qubits. An $X$-type stabilizer on the control is copied to the target; a $Z$-type stabilizer on the target is copied to the control. The corresponding logical Paulis transform in exactly the same way. CSS Codes develops the algebraic proof.

There are two distinct claims here. The support pattern limits fault spread. The CSS algebra ensures the circuit implements the desired encoded gate. An arbitrary tensor product of physical unitaries need not preserve the code space.

Incoming errors can combine

With clean inputs, one faulty physical CNOT can leave one error in each output block. A distance-three code corrects those separately. But suppose instead that a perfect transversal CNOT receives $X_{c_1}$ on the control block and $X_{q_2}$ on the target block. Then

$$X_{c_1}X_{q_2} \longmapsto X_{c_1}X_{q_1}X_{q_2}.$$

The target now has two errors. Each input block started with only one, but the total incoming support was two, outside the $t=1$ sufficient budget. In the usual Steane-code column ordering, $X_1X_2$ has the syndrome of $X_3$; correcting it as $X_3$ leaves the logical operator $X_1X_2X_3$.

Only three positions of each block are shown. Top: a faulty interaction at position 1 can damage both blocks at that position. Bottom: two incoming errors at different positions pass through a perfect layer and leave two errors in the target block. Transversality controls propagation from each location; it does not reset the incoming error count.

Hardware must also justify the location model. A shared control failure affecting many nominally separate factors is a correlated multi-position event. Calling the intended circuit transversal does not turn that event into several independent rare faults.

Why another mechanism is needed for universality

The available transversal gates depend on the code. The Steane Code has transversal logical Hadamard and inter-block CNOT; in the convention used there, $S^{\otimes7}$ implements logical $S^\dagger$. Other codes can make a non-Clifford phase gate transversal while lacking a complementary Clifford gate.

Eastin and Knill (2009) show that a fixed, nontrivial, finite-dimensional exact code detecting arbitrary single-subsystem errors cannot have a universal set of transversal encoded unitaries. Measurements, resource states, code switching and nontransversal circuits are outside that restricted gate mechanism.

There is a further geometric restriction: for the sufficiently large-distance, two-dimensional local stabilizer codes covered by Bravyi and König (2013), a constant-depth circuit of bounded-range gates can implement only a logical Clifford operation. A long measurement sequence or a changing encoding does not satisfy the same constant-depth-unitary premise. These results guide the choice of complementary mechanisms; they do not prohibit universal fault-tolerant computation.

Changing checks while preserving logical information

In code deformation, the measured stabilizers change over time. Boundaries can move, patches can merge, or the physical representation of a logical operator can change. New outcomes determine frame updates or additional constraints.

The initial and final code distances are insufficient to establish protection during the transition. A short chain of data and measurement faults can pass through an intermediate boundary. The complete measurement history, including preparation and final readout, determines which fault histories are distinguishable.

A circuit distance often counts the smallest undetected fault combination with nontrivial logical effect. This is not the number of arbitrary faults a decoder necessarily corrects. In a binary fault model, two explanations of the same detector record can differ by that undetected combination; a minimum-weight decoder has a guaranteed radius at most $\lfloor(D-1)/2\rfloor$ when the relevant distance is $D$. The code schedule and boundary conditions must be included in this statement.

Lattice surgery is an important example: local boundary checks implement a joint logical-Pauli measurement such as $Z_AZ_B$ while repeated rounds protect its outcome. The notation here denotes logical operators on patches A and B. A protected CNOT can be assembled from such parity measurements, an ancilla patch and frame updates. Lattice Surgery derives the measurement sequence and its corrections.

Standard planar-patch implementations typically use area proportional to $d^2$ and a number of repeated rounds proportional to $d$, with layout-dependent constants. These are properties of particular implementations, not a universal cost for every joint logical measurement. Routing space and idle faults during the operation matter too.

Gauge fixing and logical representatives

For a subsystem code, write the encoded space as $\mathcal H_L\otimes\mathcal H_G$, with protected logical subsystem L and gauge subsystem G. A gauge operator acts as $I_L\otimes g$. Measuring commuting gauge operators and fixing their signs changes G while preserving L.

The useful algebraic test is commutation with the bare logical algebra, represented as $L\otimes I_G$. A dressed logical representative may contain a gauge factor and need not commute with every gauge measurement. For example,

$$\begin{aligned} M&=I_L\otimes X_G,\\ \widetilde Z&=Z_L\otimes Z_G \end{aligned}$$

anticommute, although measuring $M$ acts only on the gauge subsystem. The bare representative $Z_L\otimes I_G$ commutes with $M$. Anticommutation with a dressed representative alone therefore does not show that the logical qubit is measured. See Subsystem Codes for the distinction.

Gauge fixing can expose different transversal gates in different encodings. Bombin (2015) develops this idea for gauge color codes; Anderson, Duclos-Cianci, and Poulin (2014) construct protected Steane–Reed–Muller conversion. The new checks must themselves be measured fault tolerantly, with outcome-dependent corrections that preserve the same logical identification. Vuillot and collaborators (2019) explain how code deformation and surgery can be described in this language.

Intermediate correction in pieceable gates

A pieceable construction divides a nontransversal operation into segments, with specialized correction between them. The dangerous errors are those that later segments would spread beyond recovery. Intermediate checks remove or constrain these errors before that growth occurs.

For a sequence $V_m\cdots V_1$, the implemented operation has correction steps between appropriate pieces. It is not enough to insert ordinary recovery at arbitrary times: the partially evolved state may not lie in the original code, and its errors may not match the original decoder’s assumptions. One needs the correct intermediate checks and a proof covering faults in those checks as well.

Yoder, Takagi, and Chuang (2016) construct nontransversal protected gates, including CCZ and Toffoli examples, in this way. The benefit is direct implementation without the usual distilled resource for that gate; the cost includes extra syndrome operations and construction-specific fault analysis. This is a different route to universality, not a consequence of simply slicing any circuit into short pieces.

Teleportation-based gates

Teleportation moves part of the difficult operation into an ancilla prepared before it touches the data. Let

$$|\Phi^+\rangle=(|00\rangle+|11\rangle)/\sqrt2,$$

and prepare $|\Phi_U\rangle=(I\otimes U)|\Phi^+\rangle$. For Bell outcomes labeled by $|\Phi_{ab}\rangle=(I\otimes X^aZ^b)|\Phi^+\rangle$, the unnormalized output is, up to an irrelevant branch phase,

$$\frac12 UX^aZ^b|\psi\rangle.$$

Each outcome has probability $1/4$ for the ideal resource. Writing $P_{ab}=X^aZ^b$, the known byproduct relative to the desired state is

$$C_{ab}=UP_{ab}U^\dagger.$$

Applying $C_{ab}^\dagger$ gives $U|\psi\rangle$. Gottesman and Chuang (1999) develop gate teleportation as a computational primitive; Quantum Teleportation derives the state-transfer identity.

If $U$ is Clifford, the correction is Pauli and can usually be tracked classically. For

$$T=\operatorname{diag}(1,e^{i\pi/4}),$$

one instead has $TXT^\dagger=(X+Y)/\sqrt2$. This operator is Clifford but not Pauli. A pure Pauli frame is no longer sufficient without adapting a subsequent operation or enlarging the tracked frame.

Teleportation does not purify an arbitrary bad resource. An error on the ancilla can become a logical data error, and a mistaken Bell outcome selects the wrong correction. Resource preparation, storage, Bell measurement and classical decisions all require protection. Magic State Distillation explains how noisy non-Clifford resources can be improved under specific assumptions.

Composing protected operations

In concatenated constructions, a rectangle consists of a gate gadget and trailing correction. An extended rectangle, or exRec, also includes the leading correction. Neighboring exRecs share a correction gadget, so their bad events cannot automatically be treated as independent. Aliferis, Gottesman, and Preskill (2006) handle this overlap in the threshold proof.

For independent stochastic faults of probability $p$, a construction tolerating every set of at most $t$ faulty locations has no logical failure from those sets. Its first possible contribution is order $p^{t+1}$, with a coefficient determined by damaging combinations of locations and fault types. Such combinations are called malignant. A common event producing several damaging faults with probability proportional to $p$ can remove that suppression.

Noise need not be Pauli or independent in every fault-tolerance theorem, but replacing a stochastic model by coherent amplitudes changes the analysis. For example, repeating the same small uncorrected logical rotation $N$ times adds its angle, whereas independent stochastic error probabilities compose differently. A single-gate average infidelity does not capture that distinction.

For a sequence described by composable logical channels, a useful rigorous error measure is half the diamond norm. Define

$$\delta_j=\tfrac12\|\mathcal G_j-\mathcal U_j\|_\diamond.$$

Let $\mathcal G_{\rm tot}$ and $\mathcal U_{\rm tot}$ denote the complete actual and ideal channel compositions. Contractivity and a telescoping expansion give

$$\tfrac12\|\mathcal G_{\rm tot}-\mathcal U_{\rm tot}\|_\diamond \le\sum_j\delta_j.$$

This bound does not require independent Pauli failures. It does require that the stated channels describe the composable process; isolated averages over a fluctuating memory environment may not do so. Synthesis error can be added using the same metric and triangle inequality. See Quantum Channels and Gate Decomposition for these two ingredients.

Finally, a heralded preparation has both an acceptance probability and an accepted output. Conditioning a trace-decreasing operation on success is not a linear channel when that probability depends on the input. For resources prepared separately, independent retries with acceptance $a$ multiply the mean number of attempts by $1/a$. For data already involved in an operation, rejection may instead destroy the input; retrying is not automatically possible.

Pauli corrections can often remain in a classical frame through Clifford operations. The deadline arises when an outcome first changes a measurement basis, resource choice or another adaptive step. Decoders explains why adequate throughput does not guarantee that deadline. A useful comparison includes the complete operation duration, leakage, rejected outcomes and the logical channel after all frame updates.

Exercises

1. Follow a fanout fault

An ancilla controls CNOTs into $w$ data qubits. Propagate an initial $X_a$. Repeat for a common-target ancilla initially carrying $Z_a$.

Solution

Each interaction copies the relevant component while leaving it on the ancilla:

$$\begin{aligned} X_a&\mapsto X_a\prod_{j=1}^wX_j,\\ Z_a&\mapsto Z_a\prod_{j=1}^wZ_j. \end{aligned}$$

The second line uses data-to-ancilla CNOTs. One fault can therefore produce weight $w$ on the data. Whether that pattern is harmful depends on its logical class and the available record; weight alone is only a sufficient recovery criterion.

2. Test the multi-block input budget

For identical Steane blocks, put $X_1$ on the control input and $X_2$ on the target input. Apply a perfect transversal CNOT and then independent minimum-weight recovery. Use check columns labeled by the nonzero binary vectors $1,\ldots,7$.

Solution

The control retains $X_1$ and the target acquires $X_1X_2$. The control recovery removes $X_1$. Since binary columns $1\oplus2=3$, the target decoder applies $X_3$, leaving $X_1X_2X_3$. This commutes with the checks and is not an $X$ stabilizer, whose nonidentity elements have weight four. It is a logical $X$. The two incoming errors exceed the total $t=1$ budget even though each block initially has only one error.

3. Bound malignant-pair failure

A distance-three construction has $N$ independent locations, each faulty with probability $p$. All single faults are tolerated, and $A_2$ pairs can be malignant. Bound failure while allowing every event with three or more faults to be harmful.

Solution

The union bound gives

$$\begin{aligned} p_L&\le A_2p^2+\Pr(K\ge3),\\ \Pr(K\ge3)&=\sum_{j=3}^N\binom Njp^j(1-p)^{N-j}. \end{aligned}$$

Here $K$ is the number of faulty locations. For fixed $N$, the result is $A_2p^2+O(p^3)$. Independence is used in these probabilities. A shared event creating a malignant pair with probability $cp$ produces a first-order contribution instead.

4. Distinguish bare and dressed logical operators

Start with $\rho_L\otimes|0\rangle_G\langle0|$ and measure $M=I_L\otimes X_G$. What happens to the logical state in either outcome? Why is anticommutation with $Z_L\otimes Z_G$ harmless here?

Solution

Each outcome has probability $1/2$ and gives $\rho_L\otimes|\pm\rangle_G\langle\pm|$. The logical state remains $\rho_L$. The anticommutation comes from $X_GZ_G=-Z_GX_G$, entirely within the gauge factor. Bare logical operators $L\otimes I_G$ commute with this measurement. For an initially correlated logical–gauge state, a conditioned outcome can reveal existing correlations; the nonselective gauge measurement still leaves the reduced logical state unchanged.

5. Identify the non-Pauli teleportation correction

Take $U=T$ and Bell outcome $(a,b)=(1,0)$. Compute the correction and check that it is Clifford.

Solution

The output is $TX|\psi\rangle$. Its byproduct is

$$C=TXT^\dagger=(X+Y)/\sqrt2.$$

It is Hermitian and squares to identity, so the correction is $C$ itself. Conjugation gives $CXC=Y$, $CYC=X$ and $CZC=-Z$, proving it is Clifford. It is not proportional to any Pauli. Applying it gives $CTX|\psi\rangle=T|\psi\rangle$.

6. Locate the shared correction

In the chronological sequence $\mathrm{EC}_0,G_1,\mathrm{EC}_1,G_2,\mathrm{EC}_2$, identify the two exRecs and their overlap.

Solution

The first includes $\mathrm{EC}_0,G_1,\mathrm{EC}_1$; the second includes $\mathrm{EC}_1,G_2,\mathrm{EC}_2$. They share the same physical correction operation $\mathrm{EC}_1$. A fault there is one event, not two independently sampled faults. Composable threshold arguments must account for this overlap rather than multiplying neighboring bad-event probabilities without justification.

7. Compare coherent repetition with a probability estimate

Suppose the only residual logical error is the same rotation $R_Z(\theta)$ after every intended identity gate. Find the average gate infidelity after $N$ repetitions. Compare it with $N$ times the one-gate infidelity when $N|\theta|\ll1$.

Solution

The combined error is $R_Z(N\theta)$. For a qubit unitary, the trace formula for average fidelity gives

$$r_N=\frac23\sin^2(N\theta/2).$$

At small accumulated angle, $r_N\simeq N^2\theta^2/6$, whereas $Nr_1\simeq N\theta^2/6$. The difference is coherent addition of amplitudes. The half-diamond error is $|\sin(N\theta/2)|$, consistent with a linear upper bound in the one-step half-diamond error. This example does not assume the residual rotation is corrected between repetitions.

8. Include rejected resource preparations

A resource attempt consumes 20 raw ancillas and takes time $\tau$. It is accepted independently with probability $0.8$. Find the mean raw consumption and serial preparation time per accepted resource. Can the same retry calculation always be used after a failed gate on unknown data?

Solution

The geometric mean attempt count is $1/0.8=1.25$, giving 25 raw ancillas and $1.25\tau$ in serial operation. Parallel factories have different timing and storage needs. A failed gate may have measured or destroyed the unknown data, so the input cannot simply be recreated. The geometric retry model applies only when each rejected attempt can be restarted with the needed input available.

References

• P. Aliferis, D. Gottesman, and J. Preskill, “Quantum accuracy threshold for concatenated distance-3 codes,” Quantum Information and Computation 6, 97–165 (2006), arXiv:quant-ph/0504218.
• J. T. Anderson, G. Duclos-Cianci, and D. Poulin, “Fault-tolerant conversion between the Steane and Reed–Muller quantum codes,” Physical Review Letters 113, 080501 (2014), doi:10.1103/PhysRevLett.113.080501, arXiv:1403.2734.
• H. Bombin, “Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes,” New Journal of Physics 17, 083002 (2015), doi:10.1088/1367-2630/17/8/083002, arXiv:1311.0879.
• S. Bravyi and R. König, “Classification of topologically protected gates for local stabilizer codes,” Physical Review Letters 110, 170503 (2013), doi:10.1103/PhysRevLett.110.170503, arXiv:1206.1609.
• B. Eastin and E. Knill, “Restrictions on transversal encoded quantum gate sets,” Physical Review Letters 102, 110502 (2009), doi:10.1103/PhysRevLett.102.110502, arXiv:0811.4262.
• D. Gottesman and I. L. Chuang, “Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations,” Nature 402, 390–393 (1999), doi:10.1038/46503, arXiv:quant-ph/9908010.
• C. Vuillot, L. Lao, B. Criger, C. García Almudéver, K. Bertels, and B. M. Terhal, “Code deformation and lattice surgery are gauge fixing,” New Journal of Physics 21, 033028 (2019), doi:10.1088/1367-2630/ab0199, arXiv:1810.10037.
• T. J. Yoder, R. Takagi, and I. L. Chuang, “Universal fault-tolerant gates on concatenated stabilizer codes,” Physical Review X 6, 031039 (2016), doi:10.1103/PhysRevX.6.031039, arXiv:1603.03948.