Starting point: Chapters 1–17; physical concepts and approximations are introduced as needed.
Anchor example: Repeated parity measurements with imperfect data and auxiliaries.
This lesson includes explanations, worked examples, and problems with solutions. Advanced results whose proofs are outside the chapter are identified explicitly.
We have met codes that detect errors: the three-bit repetition code, the binomial code in an oscillator, the grid code. Each relies on measurements that reveal an error without revealing the encoded information. On hardware, those measurements are themselves circuits made of noisy gates and noisy readouts. Can a device check for errors without adding more errors than it removes?
We first build a parity check from two CNOTs and an auxiliary qubit, and see why it preserves superpositions. Because the check can itself fail, we repeat it, and asking how errors move through CNOTs shows how one fault can spread. Code distance then says how many errors a code can correct, and asking how logical gates and special auxiliary states are supplied gives their cost in space and time. Finally, leakage, correlations, and latency shape real performance, and asking when a larger code actually helps leads to the threshold and the overhead of a long computation.
Our first question is how a device can learn whether two bits agree without learning either bit.
18.1 Syndrome Extraction
A parity measurement should reveal whether two data bits agree without revealing either bit. How can gates and one auxiliary qubit do that, and what happens when they fail? Two CNOTs copy the parity onto the auxiliary, and linearity shows that superpositions within each parity sector survive. Repeating the check guards against faulty reports, but CNOTs can also spread a single fault to several qubits.
18.1.1 Physical parity circuits
How can a device learn whether two bits agree without learning either? Prepare an auxiliary qubit in \(\ket0\) and apply two CNOTs, with data qubits \(x\) and \(y\) as controls and the auxiliary as target. The first writes \(x\) onto the auxiliary, and the second adds \(y\) modulo two, leaving \(\ket{x,y,x\oplus y}\). Measuring the auxiliary therefore records whether \(x\) and \(y\) agree, without measuring either one.
What happens to a superposition? By linearity, \(a\ket{00}+b\ket{11}\) leaves the auxiliary in \(\ket0\), so its coherence survives. The odd sector \(a\ket{01}+b\ket{10}\) leaves the auxiliary in \(\ket1\). A superposition across the two sectors is projected onto one of them, which is what a parity check should do. The recorded bit is the eigenvalue of \(Z_1Z_2\), with auxiliary bit 0 for \(+1\) and 1 for \(-1\). The ideal circuit is the specification that a physical implementation must meet.
18.1.2 Measurement faults and repetition
If a reported parity changes between rounds, did the data change? Not necessarily: one of the two reports may have been wrong. Repeating the check gives a history that helps tell these apart. For three independent reports of a constant parity, each wrong with probability \(e\), a majority vote fails with probability \(3e^2(1-e)+e^3\), the repetition-code formula again. At \(e=0.01\) that is 0.000298.
Is repetition enough? The constant-parity assumption is strong, since data errors can occur during the three measurements. Errors also move through gates. How does an X error on the control of a CNOT move? Check on basis states: \(\mathrm{CNOT}\,(X\otimes I)\,\mathrm{CNOT}\ket{c,t}=\ket{c\oplus1,t\oplus1}\), so \(\mathrm{CNOT}\,X_1\,\mathrm{CNOT}=X_1X_2\). An X on the control before the gate equals an X on both qubits after it. In the same way \(\mathrm{CNOT}\,Z_2\,\mathrm{CNOT}\ket{c,t}=(-1)^{c\oplus t}\ket{c,t}\), so a Z on the target spreads to both. An auxiliary fault partway through a check can therefore reach more than one data qubit, depending on the order of the gates. Repetition alone does not make a check fault-tolerant.
The ideal circuit preserves coherence within each parity sector. Two data wires and one auxiliary wire are shown; gate faults and repeated noisy measurements require a separate analysis.
Problem 18.1. What happens when the parity circuit receives (|00⟩ + |11⟩)/√2?
Worked solution
Both components put the auxiliary in zero, so its measurement leaves their superposition intact in the ideal circuit. Measuring the two data qubits individually would instead reveal which component was present.
18.2 Logical Operations
Checks tell us that errors occurred; a code must also decide which errors to undo, and it must let us compute. How many errors can a code correct, and how are logical gates performed? Code distance bounds the correctable errors when syndromes are perfect. Logical gates and the auxiliary states some of them consume then cost cycles and space.
18.2.1 Code distance and decoding
How many errors can a code correct? Call a Pauli product a logical Pauli if it changes the encoded information while leaving every check unchanged. The code distance \(d\) is the smallest number of qubits such a nontrivial operator acts on. Suppose two candidate errors each act on at most \(t\) qubits. If both produce the same syndrome, their product leaves every check unchanged and acts on at most \(2t\) qubits. When \(2t<d\), that product cannot be a nontrivial logical Pauli, so undoing either candidate gives the same encoded state. A distance-\(d\) code therefore corrects up to \(\lfloor(d-1)/2\rfloor\) arbitrary qubit errors, given ideal syndromes and a suitable recovery.
What changes when the syndromes are noisy? The decoder must then interpret changes across rounds, in space and time together, rather than trust one set of readouts. A single faulty entangling gate can also create several data errors, so faulty circuit locations are not the same as independent errors on the final qubits. The code, the schedule, the noise, and the decoder together decide the logical performance.
18.2.2 Gates and auxiliary states
How do we compute on encoded qubits? A logical gate must change the encoded state while keeping faults under control. A transversal gate acts separately on corresponding physical qubits of the code blocks, so a fault on one qubit cannot spread within its block. Other constructions move code boundaries, or measure joint logical observables between neighbouring patches of code. These procedures take cycles and temporary physical space.
What do non-Clifford gates cost? Some constructions consume a specially prepared auxiliary state for each such gate. A dedicated region that produces these states is called a factory. If a factory delivers one usable state every \(F\) cycles but the algorithm requests one every \(A\) cycles, then when \(F>A\) the computation must slow down or add factories. An ideal gate count that omits this production misses a possible bottleneck. We do not derive a universal fault-tolerant gate set here, only the accounting that any chosen construction must satisfy.
Problem 18.2. How many arbitrary physical-qubit errors can a distance-5 code correct with perfect syndrome information?
Worked solution
At most floor((5−1)/2) = 2. This does not mean that every pair of faulty circuit locations is harmless; faults can propagate to multiple data qubits.
18.3 Hardware Requirements
Distance counts independent Pauli errors, but hardware errors are not always independent or Pauli. Which hardware effects break the counting, and when does a larger code help at all? Leakage and shared failures produce errors that are correlated in time and space, and decoding takes time. Comparing codes of different distance then defines the threshold and sets the overhead of a long computation.
18.3.1 Leakage, correlation, and latency
What does a leaked qubit do to the checks? Suppose a leaked data qubit persists for many rounds and interacts with each fresh auxiliary. The resulting syndrome faults are strongly correlated in time, even though the leakage event itself was rare. Likewise, one failure of a shared control can affect many qubits in the same cycle. A fit with independent Pauli errors can miss both mechanisms.
So repeated extraction is measured in its full simultaneous context, with reset, leakage removal, readout crosstalk, and decoding deadlines included. A pipelined decoder can process checks continuously while correction is delayed, but operations that need a resolved result still wait for it. The useful figure is the logical error per cycle together with the cycle duration, since trading one against the other changes the reliability per unit of elapsed time.
18.3.2 Thresholds and overhead
When does a larger code help? A larger distance needs more qubits and more gates, hence more places where faults can occur. It also needs more faults before correction fails. If the physical error rate \(p\) is low, the second effect wins and the logical error falls as \(d\) grows; if \(p\) is high, the first wins and it rises. The crossover value \(p_{\rm th}\) is called the threshold.
How fast does the logical error fall below threshold? A distance-\(d\) code with \(d\) odd fails only when about \((d+1)/2\) faults occur together. This motivates the fit \(p_L\simeq A(p/p_{\rm th})^{(d+1)/2}\), where \(A\) and \(p_{\rm th}\) summarize the code, circuit, and decoder. It is a fitted model for a local-error regime, not a theorem.
What does a long computation require? With \(A=0.1\) and \(p/p_{\rm th}=0.1\), raising the distance from three to five changes the estimate from \(10^{-3}\) to \(10^{-4}\). If \(K\) logical cycles fail independently with probability \(p_L\), keeping the total failure below \(\epsilon\) requires approximately \(Kp_L\le\epsilon\) when errors are small. With \(K=10{,}000\) and \(\epsilon=0.01\), the target is about \(10^{-6}\) per cycle. So a good single-cycle number can still imply a large overhead in distance, and therefore in qubits.
The illustrative fit A(p/pth)^((d+1)/2), with A = 0.1, improves with distance only below its assumed threshold. It is not a universal theorem or a prediction from one average gate fidelity.
Problem 18.3. Use \(A=0.1\), \(p/p_{\rm th}=0.1\). Compare distances 3 and 5 in the illustrative fit.
Worked solution
The estimates are \(10^{-3}\) and \(10^{-4}\). Increasing distance improves this model at the cost of more qubits and operations; a real estimate must validate its noise assumptions.
We can now count every cost a computation incurs, from preparation through correction. How, then, should one processor be compared with another?
Worked model check. A computation has 10,000 logical cycles and a 1% total-failure budget. What approximate per-cycle logical target follows from an independent small-error model?
Worked solution
\(p_L\lesssim0.01/10000=10^{-6}\). The exact constraint is \(p_L\leq1-0.99^{1/10000}\); correlated failures require another analysis.
Fault-tolerant operation requires every physical component—two-qubit gates, mid-circuit syndrome readout, ancilla reset, and leakage removal—to remain below the code’s threshold error rate.
Repeated stabilizer extraction must complete within a single code cycle faster than logical errors accumulate, while classical decoders process syndrome streams without falling behind.
Correlated cosmic-ray bursts, leakage out of the computational subspace, and erasure errors require dedicated hardware mitigation and erasure-aware decoding.
Questions and worked problems
These exercises draw on the whole chapter. Attempt each question before opening a hint, explain your reasoning, then compare it with the worked solution.
How many arbitrary physical-qubit errors can a distance-\(7\) code correct with perfect syndrome information, and how many can it detect? Why must the corrected number be less than half the distance?
Hint 1
Correctable: \(\lfloor(d-1)/2\rfloor\).
Hint 2
Two candidate errors of weight \(t\) combine to weight at most \(2t\).
Worked solution
It corrects \(3\) errors and detects up to \(6\). If two different errors each of weight at most \(t\) gave the same syndrome, their product, of weight at most \(2t\), would be undetectable; for \(2t<d\) that product cannot be a nontrivial logical operator, so the decoder can identify the error. At \(t=4\), two weight-\(4\) errors could combine into a weight-\(8\ge7\) logical operator and be confused.
A constant parity is reported five times, each report wrong independently with probability \(e=0.01\). Find the probability that a majority vote is wrong. Compare with three reports.
Hint 1
Majority of five fails with three or more wrong reports.
Hint 2
Three reports gave \(2.98\times10^{-4}\).
Worked solution
\(10e^3(1-e)^2+5e^4(1-e)+e^5\approx9.9\times10^{-6}\), compared with \(2.98\times10^{-4}\) for three reports. Two extra rounds cut the voting error thirtyfold, but only if the parity stays constant: data errors during the extra rounds, and the extra time for errors to accumulate, are the real costs.
A magic-state factory delivers one state every \(F=50\) cycles, and the algorithm consumes one every \(A=20\) cycles. How many factories are needed to keep up? If only one is available, by what factor does the computation slow?
Hint 1
Factories needed: \(\lceil F/A\rceil\).
Hint 2
Slowdown with one factory: \(F/A\).
Worked solution
\(\lceil50/20\rceil=3\) factories. With one, the computation waits \(2.5\) times longer for each state, so the factory-limited part runs \(2.5\) times slower. Space for factories (more physical qubits) and time (slower execution) trade against each other in a resource estimate.
In a \(Z_1Z_2\) parity check, CNOTs run from data qubit 1 to the auxiliary, then from data qubit 2 to the auxiliary. (a) An \(X\) error hits the auxiliary between the CNOTs. What happens to the data and to the measured result? (b) A \(Z\) error hits the auxiliary between the CNOTs. Using the rule that a \(Z\) on a CNOT target propagates to the control, what happens? (c) What does this imply about auxiliary faults?
Hint 1
An \(X\) on the target is not copied to the control.
Hint 2
A \(Z\) on the target before the second CNOT becomes \(Z\) on data qubit 2 and the auxiliary.
Worked solution
(a) An \(X\) on the target passes through the second CNOT unchanged and flips the measured parity: a measurement error, with no damage to the data. (b) A \(Z\) on the auxiliary before the second CNOT propagates to its control, so data qubit 2 acquires a \(Z\) error, while the auxiliary’s \(Z\) does not affect its \(Z\)-basis readout. (c) One fault on the auxiliary can become an error on a data qubit, and in longer checks one auxiliary fault can spread to several data qubits. The check order and the code must be chosen so that such spread errors remain correctable.
Use the fit \(p_L\approx A(p/p_{\rm th})^{(d+1)/2}\) with \(A=0.1\) and \(p/p_{\rm th}=0.2\). (a) Evaluate \(p_L\) for \(d=3,5,7\). (b) Find the smallest odd \(d\) that reaches \(p_L\le10^{-6}\). (c) If a code patch needs about \(2d^2\) physical qubits, how many does one logical qubit need?
Hint 1
\((d+1)/2\ge\log(10^{-5})/\log(0.2)\approx7.15\).
Hint 2
\(2\times15^2\).
Worked solution
(a) \(d=3\): \(4\times10^{-3}\); \(d=5\): \(8\times10^{-4}\); \(d=7\): \(1.6\times10^{-4}\). (b) Need \(0.2^{(d+1)/2}\le10^{-5}\), so \((d+1)/2\ge7.15\), giving \(d=15\) (exponent \(8\)): \(p_L\approx2.6\times10^{-7}\). (c) About \(2\times225=450\) physical qubits per logical qubit. Being only five times below threshold makes the overhead large; at \(p/p_{\rm th}=0.1\) the same target needs \(d=9\).
A repeated parity check reports, over five rounds, either (a) \(0,0,1,0,0\) or (b) \(0,0,1,1,1\). Measurement errors occur with probability \(e=0.01\) per report and data flips with probability \(p=0.001\) per round. For each history, compare the probability of the two simplest explanations, and decide what happened.
Hint 1
(a): one wrong report, or a data flip followed by a flip back.
Hint 2
(b): a data flip, or three wrong reports in a row.
Worked solution
(a) One wrong report has probability about \(e=10^{-2}\); two data flips (at round 3 and back at round 4) about \(p^2=10^{-6}\). The isolated flip is almost certainly a measurement error. (b) A single data flip before round 3 has probability about \(p=10^{-3}\); three consecutive wrong reports about \(e^3=10^{-6}\). It was almost certainly a data error. Decoders reason over the history of reports in this way, treating space and time together.
A data qubit leaks and stays leaked for \(20\) rounds. Each round, its two adjacent parity checks give random results while it is leaked. (a) Roughly how many changes (detection events) do these two checks show over the \(20\) rounds? (b) Why does this pattern confuse a decoder built for independent Pauli errors? (c) What hardware feature limits the damage?
Hint 1
A random result differs from the previous one with probability \(\frac12\).
Hint 2
Expected changes per check \(\approx\frac12\times20\).
Worked solution
(a) Each check changes with probability about \(\frac12\) per round, so about \(10\) detection events per check, \(20\) in total, from one physical event. (b) A decoder expecting independent errors interprets this cluster as many separate errors and may apply a large, wrong correction, or exceed the correctable weight, causing a logical error. (c) Leakage-reduction units or periodic resets return leaked qubits to the computational space within a round or two, converting a long correlated burst into a short, correctable one.
A student argues: “A distance-\(5\) code corrects any two errors, so any two faulty gates in a syndrome cycle are corrected.” Using the propagation result from the worked problem above, explain why this can fail, and how codes and circuits are designed to prevent it.
Hint 1
A single auxiliary fault can become an error on a data qubit.
Hint 2
A weight-four check can spread one fault to two data qubits.
Worked solution
A single fault in an extraction circuit can produce errors on more than one data qubit, for example a \(Z\) on an auxiliary midway through a weight-four check spreads to the remaining controls. Then two faulty gates can produce three or four data errors, beyond what distance \(5\) corrects. Fault-tolerant designs order the CNOTs so that spread errors align harmlessly with the code’s structure, use flag qubits to detect dangerous spreads, or choose codes whose distance accounts for such “hook” errors.
A computation runs \(K=10^8\) logical cycles with a total failure budget of \(1\%\). (a) Find the per-cycle logical error target. (b) Using \(p_L\approx0.1(p/p_{\rm th})^{(d+1)/2}\) with \(p/p_{\rm th}=0.1\), find the smallest odd distance that meets it. (c) How does the required distance grow with the length of the computation?
Hint 1
\(Kp_L\le0.01\).
Hint 2
\(0.1\times0.1^{(d+1)/2}\le10^{-10}\).
Worked solution
(a) \(p_L\le10^{-10}\). (b) \(0.1^{(d+1)/2}\le10^{-9}\) needs \((d+1)/2\ge9\), so \(d=17\). (c) Because \(p_L\) falls exponentially in \(d\), the required distance grows only logarithmically with \(K\): each factor of ten in computation length adds about two to the distance at this noise level. Long computations are affordable if the hardware is well below threshold.
A transversal CNOT between two code blocks applies a physical CNOT between qubit \(i\) of the first block and qubit \(i\) of the second, for every \(i\). (a) Show that a single faulty physical CNOT produces errors on at most one qubit in each block. (b) Why does this keep a distance-\(3\) code correctable after the gate? (c) Contrast with a circuit in which one physical qubit of block 1 interacts with all qubits of block 2.
Hint 1
Each physical CNOT touches one qubit per block.
Hint 2
Errors on one qubit per block are within the correction capacity of a distance-\(3\) code.
Worked solution
(a) Each physical CNOT acts on qubit \(i\) of each block only, so even if it fails arbitrarily, it damages at most qubit \(i\) in block 1 and qubit \(i\) in block 2. (b) Each block then has at most one error, which a distance-\(3\) code corrects. (c) If one qubit interacted with every qubit of the other block, a single fault on it could spread to many qubits of block 2 and overwhelm the code. Transversality bounds fault propagation by construction, which is why transversal gates are prized despite being available only for restricted gate sets.
