Errors, syndromes, and the surface code

Real qubits decohere. Two effects dominate.

• Bit-flip ($X$) errors — the qubit's $|0\rangle$ component swaps with $|1\rangle$.
• Phase-flip ($Z$) errors — the qubit's relative phase between $|0\rangle$ and $|1\rangle$ changes sign.

Any single-qubit error can be expressed as a combination of $I$, $X$, $Y = iXZ$, and $Z$ (the four Pauli operators). Quantum noise theorems show that if you can correct $X$ and $Z$ errors on every qubit, you can correct arbitrary single-qubit errors.

The complication: classical error correction relies on copying the bit (e.g., transmit it three times, majority-vote). The no-cloning theorem from the first lesson rules out direct duplication of an unknown quantum state. Quantum error correction has to detect and undo errors without copying the qubit's amplitudes.

The solution is to encode the qubit into a larger system in a way that errors leave a detectable trace without exposing the encoded state itself.

The simplest quantum code corrects bit-flip errors using three physical qubits per logical qubit.

Encoding:

$|0_L\rangle = |000\rangle, \quad |1_L\rangle = |111\rangle.$

A superposition $\alpha|0\rangle + \beta|1\rangle$ becomes $\alpha|000\rangle + \beta|111\rangle$.

Detecting an error without measuring the encoded state: measure two parities — the parity of qubits 1 and 2, and the parity of qubits 2 and 3.

• Both parities even: no error (or three flips, undetectable).
• First parity odd, second even: qubit 1 flipped.
• Both parities odd: qubit 2 flipped.
• First parity even, second odd: qubit 3 flipped.

The parity measurements do not reveal $\alpha$ or $\beta$ — they only reveal the syndrome (the error pattern). Knowing the syndrome, the decoder applies the appropriate $X$ to undo the error, restoring the encoded state. This is the basic move of quantum error correction: extract error information via stabilizer-like measurements that commute with the logical operators.

This code corrects $X$ errors only. A separate three-qubit code corrects $Z$ errors. Combining them yields nine qubits and corrects both — Shor's original code.

Generalizing the repetition example: a stabilizer code is defined by a set of commuting Pauli operators (its stabilizers). The encoded subspace is the simultaneous +1 eigenspace of all stabilizers.

For the three-qubit code, the two stabilizers are $Z_1 Z_2$ and $Z_2 Z_3$ (the parities). The encoded states $|000\rangle$ and $|111\rangle$ satisfy $Z_1 Z_2 |\psi\rangle = +|\psi\rangle$ and $Z_2 Z_3 |\psi\rangle = +|\psi\rangle$.

An error $X_i$ acting on qubit $i$ anti-commutes with the stabilizers that touch qubit $i$. Measuring the stabilizers returns $-1$ for each one that anti-commutes with the error — the syndrome.

Key structural property. Stabilizer measurements commute with the logical operators (and with the encoded state itself), so they reveal error information without collapsing the encoded superposition. This is the precise mathematical reason no-cloning does not block error correction: the code does not copy the state; it detects errors through commutator structure.

Almost all practical quantum error-correcting codes — repetition, Shor, Steane, surface, color, LDPC — are stabilizer codes. The differences are in which stabilizers, what error-correction distance they achieve, and what physical layout they require.

The surface code arranges physical qubits on a 2D grid and defines stabilizers from local 4-qubit operators (plaquette terms). Two types of stabilizers — $X$-type and $Z$-type — alternate across the grid like a checkerboard.

The code parameters depend on the grid size $d$ (the code distance):

• Physical qubits per logical qubit: roughly $d^2$ for one type of grid; with ancilla qubits for syndrome extraction, the total is roughly $2d^2$.
• Errors corrected: up to $\lfloor (d-1)/2 \rfloor$ on any single round.
• All stabilizers are local: only 4-qubit operators on nearest-neighbor qubits. This matches naturally onto planar hardware layouts.

Why the surface code is the leading approach.

• The 4-qubit local interactions match what nearest-neighbor-connectivity hardware can implement.
• The threshold for fault tolerance is favorable (~1% per physical gate, well above the threshold of many codes).
• Decoding is tractable (minimum-weight perfect matching on a 2D graph).
• Logical operations can be implemented via lattice surgery, which scales naturally.

The price is the qubit overhead. A useful fault-tolerant logical qubit at $d = 25$ requires roughly $1250$ physical qubits per logical qubit, with additional overhead for ancilla qubits and magic-state distillation. Useful algorithms requiring hundreds or thousands of logical qubits therefore project to millions of physical qubits — the regime current hardware does not yet reach.

The central bookkeeping in fault-tolerant quantum computation is the conversion from physical to logical qubits.

For the surface code at distance $d$ with physical error rate $p$, the logical error rate per cycle scales (in the regime where the code suppresses errors) as

$p_L \approx A \cdot (p / p_{th})^{(d+1)/2}$

where $p_{th}$ is the threshold error rate (around $1\%$ for the surface code) and $A$ is a code-dependent constant. The exponential suppression is the engine: doubling $d$ does not double the protection — it raises it to a higher power.

The trade-off: each unit of code distance costs $O(d^2)$ physical qubits and corresponding control overhead. The practical question becomes:

• What physical error rate $p$ can the hardware achieve?
• What logical error rate $p_L$ does the target algorithm require?
• What code distance $d$ satisfies $p_L$ given $p$?
• How many physical qubits does that $d$ cost?

For algorithms like Shor's at cryptographically relevant problem sizes, the answers point at physical-qubit counts in the millions. The combination of physical-qubit improvements (lower $p$), code optimizations (smaller $A$, better codes), and algorithm refinements (less demanding $p_L$) all attack this overhead from different directions.

The threshold theorem, proved in various forms by Aharonov, Ben-Or, Kitaev, Knill, Laflamme, and others in the late 1990s, states:

If the physical error rate per gate is below a threshold $p_{th}$, then arbitrarily long quantum computations can be performed with arbitrarily low logical error rate, using overhead that grows polynomially in the inverse logical error rate.

The threshold depends on the code, the noise model, and the assumptions about how independently errors occur. For the surface code under realistic noise models, the threshold is in the range of $0.5\%$ to $1\%$ per physical gate.

The theorem is structurally important for two reasons.

• It establishes feasibility. If hardware can stay below threshold, the path to large fault-tolerant computation exists in principle without further conceptual breakthroughs.
• It bounds expectations. Above threshold, no amount of code overhead helps; logical errors accumulate faster than the code can correct them. Below threshold, overhead is polynomial in problem size, which is large but tractable.

Many experimental groups have reported physical gate fidelities corresponding to error rates approaching or below the surface-code threshold. Sustained below-threshold operation across many qubits and many gates is a separate engineering achievement and remains the central near-term goal.

The surface code has a structural asymmetry between Clifford and non-Clifford gates.

• Clifford gates ($H$, $S$, CNOT) on logical qubits can be implemented transversally in the surface code: applied bit-by-bit to the underlying physical qubits. They are 'cheap' in the sense of needing no additional resource overhead.
• Non-Clifford gates (e.g., $T$) cannot be implemented transversally without breaking the code's protection. The standard workaround is magic-state distillation: prepare special resource states (magic states) using a many-physical-qubit distillation process, then consume them to implement $T$ gates via gate teleportation.

Magic-state distillation produces $T$ states with logical error rate suppressed by a power of the physical error rate. Each distillation step costs many physical qubits and many gates. For demanding algorithms, magic-state distillation dominates the resource budget — sometimes by a factor of 10–100 over the surface-code error correction proper.

The structural lesson: error correction does not give 'every gate for free.' Clifford gates inherit the code's protection naturally; non-Clifford gates require an additional resource pipeline whose cost shapes the total physical-qubit count of fault-tolerant algorithm execution.

When an experiment claims a result in error correction, the structural questions to ask are:

• Below threshold? Was the physical error rate below the code's threshold during the experiment? This is necessary but not sufficient for useful error correction.
• Logical error rate suppressed? Did the logical error rate decrease as the code distance increased? This is the operational signature of below-threshold operation.
• Round count? Was the suppression maintained over many rounds of error correction, or only over a single round? Sustained logical-qubit fidelity over hundreds or thousands of cycles is the regime that matters for useful algorithms.
• Logical operations? Were non-trivial operations performed on the logical qubit (gates, measurements in different bases), or only memory storage?
• Magic states? Was non-Clifford computation demonstrated, or only Clifford operations? Useful fault-tolerant computation requires both.
• Scale? How many physical qubits per logical qubit? How many logical qubits in total?

A result that shows below-threshold suppression on one logical qubit across many rounds is a milestone on the path to fault tolerance. A result that demonstrates many logical qubits doing useful computation with non-Clifford gates is a different and later milestone. Both have appeared in the literature; precise comparisons require reading the protocol details closely.

The next lesson moves from the hardware-and-error-correction infrastructure to the algorithmic side: which problems have known quantum speedups, and what 'speedup' really claims.