<!-- Source: https://web3-lab.annaburd.me/how-quantum-computing-works/quantum-error-correction/ -->

# Foundations of quantum error correction

How a noisy quantum computer can still compute: error-correcting codes, stabilizers,
CSS, toric, surface and color codes, and fault tolerance up to the threshold theorem.

## Quantum error correction

Quantum computers are highly susceptible to errors in two distinct ways.

- Unwanted interactions with the environment. No physical system is perfectly isolated. A qubit interacts with its surroundings and can become entangled with them. When the qubit is considered on its own, its state is generally a mixed state rather than the state that was prepared. This loss of coherence is called decoherence.
- Limited accuracy of operations. A quantum gate is an ideal unitary transformation in the mathematical model, but in hardware it is implemented by a physical control pulse with finite precision. The operation can therefore deviate slightly from the ideal gate. Over a long circuit, these small imperfections accumulate.

Classical error correction has many important applications, but it is generally unnecessary for classical computation itself. A classical bit is represented by one of two well-separated ranges of physical states, such as low and high voltage. Small deviations within one range are tolerated, and digital gates restore the signal toward one of the two valid levels.

A qubit has no comparable gap between valid states. Its state can vary continuously, and every nearby point represents a legitimate quantum state. A small error therefore does not automatically get corrected back to the intended state.

A classical bit

Only the two ends count as values. A voltage that has drifted within a band is read as that level and pushed back to it, every time it passes through a gate.

A qubit

Every point along the same continuum represents a valid state. A drift produces a different state, with no range that automatically restores it to the intended one.

For large-scale quantum computing, error correction is widely regarded as essential for containing errors as computations grow.

Classical repetition codes

Repetition codes are among the simplest error-correcting codes. The idea is straightforward: repeat each bit several times. For example, a three-bit repetition code can correct any single bit flip within the block. However if two bits flip, the majority is wrong and decoding produces the wrong bit.

| Encoding | Decoding |
| --- | --- |
| $0 \mapsto 000$ | $abc \mapsto \operatorname{majority}(a, b, c)$ |
| $1 \mapsto 111$ |  |

Suppose each bit passes through a binary symmetric channel that flips it with probability $p$, independently of the others. Decoding fails when two or all three bits flip, with probability. For $p < 1/2$, this is smaller than $p$, so the encoded block is less likely to fail than a single bit.

Flip probability p0.15

Encoded

Received

???

Majority

?

The improvement comes at a cost: three physical bits are used to encode one logical bit. Longer repetition blocks push the failure probability lower, making errors rare enough for reliable computation, but never eliminating the possibility of failure.

Repetition code for qubits

The three-bit repetition code can also encode a qubit:

$$
\alpha|0\rangle + \beta|1\rangle \;\mapsto\; \alpha|000\rangle + \beta|111\rangle
$$

Nothing here is being copied. The three qubits on the right are entangled with one another, rather than being three separate qubits in the state $\alpha|0\rangle + \beta|1\rangle$, which cannot be produced by copying an unknown quantum state. The amplitudes $\alpha$ and $\beta$ belong to the block as a whole.

This circuit performs the encoding:

$$
\alpha|0\rangle + \beta|1\rangle
$$

$$
|0\rangle
$$

$$
\alpha|010\rangle + \beta|101\rangle
$$

Qubit 2 has flipped

Correctable, recover the original state α|000⟩ + β|111⟩.

The classical approach for code recovery is to inspect the three bits and take the majority. That cannot be done here. Measuring the three qubits would collapse the superposition, producing $010$ or $101$ and destroying the information carried by $\alpha$ and $\beta$. The state would be read at the cost of the state.

What is needed is the location of the flip, without learning anything about the encoded state. The two terms $|010\rangle$ and $|101\rangle$ have the same pattern of agreement and disagreement between neighbouring qubits: qubits 1 and 2 are different, and qubits 2 and 3 are different. These two comparisons are called parity checks. They give the same two-bit result for both terms, so the result reveals the location of the flip without revealing whether the state was $|000\rangle$ or $|111\rangle$, and therefore without revealing $\alpha$ or $\beta$.

Two extra qubits record these parity checks. Measuring them gives the two-bit syndrome.

$$
\alpha|000\rangle + \beta|111\rangle
$$

$$
|0\rangle
$$

$$
\alpha|000\rangle + \beta|111\rangle
$$

Qubit 2 has flipped

Syndrome 11 identifies the error without touching the superposition, and X restores the qubit.

| State | Syndrome | Correction |
| --- | --- | --- |
| $\alpha\|000\rangle + \beta\|111\rangle$ | 00 | $I \otimes I \otimes I$ |
| $\alpha\|100\rangle + \beta\|011\rangle$ | 10 | $X \otimes I \otimes I$ |
| $\alpha\|010\rangle + \beta\|101\rangle$ | 11 | $I \otimes X \otimes I$ |
| $\alpha\|001\rangle + \beta\|110\rangle$ | 01 | $I \otimes I \otimes X$ |

The code corrects a single $X$ error, but its protection is limited. Some error patterns produce a misleading syndrome and draw the wrong correction, and others produce no syndrome at all and pass through undetected. The classical repetition code has the same limit: a correction is only ever as good as the errors the code can tell apart.

Phase-flip errors

Bit flips are not the only errors a qubit can suffer. A phase-flip error is described by the $Z$ gate: it leaves $|0\rangle$ unchanged but sends $|1\rangle$ to $-|1\rangle$. The bit values stay the same, so the error is invisible in the computational basis. It becomes visible only when the two branches interfere.

$$
\alpha|0\rangle + \beta|1\rangle
$$

$$
|0\rangle
$$

$$
\alpha|000\rangle - \beta|111\rangle
$$

One phase flip

The block picks up a minus sign, while every qubit keeps its original bit value.

A $Z$ error changes a phase and nothing else, leaving every qubit value exactly as it was. The parity checks compare values, so they read the same result before and after the error and report nothing.

Fortunately, a modified version of the repetition code can detect phase flips. The idea is to encode the logical qubit in the plus-minus basis, where a $Z$ error acts like an ordinary bit flip, exchanging $|{+}\rangle$ and $|{-}\rangle$.

$$
\alpha|0\rangle + \beta|1\rangle
$$

$$
|0\rangle
$$

$$
\alpha|{+}{-}{+}\rangle + \beta|{-}{+}{-}\rangle
$$

Qubit 2 has flipped

In this basis, Z exchanges |+⟩ and |−⟩ on that qubit, so it acts as an ordinary flip.

The detection circuit is modified in the same way. Hadamards before and after the parity checks put the data qubits in the plus-minus basis, where a phase flip becomes an ordinary flip. The same syndrome can then locate it just as it locates a bit flip.

$$
\alpha|{+}{+}{+}\rangle + \beta|{-}{-}{-}\rangle
$$

$$
|0\rangle
$$

$$
\alpha|{+}{+}{+}\rangle + \beta|{-}{-}{-}\rangle
$$

Syndrome 11

The flip is located on qubit 2, and a Z on that qubit undoes it.

| State | Syndrome | Correction |
| --- | --- | --- |
| $\alpha\|{+}{+}{+}\rangle + \beta\|{-}{-}{-}\rangle$ | 00 | $I \otimes I \otimes I$ |
| $\alpha\|{-}{+}{+}\rangle + \beta\|{+}{-}{-}\rangle$ | 10 | $Z \otimes I \otimes I$ |
| $\alpha\|{+}{-}{+}\rangle + \beta\|{-}{+}{-}\rangle$ | 11 | $I \otimes Z \otimes I$ |
| $\alpha\|{+}{+}{-}\rangle + \beta\|{-}{-}{+}\rangle$ | 01 | $I \otimes I \otimes Z$ |

The same measurement can be implemented with fewer Hadamard gates. Prepare the ancillas in $|{+}\rangle$, control from them onto the data qubits, and measure the ancillas in the plus-minus basis.

$$
|+\rangle
$$

The code corrects a single $Z$ error, but its protection is limited. Multiple phase flips can produce a misleading syndrome and lead to the wrong correction, while bit flips produce no phase-flip syndrome and pass through undetected. Each version of the repetition code can only correct the errors it can distinguish.

The nine-qubit Shor code

Neither repetition code is enough on its own: one corrects bit flips, the other phase flips. The nine-qubit Shor code combines both by concatenation. First, the logical qubit is encoded by the three-qubit phase-flip code. Then each of those three qubits is encoded again by the three-qubit bit-flip code, giving three blocks of three:

$$
|0\rangle \;\mapsto\; \tfrac{1}{2\sqrt{2}}\,(|000\rangle + |111\rangle) \otimes (|000\rangle + |111\rangle) \otimes (|000\rangle + |111\rangle)
$$

$$
|1\rangle \;\mapsto\; \tfrac{1}{2\sqrt{2}}\,(|000\rangle - |111\rangle) \otimes (|000\rangle - |111\rangle) \otimes (|000\rangle - |111\rangle)
$$

X error

Z error

X correction

$$
|\psi\rangle
$$

$$
|0\rangle
$$

Block 1

Qubit 2 flipped

The inner code locates it and puts it back.

Block 2

No bit flip

Block 3

No bit flip

A Z in this block is invisible to the inner code and is left to the outer one.

sX=11 → q2

sX=00

A qubit can have both errors at once: an $X$ and a $Z$ can act on the same wire. Their order does not affect any observable outcome, since $XZ = -ZX$ and the overall minus sign has no physical effect. The error can therefore be described simply as an $X$ and a $Z$ acting on that qubit:

A bit flip has already been located and corrected within its block. A phase flip is different. It leaves every qubit’s computational-basis value unchanged, so none of the block’s parity checks change. The phase-flip component therefore remains undetected at this stage and must be handled by the outer code. To see what the outer code detects, it helps to see how a phase flip can be represented on the other side of a CNOT.

X and CNOT

Z and CNOT

The key point is that a phase flip on any one of the three physical qubits in a block is equivalent to a phase flip on the block’s qubit before encoding. The CNOT identities establish this equivalence, as the demo shows explicitly. Thus, from the outer code’s perspective, a phase flip on any qubit in a block is simply a phase flip of that block.

inner encoding

Z error

$$
|\psi\rangle
$$

$$
|0\rangle
$$

block 1

block 2

block 3

Everything to the right of the $\equiv$ is the three-qubit phase-flip code from the previous section. The equivalence means that the outer code can treat each three-qubit block as one qubit.

To correct the phase error, first undo the inner encoding so that each block becomes one qubit again. The outer syndrome can then be measured on those three qubits using the $|{+}\rangle$ ancilla circuit from the previous section. The syndrome identifies the block carrying the phase error, and once that block has been corrected the inner encoding is applied again.

encode

decode

outer syndrome

re-encode

error

$$
|\psi\rangle
$$

$$
|0\rangle
$$

$$
|+\rangle
$$

$$
0
$$

$$
1
$$

block 1

block 2

block 3

There is no need to undo the inner encoding first. The outer syndrome can be measured directly on the nine physical qubits, using the same $|{+}\rangle$ ancilla circuit with each control fanned out over all three qubits of a block. Each ancilla then checks the phase parity between a pair of blocks, touching six qubits in all. The two measurement results identify which block carries the phase flip, and since a phase flip on any of its qubits has the same effect, applying $Z$ to any one of the three corrects the error.

Also note that the two repairs are completely independent. The bit-flip correction reads only bit values and the phase-flip correction only relative phases, so neither is affected by the other. An $X$ leaves the phase syndrome unchanged, and a $Z$ leaves the bit syndrome unchanged. If a qubit carries both errors, each correction removes its own part, and the two can be applied in either order.

block phase checks

corrections

X errors

Z errors

$$
|\psi\rangle
$$

$$
|0\rangle
$$

$$
|+\rangle
$$

$$
0
$$

$$
1
$$

sX=11 → q2

sX=00

block 1

block 2

block 3

A single-qubit error has only four relevant forms: no error, an $X$, a $Z$, or both. Up to a global phase, the last case is the Pauli $Y = iXZ$, so these are simply $I$, $X$, $Y$, and $Z$. The two syndromes distinguish the four cases, while the two codes remove the bit-flip and phase-flip parts independently. That settles what the nine-qubit Shor code can correct. What remains is whether that protection is worth the cost when errors arrive at random, and what happens when an error falls outside these four cases.

Random errors

Start with the simplest noise model. Each of the nine qubits is struck independently with probability $p$, and a struck qubit suffers an $X$, a $Y$ or a $Z$. Encoding, syndrome measurement and correction are taken to be perfect. The question is whether the protection pays for itself, since the encoded qubit has nine physical qubits exposed to errors, where a bare qubit has only one.

The nine-qubit Shor code is guaranteed to recover the encoded qubit when at most one of its nine qubits is struck:

$$
\Pr(\text{at most one qubit struck}) = (1-p)^9 + 9p(1-p)^8
$$

For simplicity, cases with two or more errors are not counted. Some happen to be harmless, such as two $Z$ errors in the same block, but the nine-qubit code does not guarantee recovery in those cases. Leaving them out keeps the estimate conservative. A bare qubit comes through untouched with probability $1-p$, so the nine-qubit code comes out ahead when:

$$
(1-p)^9 + 9p(1-p)^8 > 1-p
$$

At an error rate of $p = 1.5\%$, for example, the nine-qubit code guarantees recovery in 99.24% of rounds, compared with 98.50% for a bare qubit. That is a gain of only 0.74 percentage points.

Error rate p1.50%

Guaranteed by the nine-qubit code99.24%

One bare qubit98.50%

Nine qubits after one round

?????????

Result

?

The two curves cross at $p \approx 3.2\%$. Below that rate, the nine-qubit code is ahead. Above it, the extra exposure costs more than error correction wins back. Even at its best, however, the advantage is small. The code can correct one struck qubit out of nine, so the extra redundancy only pays off when physical errors are already sufficiently rare. Rounds with two or more errors are left out entirely, and in some of them the correction only makes things worse: two bit flips in one block lead it to flip the third qubit as well.

Moreover, the model is deliberately very tidy. Every error is one of the three Pauli operators, but real noise need not look like that. A qubit may undergo a small continuous rotation or lose energy to its surroundings. Yet correcting $X$, $Y$, and $Z$ is enough to handle those more general errors.

Unitary errors

The random-error model picks $X$, $Y$, or $Z$ at random. A coherent disturbance is different: a stray field applies one continuous rotation, so before syndrome measurement no Pauli error has been classically selected. Instead, the resulting state contains several Pauli-error components at once.

Up to an unobservable global phase, every one-qubit unitary is a rotation through an angle $\theta$ about a unit axis $\vec n=(n_x,n_y,n_z)$, where $n_x^2+n_y^2+n_z^2=1$. Define the Pauli operator in that direction by $P_{\vec n}=n_xX+n_yY+n_zZ$. Because $P_{\vec n}^2=I$, its exponential separates into an identity part and a Pauli part:

$$
\begin{aligned}U(\vec n,\theta)&=e^{-i\theta P_{\vec n}/2}\\[6pt]&=\cos\tfrac{\theta}{2}\,I-i\sin\tfrac{\theta}{2}\,\bigl(n_xX+n_yY+n_zZ\bigr)\end{aligned}
$$

The same unitary is therefore a linear combination of the four Pauli operators:

$$
U=\alpha I+\beta X+\gamma Y+\delta Z
$$

Comparing this expansion with the rotation formula identifies each coefficient:

$$
\begin{aligned}\alpha&=\cos\tfrac{\theta}{2}\\[4pt]\beta&=-in_x\sin\tfrac{\theta}{2}\\[4pt]\gamma&=-in_y\sin\tfrac{\theta}{2}\\[4pt]\delta&=-in_z\sin\tfrac{\theta}{2}\end{aligned}
$$

To test the Shor code’s single-qubit guarantee, suppose this rotation acts on physical qubit $k$. Write $U_k$ for $U$ in position $k$ and the identity on the other eight qubits. The tensor product is linear in each position, so the Pauli expansion carries over term by term:

$$
\begin{aligned}U_k&=I^{\otimes(k-1)}\otimes U\otimes I^{\otimes(9-k)}\\[6pt]&=\alpha\,I^{\otimes9}+\beta\,X_k+\gamma\,Y_k+\delta\,Z_k\end{aligned}
$$

Applied to the encoded state $|\psi_L\rangle$, it produces four states of the full nine-qubit code:

$$
U_k|\psi_L\rangle=\alpha\,|\psi_L\rangle+\beta\,X_k|\psi_L\rangle+\gamma\,Y_k|\psi_L\rangle+\delta\,Z_k|\psi_L\rangle
$$

This is a superposition of four branches: the untouched codeword and the three single-qubit errors the Shor code already corrects. For this fixed qubit $k$, the four branches belong to distinct syndrome subspaces and are orthogonal, so their squared magnitudes are the four syndrome probabilities:

$$
\begin{aligned}p_I&=|\alpha|^2=\cos^2\tfrac{\theta}{2}\\[4pt]p_X&=|\beta|^2=n_x^2\sin^2\tfrac{\theta}{2}\\[4pt]p_Y&=|\gamma|^2=n_y^2\sin^2\tfrac{\theta}{2}\\[4pt]p_Z&=|\delta|^2=n_z^2\sin^2\tfrac{\theta}{2}\\[6pt]p_I+p_X+p_Y+p_Z&=1\end{aligned}
$$

The angle sets the total error weight $\sin^2(\theta/2)$, while the axis determines how that weight is split among $X$, $Y$, and $Z$. In the demo, the buttons set $\vec n$ and the slider sets $\theta$. The formula shows the resulting amplitudes, while the bars show the corresponding syndrome probabilities.

axis nrotation θ

Rotation axis

Rotation angle θ72°

$$
U_k|\psi_L\rangle = 0.809\,|\psi_L\rangle - 0.339i\,X_k|\psi_L\rangle - 0.339i\,Y_k|\psi_L\rangle - 0.339i\,Z_k|\psi_L\rangle
$$

| Branch | Syndrome | Probability | Correction |
| --- | --- | --- | --- |
| $\|\psi_L\rangle$ | Nothing flagged | 65.5% | $I$ |
| $X_k\|\psi_L\rangle$ | Bit check names qubit k | 11.5% | $X_k$ |
| $Y_k\|\psi_L\rangle$ | Bit and phase checks both | 11.5% | $Y_k$ |
| $Z_k\|\psi_L\rangle$ | Phase check names k’s block | 11.5% | $Z$on any qubit of that block |

Measuring the syndrome projects the state onto one branch, with the probability shown.

The syndrome measurement projects the superposition onto one of the four error branches. Each branch has a distinct syndrome, so the measurement identifies which Pauli error branch was selected without revealing the encoded state $|\psi_L\rangle$. The corresponding correction then restores the encoded state.

The code therefore never needs to estimate the continuous angle or axis. It only needs to distinguish the four Pauli error subspaces and apply the corresponding correction. This is the discretization of errors: the physical disturbance can vary continuously, but syndrome measurement reduces its effect to one of a discrete set of correctable outcomes.

It is good news that the nine-qubit Shor code can correct arbitrary one-qubit unitary errors, not just clean $X$, $Y$, and $Z$ errors. But this result still assumes that the syndrome measurements and correction operations are perfect. In a real device, those operations can be noisy too, and the code does not automatically protect them. Making error correction work in practice therefore requires protecting the error-correction process itself. How fun is that!

Arbitrary errors

A unitary error describes a disturbance that keeps the qubit’s state pure. Real noise can be more general. A qubit may lose energy to its surroundings or become entangled with them, leaving the qubit itself in a mixed state. When the surroundings are not observed, this evolution is described by a quantum channel $\Phi$, represented by one or more Kraus operators $A_j$:

$$
\Phi(\rho)=\sum_j A_j\rho A_j^{\dagger}
$$

The index $j$ labels the different components of the noise process. These components arise from the possible states of the surroundings and do not represent a classical choice made before the error. For $\Phi$ to preserve total probability, its Kraus operators must satisfy:

$$
\sum_j A_j^{\dagger}A_j=I
$$

Every $A_j$ is a $2\times2$ matrix, so the four Pauli operators form a basis for it just as they did for the unitary rotation:

$$
A_j=\alpha_j\,I+\beta_j\,X+\gamma_j\,Y+\delta_j\,Z
$$

Suppose the channel acts on physical qubit $k$. Each Kraus operator then becomes the same combination of $I$, $X_k$, $Y_k$, and $Z_k$, so the channel acts on the encoded state as:

$$
\begin{aligned}&\Phi_k\bigl(|\psi_L\rangle\langle\psi_L|\bigr)\\[4pt]&\quad=\sum_j\bigl(\alpha_j\,I+\beta_j\,X_k+\gamma_j\,Y_k+\delta_j\,Z_k\bigr)\,|\psi_L\rangle\langle\psi_L|\,\bigl(\alpha_j\,I+\beta_j\,X_k+\gamma_j\,Y_k+\delta_j\,Z_k\bigr)^{\dagger}\end{aligned}
$$

Every term is a superposition of the same four branches as a unitary error. Computing and measuring the syndrome, then correcting the Pauli error it names, therefore leaves the syndrome qubits and the data in the state:

$$
\begin{gathered}\xi\otimes|\psi_L\rangle\langle\psi_L|\\[8pt]\begin{aligned}\xi=\sum_j\Bigl(&|\alpha_j|^2\,|I\text{ syndrome}\rangle\langle I\text{ syndrome}|\\[4pt]&+|\beta_j|^2\,|X_k\text{ syndrome}\rangle\langle X_k\text{ syndrome}|\\[4pt]&+|\gamma_j|^2\,|Y_k\text{ syndrome}\rangle\langle Y_k\text{ syndrome}|\\[4pt]&+|\delta_j|^2\,|Z_k\text{ syndrome}\rangle\langle Z_k\text{ syndrome}|\Bigr)\end{aligned}\end{gathered}
$$

Whatever the channel, the data return to $|\psi_L\rangle\langle\psi_L|$, and all of the noise is transferred to the syndrome qubits. The probability of each syndrome is the weight of the matching Pauli term, summed over all the Kraus operators:

$$
\begin{aligned}p_I&=\sum_j|\alpha_j|^2\\[6pt]p_X&=\sum_j|\beta_j|^2\\[6pt]p_Y&=\sum_j|\gamma_j|^2\\[6pt]p_Z&=\sum_j|\delta_j|^2\end{aligned}
$$

These four probabilities always add to one, a consequence of the Kraus condition $\sum_j A_j^{\dagger}A_j=I$.

The demo applies three channels to qubit $k$: random Pauli errors, phase flips, and amplitude damping.

Channel on qubit k

Noise strength λ0.50

inputchannel output

The qubit leaks energy into its surroundings, so $|1\rangle$ relaxes to $|0\rangle$ with probability $\lambda$. This is neither a rotation nor a random Pauli error, yet both Kraus operators still break down into Paulis.

$$
\begin{aligned}A_0&=\begin{pmatrix}1&0\\0&\sqrt{1-\lambda}\end{pmatrix}=\frac{1+\sqrt{1-\lambda}}{2}\,I+\frac{1-\sqrt{1-\lambda}}{2}\,Z\\[10pt]A_1&=\begin{pmatrix}0&\sqrt{\lambda}\\0&0\end{pmatrix}=\frac{\sqrt{\lambda}}{2}\,\bigl(X+iY\bigr)\end{aligned}
$$

| Kraus operator | Same operator in the Pauli basis |
| --- | --- |
| $A_0 = \begin{pmatrix} 1.000 & 0 \\ 0 & 0.707 \end{pmatrix}$ | $0.854\,I + 0.146\,Z$ |
| $A_1 = \begin{pmatrix} 0 & 0.707 \\ 0 & 0 \end{pmatrix}$ | $0.354\,X + 0.354i\,Y$ |

| Branch | Syndrome | Probability | Correction |
| --- | --- | --- | --- |
| $\|\psi_L\rangle$ | Nothing flagged | 72.9% | $I$ |
| $X_k\|\psi_L\rangle$ | Bit check names qubit k | 12.5% | $X_k$ |
| $Y_k\|\psi_L\rangle$ | Bit and phase checks both | 12.5% | $Y_k$ |
| $Z_k\|\psi_L\rangle$ | Phase check names k’s block | 2.1% | $Z$on any qubit of that block |

Measuring the syndrome projects the state onto one branch, with the probability shown.

The recovery does not invert an entire Kraus operator. In amplitude damping, $A_1$ is not even invertible. Instead, decompose the Kraus operator into Pauli components. Each component acts like a particular Pauli error on the affected qubit, and the nine-qubit Shor code can correct each of those single-qubit Pauli errors separately. By linearity, correcting the individual components also corrects their superposition.

This works only for errors affecting one physical qubit at a time. An error process acting jointly on two qubits can contain products such as $X_rZ_s$, which act nontrivially on both qubits and are outside the Shor code’s correction guarantee. That is why the random-error estimate counted only cases with at most one error.

The price is steep: nine physical qubits for one logical qubit, with a break-even point near 3% in the simplified random-error model. Better error-correcting codes have been developed since, though none of them is perfect yet. The hope is that, together with less noisy hardware, they will eventually make large quantum computers reliable enough for long computations. The result the nine-qubit Shor code shows is more fundamental: a quantum error-correcting code can protect quantum information from noise without needing to know which error occurred.

## The stabilizer formalism

The protects one logical qubit using nine physical qubits. Its circuits extract a syndrome by asking a small set of parity questions about the physical qubits, without measuring the logical state. So although technically only a small set of questions is asked, encoding just the basis state $|0\rangle$ already gives a superposition of eight nine-bit strings, and $|1\rangle$ gives eight more with minus signs:

$$
|0\rangle\;\mapsto\;\dfrac{1}{2\sqrt2}\,\bigl(|000\rangle+|111\rangle\bigr)\otimes\bigl(|000\rangle+|111\rangle\bigr)\otimes\bigl(|000\rangle+|111\rangle\bigr)
$$

$$
|1\rangle\;\mapsto\;\dfrac{1}{2\sqrt2}\,\bigl(|000\rangle-|111\rangle\bigr)\otimes\bigl(|000\rangle-|111\rangle\bigr)\otimes\bigl(|000\rangle-|111\rangle\bigr)
$$

Nine qubits are still manageable, but a state of $n$ qubits can need $2^n$ amplitudes, so writing out encoded states stops being practical for codes large enough to be useful. The stabilizer formalism provides a compact language for describing the parity questions a code asks and the states they test.

A stabilizer is an operator that describes a property shared by all valid encoded states. Measuring a set of stabilizers therefore provides a collection of checks on the physical qubits. If an error occurs, it can change the outcome of one or more checks. The resulting pattern tells the recovery procedure which error has occurred, or narrows it down enough to choose the appropriate correction, without revealing the logical state.

Pauli operations

The checks used by the stabilizer formalism are constructed from simple operators acting on individual qubits. The basic set consists of the identity $I$ and the three $X$, $Y$, and $Z$:

$I=\begin{pmatrix}1&0\\0&1\end{pmatrix}$$X=\begin{pmatrix}0&1\\1&0\end{pmatrix}$$Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix}$$Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$

A useful property of the Pauli operators is that any two different non-identity operators anticommute. Swapping their order therefore changes the sign of their product:

For the cyclic pairs $XY$, $YZ$, and $ZX$, the product gives the remaining Pauli operator multiplied by $i$. Reversing the order changes $i$ to $-i$:

Each Pauli operator also squares to the identity:

An n-qubit Pauli string assigns one of $I$, $X$, $Y$, or $Z$ to each of the $n$ qubits and takes their tensor product. Its weight is the number of non-identity factors, that is, the number of qubits on which it acts nontrivially. The weight therefore counts how many qubits a Pauli operator acts on.

weight 6

Given $n$-qubit Pauli strings $P_1,\dots,P_r$, the set generated by them contains the identity and every product of the generators, with each generator used any number of times and in any order. It is written:

$$
\langle P_1,\dots,P_r\rangle
$$

Multiplying Pauli strings can introduce a factor of $i$, $-1$, or $-i$, so every element is one of the phases $1,\,i,\,-1,\,-i$ times an $n$-qubit Pauli string. There are only $4\cdot4^n$ such combinations, so the generated set is always finite. In the demo, each element appears with the shortest product of generators that gives it. After a few factors the products stop producing new elements, and the board marks which of the $4\cdot4^n$ combinations the set contains.

$$
I
$$

1 *i* −1− *i*

$$
X
$$

1 *i* −1− *i*

$$
Y
$$

1 *i* −1− *i*

$$
Z
$$

1 *i* −1− *i*

8 of the $4\cdot4^{1}=16$ possible elements

$$
\langle X,\,Z\rangle=\{I,\,X,\,Z,\,iY,\,-I,\,-X,\,-Z,\,-iY\}
$$

Pauli observables

A Pauli operator can act as a gate, but it can also define a measurement. To see how its measurement outcomes arise, start with the action of $Z$ on the two standard basis states:

The states $|0\rangle$ and $|1\rangle$ keep the same direction when $Z$ acts on them, changing only by a factor of $+1$ or $-1$. They are eigenstates of $Z$, and these multiplying factors are their eigenvalues: $+1$ for $|0\rangle$ and $-1$ for $|1\rangle$.

For $X$, its spectral decomposition identifies two eigenstates, $|+\rangle$ and $|-\rangle$, corresponding to the eigenvalues $+1$ and $-1$:

$$
|+\rangle=\dfrac{1}{\sqrt2}\bigl(|0\rangle+|1\rangle\bigr)\qquad|-\rangle=\dfrac{1}{\sqrt2}\bigl(|0\rangle-|1\rangle\bigr)
$$

For $Y$, the spectral decomposition gives two eigenstates that contain $i$ in their amplitudes, while their eigenvalues are again $+1$ and $-1$:

$$
|{+i}\rangle=\dfrac{1}{\sqrt2}\bigl(|0\rangle+i|1\rangle\bigr)\qquad|{-i}\rangle=\dfrac{1}{\sqrt2}\bigl(|0\rangle-i|1\rangle\bigr)
$$

All three operators have the same two eigenvalues, $+1$ and $-1$. Each Pauli operator satisfies $P^2=I$, so applying it twice must bring any state back to where it started. For an eigenstate, one application multiplies the state by its eigenvalue $\lambda$, so applying the operator twice multiplies it by $\lambda^2$. Returning to the original state therefore requires $\lambda^2=1$, giving $\lambda=+1$ or $-1$.

The factors $i$ and $-i$ appear in products of different Pauli operators, such as $XY=iZ$ and $YX=-iZ$. They are phases of those products, not eigenvalues of the individual operators $X$, $Y$, and $Z$.

From operators to measurements

To turn a Pauli operator into a measurement, use its eigenstates as the possible states after measurement. For $Z$, the two outcomes correspond to the eigenstates $|0\rangle$ and $|1\rangle$. A general state can be written as a combination of these eigenstates, and the measurement yields one of them with probabilities determined by the corresponding components of the original state. After the measurement, the state is projected onto the eigenspace associated with the observed outcome. The same construction applies to $X$ and $Y$, using their respective eigenstates.

Each outcome is represented by a projector onto its eigenspace:

In each case, the two projectors sum to the identity, defining a two-outcome with outcomes $+1$ and $-1$. The $+1$ outcome uses the projector onto the $+1$ eigenspace, and the $-1$ outcome uses the projector onto the $-1$ eigenspace.

Measuring through an ancilla

The projective measurement just described can be implemented by coupling the data to an ancilla and measuring the ancilla instead of the data qubits. This does not avoid the state update of a projective measurement: for a general data state, the measurement still projects it onto the eigenspace corresponding to the observed outcome. The advantage is that the data qubits are not directly measured, so a Pauli observable can be measured without revealing the individual data-qubit states.

Prepare the ancilla in $|+\rangle$, apply a controlled-$P$ with the ancilla as the control, and finish with a Hadamard on the ancilla. For an $X$ measurement, the circuit is:

$$
|\psi\rangle
$$

$$
\text{controlled-}P
$$

$$
|+\rangle
$$

$$
\begin{cases}0 & {+1}\text{ eigenvalue}\\ 1 & {-1}\text{ eigenvalue}\end{cases}
$$

This is a single-qubit instance of phase estimation, using to distinguish the two eigenspaces of a Pauli operator. The ancilla encodes which eigenvalue was obtained, so measuring the ancilla reveals the measurement outcome without directly measuring the data qubits.

For a data state that is not an eigenstate, let $\Pi_{\small+}$ and $\Pi_{\small-}$ be the projectors onto the $+1$ and $-1$ eigenspaces of $P$, so that $P=\Pi_{\small+}-\Pi_{\small-}$ and $I=\Pi_{\small+}+\Pi_{\small-}$. The circuit acts on $|\psi\rangle|+\rangle$ as

After the controlled-$P$ and the final Hadamard, the joint state is $\Pi_{\small+}|\psi\rangle|0\rangle+\Pi_{\small-}|\psi\rangle|1\rangle$. Measuring the ancilla selects one of these two orthogonal branches:

- Outcome $0$ occurs with probability $\lVert\Pi_{\small+}|\psi\rangle\rVert^2$. The data state becomes the normalized state $\Pi_{\small+}|\psi\rangle$, which lies in the $+1$ eigenspace.
- Outcome $1$ occurs with probability $\lVert\Pi_{\small-}|\psi\rangle\rVert^2$. The data state becomes the normalized state $\Pi_{\small-}|\psi\rangle$, which lies in the $-1$ eigenspace.

Measuring $P$ directly, as the $\{\Pi_{\small+},\Pi_{\small-}\}$, gives the same result. The outcome is $+1$ with probability $\mathrm{Pr}(+1)=\lVert\Pi_{\small+}|\psi\rangle\rVert^2$ and $-1$ with probability $\mathrm{Pr}(-1)=\lVert\Pi_{\small-}|\psi\rangle\rVert^2$, and the data is left in the normalized $\Pi_{\small+}|\psi\rangle$ or $\Pi_{\small-}|\psi\rangle$ respectively. The ancilla circuit therefore matches a direct measurement of $P$ in both its outcome statistics and its, without ever measuring the data qubits.

Pauli operations on $n$ qubits

The same construction extends to $n$-qubit Pauli operators, formed as tensor products of single-qubit Pauli matrices and identities, such as $Z\otimes Z$ or $X\otimes I\otimes Y$. Each such operator squares to the identity, so its only eigenvalues are $+1$ and $-1$, giving a two-outcome projective measurement. For $Z\otimes Z$,

$$
\begin{aligned}Z\otimes Z&=\bigl(|0\rangle\langle0|-|1\rangle\langle1|\bigr)\otimes\bigl(|0\rangle\langle0|-|1\rangle\langle1|\bigr)\\[4pt]&=\textcolor{#2563eb}{|00\rangle\langle00|}\textcolor{#b45309}{{}-|01\rangle\langle01|-|10\rangle\langle10|}\textcolor{#2563eb}{{}+|11\rangle\langle11|}\\[4pt]&=\textcolor{#2563eb}{\bigl(|00\rangle\langle00|+|11\rangle\langle11|\bigr)}-\textcolor{#b45309}{\bigl(|01\rangle\langle01|+|10\rangle\langle10|\bigr)}.\end{aligned}
$$

Each outcome has its own projector:

- Outcome $\textcolor{#2563eb}{+1}$, the two bits have the same value: $\textcolor{#2563eb}{\Pi_{\small+}=|00\rangle\langle00|+|11\rangle\langle11|}$
- Outcome $\textcolor{#b45309}{-1}$, the two bits have different values: $\textcolor{#b45309}{\Pi_{\small-}=|01\rangle\langle01|+|10\rangle\langle10|}$

The measurement therefore determines their parity without determining either bit individually. This is not the same as measuring both qubits in the standard basis. Measuring each qubit reveals both bits, so a state such as $\alpha|00\rangle+\beta|11\rangle$ collapses to $|00\rangle$ or $|11\rangle$. The $Z\otimes Z$ measurement reveals only the parity, and since both terms have even parity, it leaves the superposition intact. This is what lets a parity check detect errors without disturbing the encoded state.

The parity-check circuit

The same ancilla-based construction also applies to multi-qubit Pauli measurements. Instead of measuring a single-qubit Pauli such as $Z$, the operator $P$ can be a tensor product such as $Z\otimes Z$. The ancilla then records the eigenvalue of the joint operator, allowing a property of several qubits to be measured without measuring them individually.

For $Z\otimes Z$, that property is the parity of the two data bits. The parity of bits $b_1$ and $b_2$ is $b_1\oplus b_2$, their sum modulo 2, which is $\textcolor{#2563eb}{0}$ when the bits agree and $\textcolor{#b45309}{1}$ when they differ. It matches the eigenvalues of $Z\otimes Z$: $|00\rangle$ and $|11\rangle$ have parity $\textcolor{#2563eb}{0}$ and lie in the $\textcolor{#2563eb}{+1}$ eigenspace, while $|01\rangle$ and $|10\rangle$ have parity $\textcolor{#b45309}{1}$ and lie in the $\textcolor{#b45309}{-1}$ eigenspace. The ancilla outcome is therefore the parity bit.

The controlled operation applies $Z\otimes Z$ to the data when the ancilla is in the $|1\rangle$ branch. This can be implemented using two controlled-$Z$ gates, both controlled by the same ancilla:

$$
|\psi\rangle|0\rangle\;\longmapsto\;|\psi\rangle|0\rangle\qquad\qquad|\psi\rangle|1\rangle\;\longmapsto\;(Z\otimes Z)|\psi\rangle|1\rangle
$$

On the $|1\rangle$ branch, the first controlled-$Z$ applies $Z$ to the first data qubit and the second applies $Z$ to the second data qubit. Together, their action is exactly $Z\otimes Z$, and the final Hadamard then sorts the data terms by parity:

Measuring the ancilla keeps either the even-parity or odd-parity part of the data, while preserving the superposition within that parity sector. For $Z\otimes Z$, outcome $\textcolor{#2563eb}{0}$ keeps the $|00\rangle$ and $|11\rangle$ components, while outcome $\textcolor{#b45309}{1}$ keeps the $|01\rangle$ and $|10\rangle$ components. Thus, an outcome of $\textcolor{#b45309}{1}$ does not distinguish $|01\rangle$ from $|10\rangle$. It only tells that the two bits are different.

A $Z\otimes Z$ measurement of two qubits is therefore a measurement of their parity. The complete circuit is:

$$
|\psi\rangle
$$

$$
|+\rangle
$$

$$
\text{controlled-}(Z\otimes Z)
$$

$$
\begin{cases}0 & {+1}\text{ eigenvalue}\\ 1 & {-1}\text{ eigenvalue}\end{cases}
$$

An equivalent circuit replaces the two controlled-$Z$ gates with two CNOTs that target the ancilla. The ancilla then starts in $|0\rangle$ and needs no Hadamard:

$$
|\psi\rangle
$$

$$
|0\rangle
$$

$$
\begin{cases}0 & {+1}\text{ eigenvalue}\\ 1 & {-1}\text{ eigenvalue}\end{cases}
$$

So, a $Z\otimes Z$ measurement can be implemented as a parity check using two CNOTs. The same construction measures $X\otimes X$, with controlled-$X$ gates in place of controlled-$Z$ gates.

Stabilizers in the Repetition Code

The stores one input qubit in the span of $|000\rangle$ and $|111\rangle$. The encoded amplitudes are unknown, so error detection must preserve both basis states and any superposition of them:

$$
\alpha|0\rangle+\beta|1\rangle\;\longmapsto\;|\psi_L\rangle=\alpha|000\rangle+\beta|111\rangle
$$

A check should therefore distinguish whether neighboring qubits have the same value without distinguishing $|000\rangle$ from $|111\rangle$. This can be done with the multi-qubit Pauli operators $Z\otimes Z\otimes I$ and $I\otimes Z\otimes Z$, which check qubits 1–2 and 2–3 respectively. Since the checked qubits have the same value in both $|000\rangle$ and $|111\rangle$, both checks return $+1$ on every encoded state:

A Pauli operator that leaves every encoded state unchanged is called a stabilizer of the code. The two parity checks are independent stabilizers, chosen as generators of the stabilizer group. Multiplying them gives another stabilizer, $(Z\otimes Z\otimes I)(I\otimes Z\otimes Z)=Z\otimes I\otimes Z$, because $Z^2=I$ on the middle qubit. This third stabilizer is therefore already generated by the first two. Together with the identity, the stabilizers form the stabilizer group:

$$
\langle Z\otimes Z\otimes I,\;I\otimes Z\otimes Z\rangle=\{I\otimes I\otimes I,\;Z\otimes Z\otimes I,\;I\otimes Z\otimes Z,\;Z\otimes I\otimes Z\}
$$

Each generator is measured with its own ancilla, using the parity-measurement circuit on the two qubits it involves:

$$
|\psi_L\rangle
$$

$$
(X\otimes I\otimes I)|\psi_L\rangle
$$

Bit flip on qubit 1

The signs (−1, +1) single out this qubit.

$$
|0\rangle
$$

$$
Z\otimes Z\otimes I
$$

$$
I\otimes Z\otimes Z
$$

A bit flip moves the encoded state out of the $+1$ eigenspace of the stabilizers that cover the flipped qubit. The resulting change in signs reveals which checks detect the error and therefore which qubit was flipped.

To see where these signs come from, apply a check to the errored state and commute the check operator past the error operator until it acts directly on $|\psi_L\rangle$. Since the check leaves $|\psi_L\rangle$ unchanged, the remaining sign is the measurement outcome:

$$
\begin{aligned}\textcolor{#0284c7}{(Z\otimes Z\otimes I)}\textcolor{#e11d48}{(X\otimes I\otimes I)}|\psi_L\rangle&=-\textcolor{#e11d48}{(X\otimes I\otimes I)}\textcolor{#0284c7}{(Z\otimes Z\otimes I)}|\psi_L\rangle=-\textcolor{#e11d48}{(X\otimes I\otimes I)}\textcolor{#084e79}{|\psi_L\rangle}\\[4pt]\textcolor{#0284c7}{(I\otimes Z\otimes Z)}\textcolor{#e11d48}{(X\otimes I\otimes I)}|\psi_L\rangle&=\textcolor{#e11d48}{(X\otimes I\otimes I)}\textcolor{#0284c7}{(I\otimes Z\otimes Z)}|\psi_L\rangle=\textcolor{#e11d48}{(X\otimes I\otimes I)}\textcolor{#084e79}{|\psi_L\rangle}\end{aligned}
$$

The sign appears when the check and error are swapped. Because both operators are tensor products, they can be compared one qubit at a time. A $\textcolor{#0284c7}{Z}$ in the check contributes a factor of $-1$ when it meets an $\textcolor{#e11d48}{X}$ in the error, since $\textcolor{#0284c7}{Z}\textcolor{#e11d48}{X}=-\textcolor{#e11d48}{X}\textcolor{#0284c7}{Z}$. If either operator has $I$ on that qubit, they commute and contribute $+1$. The overall eigenvalue is therefore determined by the parity of the overlap: a check returns $-1$ when it covers an odd number of flipped qubits and $+1$ when it covers an even number.

The two measured signs form the syndrome. For a single bit flip, each qubit produces a distinct pair of signs, allowing the flipped qubit to be identified:

| Error | $Z\otimes Z\otimes I$ | $I\otimes Z\otimes Z$ | Reading |
| --- | --- | --- | --- |
| $I\otimes I\otimes I$ | +1 | +1 | No bit flip |
| $X\otimes I\otimes I$ | −1 | +1 | Qubit 1 |
| $I\otimes X\otimes I$ | −1 | −1 | Qubit 2 |
| $I\otimes I\otimes X$ | +1 | −1 | Qubit 3 |

For multiple bit flips, the same parity rule applies: each check returns $-1$ for an odd number of overlapping flips and $+1$ for an even number. These two checks therefore distinguish all single-bit errors, but they cannot uniquely distinguish every possible multiple-bit-flip pattern.

The two signs split the 8-dimensional space of three qubits into four 2-dimensional subspaces, one for each syndrome, with the code space as the $(+1,+1)$ subspace. The Pauli operations split the same way: ignoring phases, the 64 three-qubit Pauli operations fall into four collections of 16, so that, for example, $I\otimes I\otimes Z$, $Z\otimes Z\otimes Z$, and $X\otimes X\otimes X$ all give $(+1,+1)$.

|  | $I\otimes Z\otimes Z$ |  |  |  |
| --- | --- | --- | --- | --- |
|  | $+1$ | $-1$ |  |  |
| $Z\otimes Z\otimes I$ |  | $+1$ | $\|000\rangle$$\|111\rangle$ | $\|001\rangle$$\|110\rangle$ |
| $-1$ | $\|100\rangle$$\|011\rangle$ | $\|010\rangle$$\|101\rangle$ |  |  |

The $Z$ in a check specifies the Pauli observable being measured. It does not indicate a $Z$ error. These $Z$-type checks detect $X$ bit flips because $Z$ and $X$ anticommute. A phase flip $Z$, by contrast, commutes with both checks and therefore produces no change in the syndrome. The extends this construction with additional checks that can detect phase flips as well.

Stabilizer codes

The is a simple example of a more general way to construct quantum error-correcting codes: specify a code space through a set of Pauli checks rather than listing its basis states explicitly. This idea extends naturally from the three-qubit repetition code to arbitrary numbers of qubits.

For an $n$-qubit system, let $P_1,\ldots,P_r$ be the Pauli checks. These operators are called stabilizer generators, and together they define a stabilizer code when they satisfy three conditions:

1. 1.
   
   The generators commute with one another.
   
   $P_jP_k=P_kP_j\qquad\text{for all }j,k\in\{1,\ldots,r\}.$
   
   This ensures that the generators can have common eigenstates and therefore define a shared code space. The repetition code satisfies this condition because its two generators are both $Z$-type operators and therefore commute.
2. 2.
   
   The generators form a minimal generating set.
   
   No generator can be written as a product of the others:
   
   $P_k\notin\langle P_1,\ldots,P_{k-1},P_{k+1},\ldots,P_r\rangle\qquad\text{for each }k\in\{1,\ldots,r\}.$
   
   The right-hand side is the group generated by every generator except $P_k$. If $P_k$ belonged to it, every state fixed by the other generators would already be fixed by $P_k$, so its check would add no new constraint.
   
   The repetition code's generators $Z\otimes Z\otimes I$ and $I\otimes Z\otimes Z$ form a minimal set, since neither is a product of the other. Adding $Z\otimes I\otimes Z$ as a third generator would break the condition, because it is already their product:
   
   Its check would only repeat information: its sign is always the product of the other two signs.
3. 3.
   
   At least one nonzero vector is fixed by every generator.
   
   This ensures that the code space is not trivial. For commuting generators, the condition can be expressed equivalently as
   
   $-I^{\otimes n}\notin\langle P_1,\ldots,P_r\rangle.$
   
   Every element of the generated group is a product of the generators, so any state fixed by all generators is also fixed by every element of the group. If the group contained $-I^{\otimes n}$, a common $+1$ eigenstate would have to satisfy $-I^{\otimes n}|\psi\rangle=|\psi\rangle$, which is possible only for $|\psi\rangle=0$.
   
   The repetition code satisfies this condition: its stabilizer group $\{I\otimes I\otimes I,\;Z\otimes Z\otimes I,\;I\otimes Z\otimes Z,\;Z\otimes I\otimes Z\}$ does not contain $-I\otimes I\otimes I$, and $|000\rangle$ is a common $+1$ eigenstate of its generators. Commutation alone is not enough, however. $X\otimes X$, $Y\otimes Y$, and $Z\otimes Z$ commute pairwise, but their product is $-I\otimes I$, so no nonzero state is fixed by all three:

The code space is the set of all vectors fixed by every generator:

$$
\mathcal C=\bigl\{|\psi\rangle:P_1|\psi\rangle=\cdots=P_r|\psi\rangle=|\psi\rangle\bigr\}.
$$

Because a vector fixed by every generator is also fixed by every product of them, the same space is the set of vectors fixed by the entire stabilizer group $\langle P_1,\ldots,P_r\rangle$. For the repetition code, this space is

$$
\mathcal C=\operatorname{span}\{|000\rangle,|111\rangle\}.
$$

Overall, a small set of independent, commuting Pauli generators specifies both the code space and the checks used to detect errors. Measuring these generators produces the syndrome, with the resulting signs indicating how an error has changed the stabilizer eigenvalues.

Examples of stabilizer codes

Stabilizer codes range from small textbook examples to large families such as surface codes, each specified by its set of generators. A few classic examples are shown below as grids, with one row for each check and one column for each qubit.

|  | q1 | q2 | q3 |  |
| --- | --- | --- | --- | --- |
| Error |  |  |  |  |
| $S_{1}$ | Z | Z | I | −1 |
| $S_{2}$ | I | Z | Z | −1 |

Error detected

$S_{1}$ and $S_{2}$ return −1.

The bit-flip code encodes one qubit into three, as $\alpha|000\rangle+\beta|111\rangle$. It protects against an $X$ bit flip on any one qubit, but not against $Z$ phase flips.

Code space dimension

The stabilizer generators do more than identify errors: they also determine how much quantum information the code can store. Starting with $n$ physical qubits gives a $2^n$-dimensional state space. Each independent stabilizer condition restricts the allowed states to a $+1$ eigenspace and halves that dimension. With $r$ independent generators, the code space therefore has dimension

$$
\dim\mathcal C=2^{\,n-r}.
$$

A $2^{n-r}$-dimensional code space can store $n-r$ logical qubits, so $n-r$ is the number of qubits encoded by the code. This gives a useful way to read the structure of a stabilizer code: $n$ tells how many physical qubits are used, while $r$ tells how many independent constraints are imposed.

For the example codes:

| Code | $n$ qubits | $r$ generators | Encoded qubits $n-r$ |
| --- | --- | --- | --- |
| 3-qubit repetition code (bit flips) | 3 | 2 | $3-2=1$ |
| 3-qubit repetition code (phase flips) | 3 | 2 | $3-2=1$ |
| 9-qubit Shor code | 9 | 8 | $9-8=1$ |
| 7-qubit Steane code | 7 | 6 | $7-6=1$ |
| 5-qubit code | 5 | 4 | $5-4=1$ |
| E-bit code | 2 | 2 | $2-2=0$ |
| GHZ code | 3 | 3 | $3-3=0$ |

When $n-r=0$, the code space is one-dimensional. It contains only a single state up to an overall scalar, so it does not encode an unknown qubit. This is the case for the e-bit and GHZ codes, whose stabilizers fix the Bell and GHZ states.

The projector view of $\dim\mathcal C=2^{\,n-r}$

The previous dimension count started from the $2^n$-dimensional state space of the $n$ physical qubits and asked how many independent conditions the stabilizer generators impose. Each independent condition halves the dimension of the allowed subspace.

The same result can be obtained by constructing a projector onto the code space. Each stabilizer check acts like a filter: it keeps the states that satisfy the check, with eigenvalue $+1$, and removes the states that fail it, with eigenvalue $-1$. For one generator $P_k$, define the projector for this check as

$$
\displaystyle \Pi_k=\frac{I^{\otimes n}+P_k}{2}.
$$

Here $I^{\otimes n}$ is the identity on all $n$ qubits, formed by the tensor product of $n$ copies of the single-qubit identity $I$. It leaves every state unchanged, $I^{\otimes n}|\psi\rangle=|\psi\rangle$, and it is what turns $P_k$ into a filter.

On its own, $P_k$ only multiplies an eigenstate by $+1$ or $-1$, so a state with eigenvalue $-1$ survives the operation, but with its sign flipped. Adding $I^{\otimes n}$ changes these two possible eigenvalues to $1+1=2$ and $1-1=0$, and dividing by $2$ then gives $1$ and $0$. Thus, the projector keeps a state that passes the check unchanged and sends a state that fails the check to $0$.

To see this explicitly, suppose $|\psi\rangle$ is an eigenvector of $P_k$, then $P_k$ acts on $|\psi\rangle$ in a particularly simple way: the result is the same state $|\psi\rangle$, multiplied by an eigenvalue:

| State | $P_k$ eigenvalue | Applying $\Pi_k$ | After the filter $\Pi_k$ |
| --- | --- | --- | --- |
| passes the check | $+1$ | $\displaystyle \Pi_k\|\psi\rangle=\frac{I^{\otimes n}\|\psi\rangle+P_k\|\psi\rangle}{2}=\frac{\|\psi\rangle+\|\psi\rangle}{2}=\|\psi\rangle$ | kept |
| fails the check | $-1$ | $\displaystyle \Pi_k\|\psi\rangle=\frac{I^{\otimes n}\|\psi\rangle+P_k\|\psi\rangle}{2}=\frac{\|\psi\rangle-\|\psi\rangle}{2}=0$ | removed |

Because the stabilizer generators commute, the filters commute too, and the order in which they are applied does not matter. Stacking all $r$ filters keeps exactly the states that pass every check, which gives the code-space projector

$$
\displaystyle \Pi_{\mathcal C}=\Pi_1\Pi_2\cdots\Pi_r=\frac{I^{\otimes n}+P_1}{2}\cdot\frac{I^{\otimes n}+P_2}{2}\cdots\frac{I^{\otimes n}+P_r}{2}=\prod_{k=1}^{r}\frac{I^{\otimes n}+P_k}{2}.
$$

Now expand this product. For each generator $P_k$, the product contains a choice between $I^{\otimes n}$ and $P_k$. For example, when $r=2$,

$$
\displaystyle \begin{aligned}\Pi_{\mathcal C}&=\frac{I^{\otimes n}+P_1}{2}\cdot\frac{I^{\otimes n}+P_2}{2}\\[4pt]&=\frac14\bigl(I^{\otimes n}+P_1\bigr)\bigl(I^{\otimes n}+P_2\bigr)\\[4pt]&=\frac14\bigl(I^{\otimes n}I^{\otimes n}+I^{\otimes n}P_2+P_1I^{\otimes n}+P_1P_2\bigr)\\[4pt]&=\frac14\bigl(I^{\otimes n}+P_1+P_2+P_1P_2\bigr).\end{aligned}
$$

For general $r$, the same expansion gives $2^r$ terms, because each of the $r$ factors contributes either $I^{\otimes n}$ or its generator $P_k$:

$$
\displaystyle \Pi_{\mathcal C}=\frac{1}{2^r}\sum_{a_1,\ldots,a_r\in\{0,1\}}P_1^{a_1}P_2^{a_2}\cdots P_r^{a_r}.
$$

Here, each $a_k$ is either $0$ or $1$. If $a_k=0$, the factor is $I^{\otimes n}$. If $a_k=1$, it is $P_k$.

Thus there are $2^r$ terms, one for each choice of including or excluding each generator. These terms are exactly the elements of the stabilizer group $S=\langle P_1,\ldots,P_r\rangle$, each appearing once. Two different choices cannot give the same product, because that would make one generator a product of the others, contradicting their independence.

The projector $\Pi_{\mathcal C}$ keeps exactly the states in the code space and sends all other states to $0$. Therefore, in a basis that separates the code space from its orthogonal complement, $\Pi_{\mathcal C}$ has $1$ on the code-space dimensions and $0$ elsewhere. The trace of $\Pi_{\mathcal C}$ counts these $1$s, giving

$$
\mathrm{Tr}\bigl(\Pi_{\mathcal C}\bigr)=\dim\mathcal C.
$$

Because the trace is linear, the trace of the expanded projector can now be taken term by term:

$$
\displaystyle \dim\mathcal C=\mathrm{Tr}\bigl(\Pi_{\mathcal C}\bigr)=\frac{1}{2^r}\sum_{a_1,\ldots,a_r\in\{0,1\}}\mathrm{Tr}\bigl(P_1^{a_1}P_2^{a_2}\cdots P_r^{a_r}\bigr).
$$

Only the term with every $a_k=0$ contributes to the trace. That term is the identity $I^{\otimes n}$, a $2^n\times 2^n$ matrix with every diagonal entry equal to $1$. Its trace adds up those $2^n$ ones, which is easy to see for one and two qubits and holds the same way for any $n$:

$$
\displaystyle \begin{aligned}\mathrm{Tr}(I)&=\mathrm{Tr}\begin{pmatrix}1&0\\0&1\end{pmatrix}=2,\\[6pt]\mathrm{Tr}(I\otimes I)&=\mathrm{Tr}\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}=4=2^2,\\[6pt]\mathrm{Tr}\bigl(I^{\otimes n}\bigr)&=\underbrace{1+1+\cdots+1}_{2^n}=2^n.\end{aligned}
$$

Every other term includes at least one generator, so it is a Pauli string with a sign $\pm1$ in front. It cannot be $I^{\otimes n}$, because that is already the term with no generators chosen, and by the third stabilizer condition it cannot be $-I^{\otimes n}$. So at least one of its factors is $X$, $Y$ or $Z$. The trace of a tensor product is the product of the traces of its factors, and $\mathrm{Tr}(X)=\mathrm{Tr}(Y)=\mathrm{Tr}(Z)=0$, so a single such factor makes the whole trace $0$. For example,

$$
\mathrm{Tr}(X\otimes Z\otimes I)=\mathrm{Tr}(X)\,\mathrm{Tr}(Z)\,\mathrm{Tr}(I)=0\cdot0\cdot2=0.
$$

Only the identity term survives, so

$$
\displaystyle \dim\mathcal C=\mathrm{Tr}\bigl(\Pi_{\mathcal C}\bigr)=\frac{1}{2^r}\bigl(2^n+0+\cdots+0\bigr)=\frac{2^n}{2^r}=\boxed{2^{\,n-r}}.
$$

| $\|x\rangle$ | $I^{\otimes 3}$III | $P_{1}$ZZI | $P_{2}$IZZ | $P_{1}P_{2}$ZIZ | $\Pi_{\mathcal C}$ |
| --- | --- | --- | --- | --- | --- |
| $\|000\rangle$ | +1 | +1 | +1 | +1 | $1$ |
| $\|001\rangle$ | +1 | +1 | −1 | −1 | $0$ |
| $\|010\rangle$ | +1 | −1 | −1 | +1 | $0$ |
| $\|011\rangle$ | +1 | −1 | +1 | −1 | $0$ |
| $\|100\rangle$ | +1 | −1 | +1 | −1 | $0$ |
| $\|101\rangle$ | +1 | −1 | −1 | +1 | $0$ |
| $\|110\rangle$ | +1 | +1 | −1 | −1 | $0$ |
| $\|111\rangle$ | +1 | +1 | +1 | +1 | $1$ |
| $\mathrm{Tr}$ | 8 | 0 | 0 | 0 | 2 |

Down the columns: $\mathrm{Tr}\bigl(\Pi_{\mathcal C}\bigr)=\tfrac{1}{4}\bigl(8+0+0+0\bigr)=2$

Across the rows: $\mathrm{Tr}\bigl(\Pi_{\mathcal C}\bigr)=1+1=2$

Counting independent conditions and taking the trace of the projector give the same dimension, $2^{n-r}$, so a stabilizer code on $n$ physical qubits with $r$ independent generators encodes $n-r$ logical qubits. This is the central trade-off of a stabilizer code: each of the $r$ checks uses up one of the $n$ physical qubits’ degrees of freedom, and the remaining $n-r$ carry the logical information.

Clifford circuits and encodings

A stabilizer code is defined by its Pauli checks, but a quantum code is useful only if operations can also be performed on its states. What is needed are quantum gates that manipulate encoded states while the code can still be tracked with the same stabilizer description.

Clifford operations have exactly this property. When a Clifford operation is applied, every Pauli check is transformed into another Pauli operation. So the stabilizers remain Pauli checks after the operation, rather than becoming more complicated operators. This makes Clifford circuits especially convenient for preparing encoded states, manipulating them, and performing error correction.

A Clifford operation is a unitary operation that can be implemented by a circuit built from three types of gates: Hadamard gates, $S$ gates, and CNOT gates.

Clifford operations can also be described by how they act on Pauli operations. Up to a global phase, an $n$-qubit unitary $U$ is a Clifford operation if and only if conjugation by $U$ — the map sending $P$ to $UPU^{\dagger}$ — sends every $n$-qubit Pauli operation to another $n$-qubit Pauli operation. This is exactly the property that keeps Pauli checks Pauli after the operation.

Formally, for every $P_1,\ldots,P_n\in\{I,X,Y,Z\}$ there exist $Q_1,\ldots,Q_n\in\{I,X,Y,Z\}$ such that

$$
U\,(P_1\otimes\cdots\otimes P_n)\,U^{\dagger}=\pm\,Q_1\otimes\cdots\otimes Q_n.
$$

Conjugation is useful here because it describes how an operator changes when a unitary operation is applied to a state. A stabilizer is such an operator: it is a Pauli operation that leaves the state unchanged. If $P$ stabilizes $|\psi\rangle$, then after applying $U$, the corresponding stabilizer is $UPU^{\dagger}$:

$$
\bigl(UPU^{\dagger}\bigr)\,U|\psi\rangle=UP\bigl(U^{\dagger}U\bigr)|\psi\rangle=UP|\psi\rangle=U|\psi\rangle.
$$

Thus, $UPU^{\dagger}$ stabilizes the transformed state $U|\psi\rangle$. This is why the Clifford property is important for stabilizer codes: because $UPU^{\dagger}$ is again a Pauli operation, the transformed state can still be described using Pauli stabilizers.

Clifford operations are not for quantum computation. There are only finitely many $n$-qubit Clifford operations, and by the [Gottesman–Knill theorem](https://en.wikipedia.org/wiki/Gottesman%E2%80%93Knill_theorem) their action on standard basis states can be simulated efficiently on a classical computer.

Conveniently, stabilizer codes can always be encoded using Clifford operations, with at most $O(n^2/\log n)$ gates. Such encoders were constructed by [Cleve and Gottesman](https://arxiv.org/abs/quant-ph/9607030), and the gate count holds because [every Clifford operation on $n$ qubits](https://arxiv.org/abs/quant-ph/0406196) can be implemented with that many gates.

$$
\alpha|0\rangle+\beta|1\rangle
$$

$$
|0\rangle
$$

$$
U
$$

$S_{1}=Z_{1}Z_{2}$$S_{2}=Z_{2}Z_{3}$

The result of the encoder is an entangled state that spreads the logical information across all three physical qubits. Starting from $\alpha|0\rangle+\beta|1\rangle$, the bit-flip encoder produces

$$
U\bigl((\alpha|0\rangle+\beta|1\rangle)\otimes |00\rangle\bigr)=\alpha|000\rangle+\beta|111\rangle.
$$

This is the three-qubit repetition code. The logical qubit is no longer stored in the first qubit alone. It is a joint property of all three.

The checks followed through the encoder are the tools for finding errors. An error on one qubit changes the state and reverses the sign of every check it anticommutes with. An $X$ on $q_{1}$ reverses $S_{1}$, an $X$ on $q_{2}$ reverses $S_{1}$ and $S_{2}$, and an $X$ on $q_{3}$ reverses $S_{2}$. Measuring the checks reads this pattern, the, without measuring $\alpha$ or $\beta$. Once the error is identified, applying the same Pauli operation again undoes it and restores the encoded state.

A Clifford encoder makes this possible because Clifford gates send Pauli checks to Pauli checks. The simple checks of the ancillas become the code’s checks, $Z_{2}\mapsto S_{1}$ and $Z_{3}\mapsto S_{2}$, and those are the checks that later detect errors. The encoder turns the original qubit into a protected logical qubit.

Detecting errors

Stabilizer checks act like parity checks. An encoded state is a $+1$ eigenvector of every check, so measuring a check returns $+1$ with certainty and leaves the encoded state unchanged. An error can flip some of these outcomes to $-1$. The pattern of flips is called the syndrome.

Let $P_1,\ldots,P_r$ be the stabilizer generators of an $n$-qubit code, and let the $n$-qubit Pauli operation $E$ represent an error acting on a code state $|\psi\rangle$. Two Pauli operations either commute or anticommute.

- If $E$ anticommutes with $P_k$, then
   
   $P_k\,E|\psi\rangle=-E\,P_k|\psi\rangle=-E|\psi\rangle.$
   
   The last equality follows because $P_k$ leaves the original code state $|\psi\rangle$ unchanged. Measuring $P_k$ on the state after the error therefore returns $-1$.
- If $E$ commutes with $P_k$, the same calculation has no sign change, so measuring $P_k$ on the state after the error returns $+1$.

Measuring all $r$ generators gives a list of signs: the syndrome. The syndrome depends only on which generators anticommute with $E$ and reveals nothing about the encoded state $|\psi\rangle$. Measuring the generators therefore leaves the encoded information intact.

Every error falls into one of three cases:

| Case | Error | Syndrome | Effect on the code |
| --- | --- | --- | --- |
| 1 · harmless | $E=\alpha Q$ for some $Q\in\langle P_1,\ldots,P_r\rangle$ | all $+1$ | Leaves every code state unchanged apart from the factor $\alpha$: $E\|\psi\rangle=\alpha\|\psi\rangle$ |
| 2 · dangerous | $EP_k=P_kE$ for every $k$, but $E$ is not a case-1 error | all $+1$ | Acts as a logical operation that the checks do not detect |
| 3 · detected | $P_kE=-EP_k$ for at least one $k$ | some $-1$ | Moves the state out of the code space |

Only case 2 is dangerous. Its syndrome is all $+1$, as in case 1, but the error acts as a logical operation, such as flipping the encoded qubit, and no check notices.

Errors below the code’s distance cannot fall into case 2. The distance $d$ of a code is the minimum weight of a case-2 error: the smallest number of physical qubits that an undetected logical error must act on. Every error of smaller weight either leaves the encoded state unchanged or is detected. A code that encodes $m$ qubits into $n$ qubits with distance $d$ is called an $[[n,m,d]]$ code.

$$
[[n,m,\textcolor{#e11d48}{d}]]=[[3,1,\textcolor{#e11d48}{1}]]
$$

| Error | Weight | $S_{1}$ | $S_{2}$ | Effect |
| --- | --- | --- | --- | --- |
| 1 · harmless · every check +1, the state is unchanged |  |  |  |  |
|  | 2 | +1 | +1 | unchanged |
|  | 2 | +1 | +1 | unchanged |
| 2 · dangerous · every check +1, yet the state changes |  |  |  |  |
|  | 1= d | +1 | +1 | $\alpha\|\overline{0}\rangle-\beta\|\overline{1}\rangle$ |
|  | 3 | +1 | +1 | $\alpha\|\overline{1}\rangle+\beta\|\overline{0}\rangle$ |
| 3 · detected · some check reads −1 |  |  |  |  |
|  | 1 | −1 | +1 | leaves the code space |
|  | 1 | −1 | −1 | leaves the code space |
|  | 1 | +1 | −1 | leaves the code space |

|  | q1 | q2 | q3 | sign |
| --- | --- | --- | --- | --- |
| $E$ | X |  |  |  |
| $S_{1}$ | Z | Z | I | −1 |
| $S_{2}$ | I | Z | Z | +1 |

Together, these ideas describe how a stabilizer code works. A set of commuting Pauli checks defines the code space, and a Clifford encoder places any state in that space. Measuring the checks gives an error’s signature, the syndrome, without revealing the encoded data. Errors that are products of checks leave the encoded state unchanged, and errors that anticommute with at least one check appear in the syndrome. Only errors that commute with every check but are not products of checks as in case 1 can change the encoded qubit without being detected. The distance $d$ is the smallest weight of such an error, so every error on fewer than $d$ qubits is either detected or harmless.

Knowing that an error happened is not yet enough to undo the error, though. For correction, the syndrome must point to the error.

Correcting errors

To correct an error, a decoder must choose an operation that restores the encoded state. The difficulty is that the syndrome does not identify exactly which error occurred: many different errors produce the same syndrome. With $r$ generators on $n$ qubits, there are $2^r$ syndromes and $4^n$ Pauli operations, ignoring phases. Each syndrome is associated with $4^n/2^r$ of these operations.

Some errors with the same syndrome also have the same effect on code states. If $S$ is a stabilizer element, then $E$ and $ES$ are equivalent, since every code state $|\psi\rangle$ satisfies

$$
ES|\psi\rangle=E\bigl(S|\psi\rangle\bigr)=E|\psi\rangle.
$$

Even after grouping equivalent errors, for each syndrome there remain $4^{n-r}$ classes that act differently on the code space, and a single correction can undo errors in at most one of them. Thus, unless $r=n$, in which case the code space is one-dimensional, no procedure can correct every error, and a decoder must choose which class to correct.

Still, the syndrome provides information for error correction: it indicates which stabilizer checks are nontrivial, but it does not identify the exact error that occurred. A natural decoding rule is therefore: for each syndrome $s$, choose a lowest-weight Pauli operation $C$ that produces $s$, and apply $C$ as the correction. For a code of distance $d$, this rule corrects every error of weight less than $d/2$.

To see why, suppose the actual error $E$ has weight less than $d/2$. Since $E$ produces the measured syndrome, the chosen correction $C$ produces the same syndrome. After the correction, the residual operation $CE$ remains, and three facts about it follow.

- $C$ is no heavier than $E$. $C$ has the lowest weight among operations with this syndrome, and $E$ is one of them, so $\operatorname{wt}(C)\le\operatorname{wt}(E)$.
- $CE$ is lighter than the distance. Its weight is at most the sum of the two weights, so
   
   $\operatorname{wt}(CE)\le\operatorname{wt}(C)+\operatorname{wt}(E)\le2\operatorname{wt}(E)<d.$
- $CE$ passes every check. $C$ and $E$ flip the same check outcomes, so in the product $CE$ the flips cancel.

By definition of the code distance, any operation that passes every check but changes the encoded state must have weight at least $d$. But $CE$ passes every check and has weight less than $d$. Therefore, $CE$ cannot change the encoded state. It has no logical effect, so the correction $C$ successfully cancels the error $E$.

If the error is larger, the argument above no longer works. The lowest-weight operation with the same syndrome may be quite different from $E$, so $CE$ can have weight $d$ or more. In that case, $CE$ may change the encoded state instead of simply canceling the error.

This means that every error affecting fewer than $d/2$ qubits can be corrected. Equivalently, a code of distance $d$ can correct errors on up to $\lfloor (d-1)/2\rfloor$ qubits. The Shor, Steane, and five-qubit codes all have distance $3$, so they can each correct any single-qubit error.

$$
[[n,m,\textcolor{#e11d48}{d}]]=[[7,1,\textcolor{#e11d48}{3}]]\qquad \left\lfloor\tfrac{\textcolor{#e11d48}{d}-1}{2}\right\rfloor=1
$$

corrected · $CE$ is a product of checks, so $C$ undoes $E$ on every code state

logical error · $CE$ passes every check but is not a product of checks, so it changes the encoded state

| Error $E$ | Weight | Syndrome | Correction $C$ | $CE$ |
| --- | --- | --- | --- | --- |
| corrected · $CE$ is a product of checks, so $C$ undoes $E$ on every code state |  |  |  |  |
|  | 1 | −−−+++ | $X_{1}$ | $I$ |
|  | 1 | +++−+− | $Z_{3}$ | $I$ |
|  | 1 | ++−++− | $Y_{7}$ | $I$ |
|  | 2 | −−−−−+ | $X_{1}Z_{2}$ | $I$ |
| logical error · $CE$ passes every check but is not a product of checks, so it changes the encoded state |  |  |  |  |
|  | 2 | ++−+++ | $X_{7}$ | $X_{1}X_{2}X_{7}\;(\overline{X})$ |
|  | 2 | +++−−+ | $Z_{2}$ | $Z_{1}Z_{2}Z_{7}\;(\overline{Z})$ |
|  | 2 | +−−+++ | $X_{5}$ | $X_{1}X_{4}X_{5}\;(\overline{X})$ |

|  | q1 | q2 | q3 | q4 | q5 | q6 | q7 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $E$ | X | I | I | I | I | I | I |
| $C$ | X | I | I | I | I | I | I |
| $CE$ | I | I | I | I | I | I | I |

syndrome

−−−+++

lightest C

$$
X_{1}
$$

weight of CE

$$
0<d
$$

result

restored

The remaining challenge is finding the correction $C$, and unfortunately, for a given choice of generators and a syndrome, finding a lowest-weight Pauli operation that produces that syndrome is computationally difficult in general. Finding codes that allow a lowest-weight correction to be chosen efficiently is part of the art of code design.

## Quantum code constructions

With the stabilizer formalism in place, the next step is to construct codes with useful properties. The goal is to protect quantum information from errors while keeping the checks simple, local, and scalable as the code grows.

Classical linear codes

Let $\Sigma=\{0,1\}$ be the binary alphabet. A classical linear code is a nonempty set of binary strings $\mathcal C\subseteq\Sigma^n$ that is closed under bitwise addition modulo 2:

$$
u,v\in\mathcal C\;\Longrightarrow\;u\oplus v\in\mathcal C.
$$

Bitwise addition treats a string as a list of separate bits, not as a binary number. Position $i$ of $u\oplus v$ is computed from position $i$ of $u$ and $v$ alone, and the sum is taken modulo 2:

As a result, nothing carries. In a binary number, the positions stand for $1$, $2$, $4$, and so on, so a sum of $2$ in one position equals a $1$ in the next position and has to move there. In a string, each position is an independent bit, so a sum of $2$ is replaced by its remainder $0$ modulo 2 and the other positions are left alone. The same two strings, added bitwise and as the numbers $3$ and $1$, give different results:

The $\{000,111\}$ is a linear code, since every sum of two codewords is again $000$ or $111$:

Not every set of strings is closed. The set $\{000,100,111\}$, the repetition code with $100$ added, is not a linear code, because one of its sums falls outside it:

A richer example is the [Hamming code](https://en.wikipedia.org/wiki/Hamming_code), a set of sixteen codewords:

$$
\mathcal C=
$$

$0000000$$1100001$$1010010$$0110011$$0110100$$1010101$$1100110$$0000111$$1111000$$0011001$$0101010$$1001011$$1001100$$0101101$$0011110$$1111111$

Codes like this are labelled $[n,m,d]$. The codewords have $n$ bits, there are $2^m$ of them, so the code carries $m$ bits of information, and any two codewords differ in at least $d$ positions. The Hamming code is a $[7,4,3]$ code: sixteen codewords of seven bits, pairwise at least three bits apart. A single flipped bit therefore leaves a word closer to its own codeword than to any other, and can be undone. And the 3-bit repetition code $\{000,111\}$ is a $[3,1,3]$ code.

The has the same three roles, $n$ qubits, $m$ encoded qubits and distance $d$, and the double brackets mark it as quantum. The numbers do not carry over from a classical code to a quantum one, though. The is built from the Hamming code, yet it is a $[[7,1,3]]$ code.

Two ways to describe a linear code

A linear code can be specified in two equivalent ways: by describing how to construct its codewords, or by specifying conditions that a string must satisfy to be a codeword.

The first uses generators. A set of generators $u_1,\ldots,u_m$ is chosen so that every codeword can be formed by adding some of them. For each generator, $\alpha_k=1$ means that it is included in the sum and $\alpha_k=0$ means that it is not:

$$
\mathcal C=\bigl\{\alpha_1u_1\oplus\cdots\oplus\alpha_mu_m\;:\;\alpha_1,\ldots,\alpha_m\in\{0,1\}\bigr\}.
$$

The second uses parity checks. A set of checks $v_1,\ldots,v_r$ is chosen so that a string is a codeword exactly when it passes every check. A string $u$ passes a check $v$ when their binary dot product $u\cdot v$ is 0:

$$
\mathcal C=\bigl\{u\in\Sigma^n\;:\;u\cdot v_1=\cdots=u\cdot v_r=0\bigr\}.
$$

Generators

| $\alpha_k$ |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- |
|  | $u_{1}$ |  |  |  |  |
|  |  |  |  |  |  |

Parity checks

|  |  |  |  |  | $u\cdot v_k$ |
| --- | --- | --- | --- | --- | --- |
|  | $u$ |  |  |  |  |
|  | $v_{1}$ | 1 | 1 | 0 | 1 |
|  | $v_{2}$ | 0 | 1 | 1 | 1 |

Not a codeword

$u\cdot v_{1}=u\cdot v_{2}=1$, so no choice of $\alpha_k$ builds $u$.

The 3-bit repetition code is a $[3,1,3]$ code with a single generator, so its two codewords are the sums with $\alpha_1=0$ and $\alpha_1=1$, namely $000$ and $111$. Its checks $110$ and $011$ ask that the first two bits agree and that the last two agree.

Linear codes therefore provide two complementary descriptions of the same structure: generators specify how codewords are built, while parity checks specify the conditions they must satisfy. Together, these give both a way to construct the code and a way to detect errors.

CSS codes

A provides two kinds of structure: generators and parity checks. In a quantum code, the parity-check idea can be applied in two different bases: the computational basis $\{|0\rangle,|1\rangle\}$ and the plus/minus basis $\{|+\rangle,|-\rangle\}$. A CSS code uses both kinds of quantum parity checks as: one set in each basis. This lets it detect $X$ errors and $Z$ errors separately.

On the classical side, a string $u$ passes a parity check $v$ when $u\cdot v=0$, and the code $\mathcal C$ consists of the strings that pass every check. In the quantum version, the same check is represented by a Pauli $Z$ operation. For a binary string $v$, define $Z^v$ as the operation that applies $Z$ to each qubit where $v$ has a 1 and $I$ where $v$ has a 0:

$$
Z^{v}=Z^{v_1}\otimes Z^{v_2}\otimes\cdots\otimes Z^{v_n}.
$$

On a computational-basis state $|u\rangle$, the operation $Z^v$ contributes a factor of $-1$ for every position where both $u$ and $v$ have a 1:

$$
Z^{v}|u\rangle=(-1)^{u\cdot v}|u\rangle.
$$

The eigenvalue is $+1$ exactly when $u\cdot v=0$. Thus, $|u\rangle$ satisfies the checks $Z^{v_1},\ldots,Z^{v_r}$ exactly when $u$ satisfies the corresponding classical checks $v_1,\ldots,v_r$, that is, when $u\in\mathcal C$.

A classical parity check therefore becomes a Z-type stabilizer generator, containing only $Z$ and $I$. For example, the 3-bit repetition code’s checks $110$ and $011$ become $ZZI$ and $IZZ$. The Hamming code’s checks become $ZZZZIII$, $ZZIIZZI$, and $ZIZIZIZ$.

The same parity check can be expressed in the plus/minus basis. Define $X^v=X^{v_1}\otimes\cdots\otimes X^{v_n}$ in the same way, and let $H^{\otimes n}|u\rangle$ denote the state with $|+\rangle$ where $u$ has a $0$ and $|-\rangle$ where it has a $1$. Since $X|\pm\rangle=\pm|\pm\rangle$, the corresponding calculation is:

$$
X^{v}H^{\otimes n}|u\rangle=(-1)^{u\cdot v}H^{\otimes n}|u\rangle.
$$

Thus the same parity check becomes an X-type stabilizer generator, with $X$ replacing $Z$ and the plus/minus basis replacing the computational basis. For the Hamming code, the checks $1111000$, $1100110$, and $1010101$ become $XXXXIII$, $XXIIXXI$, and $XIXIXIX$. Their common $+1$ eigenspace contains the sixteen basis states corresponding to the Hamming codewords, with $0$ represented by $|+\rangle$ and $1$ by $|-\rangle$. For example, the codeword $0110100$ gives $|{+}{-}{-}{+}{-}{+}{+}\rangle$.

The central idea is simple: a classical parity check has a quantum version in either basis. $Z$-type stabilizers impose the checks in the computational basis, while $X$-type stabilizers impose the same checks in the plus/minus basis. Using both gives a CSS code two complementary sets of checks: $Z$-type stabilizers detect $X$ errors, while $X$-type stabilizers detect $Z$ errors.

Z stabilizer generators

| $\|u\rangle$ |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $Z^{v_{1}}$ | Z | Z | Z | Z | I | I | I | +1 |
| $Z^{v_{2}}$ | Z | Z | I | I | Z | Z | I | +1 |
| $Z^{v_{3}}$ | Z | I | Z | I | Z | I | Z | −1 |

X stabilizer generators

| $H^{\otimes n}\|u\rangle$ |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $X^{v_{1}}$ | X | X | X | X | I | I | I | +1 |
| $X^{v_{2}}$ | X | X | I | I | X | X | I | +1 |
| $X^{v_{3}}$ | X | I | X | I | X | I | X | −1 |

Not a codeword

$u\cdot v_{3}=1$, so that check returns $-1$ in both bases.

There is one more requirement: the $Z$-type and $X$-type stabilizers must be able to hold simultaneously. A code state must satisfy $S|\psi\rangle=|\psi\rangle$ for every stabilizer $S$. Now suppose two stabilizers $S$ and $T$ anticommute, so $ST=-TS$. If both are to leave the same state $|\psi\rangle$ unchanged, then $S|\psi\rangle=T|\psi\rangle=|\psi\rangle$, and therefore

$$
|\psi\rangle=ST|\psi\rangle=-TS|\psi\rangle=-|\psi\rangle.
$$

This can only be true for $|\psi\rangle=0$, which is not a valid quantum state. Thus, stabilizers that anticommute cannot belong to the same stabilizer code: all stabilizers must commute. In particular, every $X$-type stabilizer must commute with every $Z$-type stabilizer.

Whether an $X$-type and a $Z$-type stabilizer commute depends only on how many qubits they act on simultaneously. On a qubit where one stabilizer has $I$, the two operators commute automatically. On a qubit where both act, one has $X$ and the other has $Z$, and swapping their order introduces a minus sign because $XZ=-ZX$. Thus, each qubit where both stabilizers act contributes one minus sign. For strings $x$ and $z$, this gives

$$
X^{x}Z^{z}=(-1)^{x\cdot z}Z^{z}X^{x}.
$$

2 shared qubits: $(-1)(-1)=+1$commute

1 shared qubit: $-1$anticommute

An even overlap gives an even number of minus signs, which cancel, while an odd overlap leaves one minus sign. For example, $XXI$ and $ZZI$ overlap on two qubits, so they commute, whereas $XXI$ and $IZZ$ overlap on one qubit, so they anticommute. Therefore, if $z_1,\ldots,z_s\in\Sigma^n$ are the parity checks for the $Z$-type stabilizers and $x_1,\ldots,x_t\in\Sigma^n$ are those for the $X$-type stabilizers, every $X$-type stabilizer must overlap every $Z$-type stabilizer on an even number of qubits, which means $x_i\cdot z_j=0$ for every $i$ and $j$.

Error detection and correction

The CSS construction separates $X$ and $Z$ errors into two independent parts. A $Z$ error commutes with every $Z$-type stabilizer, so it does not change their outcomes, while an $X$ error commutes with every $X$-type stabilizer for the same reason. Thus, the $Z$-type checks detect only the $X$ part of an error, and the $X$-type checks detect only its $Z$ part. Since every Pauli error can be written, up to a phase, as an $X$ part times a $Z$ part, with $Y$ contributing to both, decoding reduces to two separate classical decoding problems.

Suppose the $Z$-type stabilizers can correct up to $j$ $X$ errors, while the $X$-type stabilizers can correct up to $k$ $Z$ errors. Then the CSS code can correct any Pauli error acting on at most $\min\{j,k\}$ qubits. Such an error has at most $\min\{j,k\}$ qubits in each of its $X$ and $Z$ parts, so both parts can be decoded successfully.

In the Steane code both halves are the, which correct one bit flip, so $j=k=1$. Any single-qubit error is corrected, and so is an $X$ on one qubit together with a $Z$ on another:

|  | q1 | q2 | q3 | q4 | q5 | q6 | q7 | before | after |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $E$ |  |  |  |  |  |  |  |  |  |
| $Z^{v_{1}}$ | Z | Z | Z | Z | I | I | I | −1 | +1 |
| $Z^{v_{2}}$ | Z | Z | I | I | Z | Z | I | −1 | +1 |
| $Z^{v_{3}}$ | Z | I | Z | I | Z | I | Z | +1 | +1 |
| $X^{v_{1}}$ | X | X | X | X | I | I | I | +1 | +1 |
| $X^{v_{2}}$ | X | X | I | I | X | X | I | −1 | +1 |
| $X^{v_{3}}$ | X | I | X | I | X | I | X | −1 | +1 |
| $R$ | I | X | I | I | Z | I | I |  |  |
| $RE$ | I | I | I | I | I | I | I |  |  |

Corrected

R undoes every error in E, so the encoded state is back where it started.

Stronger error correction comes at a cost. Each independent stabilizer halves the code space, so a CSS code on $n$ qubits with $s$ independent $Z$-type and $t$ independent $X$-type stabilizers encodes $n-s-t$ logical qubits. Adding more checks can detect and correct more errors, but it also reduces the number of qubits available to store information.

Code spaces of CSS codes

The stabilizers of a code say which states are allowed, but not what those states look like. For a CSS code the answer is concrete — every code state is a superposition of classical codewords, and the two kinds of checks decide which codewords appear and with what amplitudes.

Write a state in the computational basis as a superposition of strings $w$. A $Z$-type check $Z^z$ multiplies each term by $(-1)^{w\cdot z}$. For the state to stay unchanged, every term must get the sign $+1$, so only strings that pass all $Z$-type checks may appear.

An $X$-type check $X^x$ does not change signs. It flips bits, sending each term $|w\rangle$ to $|w\oplus x\rangle$. For the state to stay unchanged, the string $w\oplus x$ must appear whenever $w$ does, with the same amplitude. Applying several $X$-type checks adds their sum, so together with $w$ the state must contain $w$ plus every sum of $X$-type checks, all with equal amplitudes.

Two are therefore involved: $\mathcal C_Z$, the strings that pass every $Z$-type check $z_1,\ldots,z_s$, and $\mathcal D_X$, the sums of the $X$-type checks $x_1,\ldots,x_t$:

$$
\begin{aligned}\mathcal C_Z&=\bigl\{u\in\Sigma^n\;:\;u\cdot z_1=\cdots=u\cdot z_s=0\bigr\},\\[4pt]\mathcal D_X&=\bigl\{\alpha_1x_1\oplus\cdots\oplus\alpha_tx_t\;:\;\alpha_1,\ldots,\alpha_t\in\{0,1\}\bigr\}.\end{aligned}
$$

A code state is then built in one step. Start from any string $u\in\mathcal C_Z$, collect everything reachable from it by adding a sum of $X$-type checks, written $u\oplus\mathcal D_X$, and take the equal superposition:

$$
\displaystyle|u\oplus\mathcal D_X\rangle=\frac{1}{\sqrt{2^t}}\sum_{v\in\mathcal D_X}|u\oplus v\rangle.
$$

Adding $X$-type checks never leads out of $\mathcal C_Z$. Every $X$-type check overlaps every $Z$-type check evenly, so it passes all of them, and so does every sum of them. In symbols, $\mathcal D_X\subseteq\mathcal C_Z$. Every term of the superposition therefore passes the $Z$-type checks, and an $X$-type check only shuffles the terms among themselves. Both requirements hold.

The same construction works with the roles of the two bases swapped. Let $\mathcal C_X$ be the strings that pass every $X$-type check and $\mathcal D_Z$ the sums of the $Z$-type checks:

$$
\begin{aligned}\mathcal C_X&=\bigl\{u\in\Sigma^n\;:\;u\cdot x_1=\cdots=u\cdot x_t=0\bigr\},\\[4pt]\mathcal D_Z&=\bigl\{\alpha_1z_1\oplus\cdots\oplus\alpha_sz_s\;:\;\alpha_1,\ldots,\alpha_s\in\{0,1\}\bigr\}.\end{aligned}
$$

Building the superpositions in the plus/minus basis instead, one for each $u\in\mathcal C_X$, describes the same code space:

$$
\displaystyle H^{\otimes n}|u\oplus\mathcal D_Z\rangle=\frac{1}{\sqrt{2^s}}\sum_{v\in\mathcal D_Z}H^{\otimes n}|u\oplus v\rangle.
$$

All 128 strings $w$ of 7 bits, each standing for the state $|w\rangle$. A code state is a superposition of such states that every check leaves unchanged.

| $Z^{z_{1}}$ | Z | Z | Z | Z | I | I | I |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $Z^{z_{2}}$ | Z | Z | I | I | Z | Z | I |  |
| $Z^{z_{3}}$ | Z | I | Z | I | Z | I | Z |  |
| $X^{x_{1}}$ | X | X | X | X | I | I | I |  |
| $X^{x_{2}}$ | X | X | I | I | X | X | I |  |
| $X^{x_{3}}$ | X | I | X | I | X | I | X |  |

The two types of checks do different jobs:

- Z checks: choose which computational-basis strings may appear.
- X checks: impose equality relations among the amplitudes of those strings.

Together they define the code space: allowed strings are selected by the Z checks, and their amplitudes are constrained by the X checks. Different X-check orbits can still have independent amplitudes.

A CSS code uses many physical qubits to protect a smaller number of logical qubits. Its stabilizer checks reduce the full state space of $n$ physical qubits from dimension $2^n$ to a much smaller code space of dimension $2^{n-s-t}$.

For example, the Steane code uses 7 physical qubits but encodes only one logical qubit. Its 128 possible physical strings are reduced to 16 by the $Z$-type checks, then to two logical basis states by the $X$-type checks. Each logical state is represented by a superposition of 8 physical strings, providing the redundancy needed to detect and correct errors.

The central idea is a trade-off: more physical qubits are used to represent fewer logical qubits, gaining protection against errors in return.

Toric code

CSS codes use sets of commuting checks to restrict the physical qubits to a smaller code space, protecting a few logical qubits from errors. But increasing the number of physical qubits does not automatically give better protection. To make a larger code correct more errors, its checks may also need to involve more qubits, connecting larger parts of the code. Such checks are harder to measure reliably and require more complex hardware. The challenge is therefore to increase protection while keeping the checks small and local.

The toric code achieves this by keeping every check local: each check touches only four neighboring qubits, regardless of the size of the code. At the same time, the smallest logical operation grows with the lattice, making logical errors increasingly difficult to create.

The toric code arranges its qubits on a repeating square lattice with no boundaries. Opposite sides are identified, so moving across one edge of the lattice brings you back from the opposite side. This turns the flat grid into a torus, where paths can wrap around in two independent directions.

Lattice sizeL = 5

Every edge of the lattice holds one physical qubit. Each of the $L\times L$ cells contributes two edges, its top and its left side, because its bottom and right sides are the top and left sides of the neighboring cells. The dotted copies on the right and bottom of the lattice are these shared edges seen a second time. The total number of physical qubits is therefore $n=2L^2$.

The checks are attached to the tiles and vertices of the lattice. A tile carries a $Z$ check on its four edges, while a vertex carries an $X$ check on the four edges that meet there. When errors occur, they change the outcomes of nearby checks, producing a syndrome that reveals where the error chain begins and ends. A decoder uses this syndrome to choose a correction. All of these steps take place on the same lattice.

Every edge belongs to exactly two tiles, so the product of all tile checks is the identity. The same is true for the vertex checks. Each type therefore has $L^2-1$ independent checks. With $2L^2$ physical qubits, the number of logical qubits the code encodes is (yes, only two logical qubits):

$$
k=2L^2-2(L^2-1)=2.
$$

An $X$ error on an edge flips the outcomes of the two neighboring $Z$ checks. When several $X$ errors form a chain, the checks along the middle of the chain are flipped twice and return to $+1$. Only the two ends remain visible in the syndrome.

If the chain closes, it has no ends and passes every check. Such a closed chain is a loop. A loop around an ordinary region is a product of vertex checks, so it is a stabilizer and leaves the encoded state unchanged. A loop that winds around the torus cannot be produced by local checks, so it acts as a logical operator.

There are two independent ways to wind around the torus, giving two logical $X$ operations. The corresponding $Z$ loops run in the other directions and form the logical $Z$ operations.

The shortest winding loop runs straight along one row or column and contains $L$ qubits. A logical error therefore needs at least $L$ single-qubit errors, so the distance is $d=L$ and grows with the lattice. Together with $n=2L^2$ and $k=2$, this gives the parameters of the toric code:

$$
[[2L^2,2,L]].
$$

For decoding, the syndrome gives the endpoints of the error chains but not their paths. The decoder therefore connects the endpoints with the shortest overall set of paths, using minimum-weight perfect matching. The correction succeeds when its paths reproduce the error chains up to stabilizers. If the chosen paths differ from the actual errors by a winding loop, the correction instead produces a logical error. For an isolated chain shorter than $L/2$, the original path is the shorter route between its endpoints and is therefore recovered correctly.

For independent errors with the same small probability, shorter chains are more likely, so matching looks for the most likely error consistent with the syndrome. Real noise is more complicated: error rates can vary, errors can be correlated, $Y$ errors affect both check types, and measurements can also fail. More advanced decoders account for these effects and for the fact that errors related by stabilizers are physically equivalent, trading accuracy against computational cost.

The toric code has two kinds of local check. A blue tile check applies $Z$ to the four qubits around a square, while a violet vertex check applies $X$ to the four qubits meeting at a vertex:

$$
Z_t=Z_1Z_2Z_3Z_4,\qquad X_v=X_1X_2X_3X_4.
$$

A check measurement returns $+1$ or $-1$. In the absence of errors, every check returns $+1$.

The two checks either share no qubits or share two. Whenever $X$ and $Z$ act on the same qubit, swapping their order introduces a minus sign. Two shared qubits therefore introduce two minus signs, which cancel. Thus every tile check commutes with every vertex check, so all checks can be measured together, regardless of the lattice size:

$$
Z_tX_v=(-1)^2X_vZ_t=X_vZ_t.
$$

The toric code shows how quantum information can be stored in the global structure of a space, rather than in any particular group of qubits. Its local checks remain small as the lattice grows, while its protection comes from the topology of the code.

Surface codes

A toric code is defined on a torus, which is awkward for a planar device because opposite edges must be connected. The code does not actually need this wraparound. Cutting the torus open produces a flat patch called a surface code, using only nearest-neighbor qubits in a plane.

In a planar surface code, interior stabilizers still act on four qubits. At the boundary, some of the qubits that would have continued beyond the edge are absent, so the affected stabilizers have weight three. $Z$-type stabilizers are truncated at the top and bottom boundaries, while $X$-type stabilizers are truncated at the left and right boundaries.

The boundaries also determine which error chains can become logical operations. An $X$ chain can connect the left and right boundaries, while a $Z$ chain can connect the top and bottom boundaries. Such a chain produces no syndrome, so it acts as a logical operator. The shortest chain contains $L$ qubits, giving the code parameters $[[$$L^2+(L-1)^2$$,\,$$1$$,\,L]]$.

Rotated surface code

The rotated surface code rearranges the same surface-code construction into a checkerboard layout. The rotation preserves the code distance and syndrome structure while using fewer physical qubits: $d^2$ instead of $d^2+(d-1)^2$. A distance-5 code, for example, needs 25 qubits instead of 41.

The $d^2$ data qubits form the corners of the checkerboard. Full squares carry four-qubit stabilizers, while boundary plaquettes carry two-qubit stabilizers. $X$- and $Z$-type stabilizers alternate across the patch, with their boundary types arranged to support the same logical operators as the planar code. The patch encodes one logical qubit, giving $[[d^2,\,1,\,d]]$.

The error picture is the same. An error chain normally produces syndrome at its endpoints, while a closed chain produces none. At a boundary, a chain can end without producing a $-1$ outcome.

For example, an $X$ chain connecting the top and bottom boundaries acts as a logical $X$. Its shortest path contains $d$ qubits, so the code distance is $d$.

RotationPlanar code

The rotated code comes from the planar code in three moves, shown here for $d=7$.

1. Draw the checks through their qubits. Each planar-code check acts on the qubits around a tile or vertex. Drawn as the polygon connecting those qubits, each check becomes a diamond: blue for $Z$ checks and violet for $X$ checks. Together, the diamonds form a checkerboard across the patch. Checks cut by the boundary become triangles.

2. Turn the lattice by 45°. The diamonds become upright squares, with a qubit at every corner.

3. Keep only the central $d\times d$ qubits. Checks entirely inside the square keep all four qubits. A check crossing the boundary keeps two. Only one check type is kept on each side: $X$ on the top and bottom, $Z$ on the left and right. This avoids having neighboring checks of different types share a single qubit, which would make them anticommute.

A logical chain from top to bottom still needs one qubit in each of the $d$ rows, so the distance remains $d$. But the number of physical qubits drops:

$$
d^2+(d-1)^2=85\;\longrightarrow\;d^2=49.
$$

The surface code therefore keeps the key protection of the toric code without requiring a torus. Its stabilizers involve only nearby qubits on a flat surface, matching the geometry of physical quantum hardware. The rotated layout goes one step further by reducing the number of physical qubits needed for the same code distance.

The advantage is therefore **not stronger error correction than the toric code**. Both have the same basic topological protection. The surface code is more practical because its geometry fits a planar device, and the rotated version reduces its qubit overhead further.

Color codes

Surface codes are well suited to protecting information on a plane, but their logical gates are less convenient to implement. Color codes use a different lattice structure that makes more logical gates transversal: the gate can be applied independently to each physical qubit, so an error on one qubit does not spread to another.

The key idea is simple. Every face carries both an $X$-type and a $Z$-type stabilizer:

$$
\begin{aligned}Z_f&=\prod_{q\in f}Z_q\\[4pt]X_f&=\prod_{q\in f}X_q.\end{aligned}
$$

The faces are colored so that neighboring faces have different colors. This three-coloring is what gives color codes their name, while the underlying geometry ensures that different faces share either no qubits or two. An $X$ and $Z$ check therefore anticommute twice when they overlap, so the two minus signs cancel and all checks commute.

Because every face has both an $X$ check and a $Z$ check, swapping $X$ and $Z$ leaves the code unchanged. Applying $H$ to every physical qubit performs exactly this swap, so the code space is preserved and the logical qubit undergoes an $H$ gate. Since each $H$ acts on one qubit independently, an error on one qubit cannot spread to another during the operation. This is the transversal property: in two-dimensional color codes, every Clifford gate can be implemented by gates that never couple two qubits of the same code block.

The smallest example of a color code is the: seven qubits arranged as a triangle with three faces. Each face carries one $X$ and one $Z$ check, giving the six stabilizer generators. Larger color codes use the same construction on larger lattices, such as triangles tiled with hexagons. Their distance increases with the lattice size while preserving the same transversal-gate structure. As with the surface code, the whole lattice still encodes only one logical qubit, however large it grows.

Distanced = 7, 37 qubits

A color code places qubits at the corners of a honeycomb lattice cut into a triangle. Along the three sides, the boundary cuts the hexagons down to four-qubit faces.

For distance $d$, the triangle has $n=(3d^2+1)/4$ qubits and $(n-1)/2$ faces. Each face gives one $X$ and one $Z$ check, so there are $n-1$ independent checks, leaving one logical qubit:

$$
k=n-(n-1)=37-36=1.
$$

provide the basic structure for detecting errors. use two such structures to build a quantum code, with one detecting bit flips and the other detecting phase flips. The arranges these checks on a lattice wrapped around a torus, so that each one acts only on nearby qubits. cut the torus open into a flat patch, and the rotated layout reaches the same distance with fewer qubits. keep the checks local on a three-colored lattice, with both an $X$ check and a $Z$ check on every face.

These codes share a cost. A standard surface-code patch of distance $d$ stores one logical qubit, so storing more logical qubits requires more patches, while the number of physical qubits per patch grows roughly as $d^2$. Much of current research therefore looks for codes that store many logical qubits in a single code while keeping each check small:

- The gross code is a $[[144,12,12]]$ code from the bivariate bicycle family. It stores twelve logical qubits in 144 physical ones, needs another 144 qubits for syndrome measurements, and can be laid out on two planar layers of connections ([Bravyi et al., 2023](https://arxiv.org/abs/2308.07915)).
- Quantum LDPC codes keep every check on only a few qubits without requiring a flat lattice. Some families can grow both the number of logical qubits and the distance with the size of the code ([Panteleev and Kalachev, 2021](https://arxiv.org/abs/2111.03654)).
- Floquet codes have no fixed set of stabilizers. Instead, their logical information is protected by a repeating sequence of two-qubit measurements ([Hastings and Haah, 2021](https://arxiv.org/abs/2107.02194)).
- Subsystem codes such as the Bacon–Shor code leave some degrees of freedom unprotected, allowing the remaining checks to be simpler to measure ([Bacon, 2005](https://arxiv.org/abs/quant-ph/0506023)).
- Bosonic codes such as the GKP code store a qubit in the continuous states of a single oscillator instead of distributing it across many two-level systems ([Gottesman, Kitaev and Preskill, 2000](https://arxiv.org/abs/quant-ph/0008040)).

The original papers behind these codes develop their ideas in full:

- Kitaev, 1997. [Fault-tolerant quantum computation by anyons](https://arxiv.org/abs/quant-ph/9707021)
- Bombin and Martin-Delgado, 2006. [Topological quantum distillation](https://arxiv.org/abs/quant-ph/0605138)
- Fowler, Mariantoni, Martinis and Cleland, 2012. [Surface codes: Towards practical large-scale quantum computation](https://arxiv.org/abs/1208.0928)
- Google Quantum AI, 2024. [Quantum error correction below the surface code threshold](https://arxiv.org/abs/2408.13687)

The [Error Correction Zoo](https://errorcorrectionzoo.org/) catalogs hundreds of codes, their parameters, and the relationships between them. It is a useful reference when encountering a code elsewhere.

## Fault-tolerant quantum computing

A quantum computer cannot simply encode information and assume the rest of the computation is reliable. Its qubits must be prepared, manipulated, and measured, while the error-correction process itself is also imperfect. Fault-tolerant quantum computing is the set of techniques that makes these operations reliable despite those faults.

The key is to design the computation so that errors remain controlled and can be detected and corrected before they accumulate. This leads to the threshold theorem: below a certain physical error rate, increasing the amount of error correction can make an arbitrarily long quantum computation arbitrarily reliable.

Faults and the noise model

A fault-tolerance analysis starts with the circuit to be implemented and asks where it can fail. Classical computation is assumed to be perfect, but anything involving quantum information may be faulty: preparing a qubit, applying a gate, measuring a qubit, and even storing a qubit while it waits.

The standard starting point is the independent stochastic noise model. In this model, faults are assumed to be uncorrelated and to occur independently at each possible fault location with a given probability. Real devices are likely to exhibit some correlations between errors, so this model is only a first approximation to them.

The example is the circuit for. A Hadamard and a CNOT turn two qubits in $|0\rangle$ into an entangled pair. Two measurements and two corrections controlled by their outcomes then move the state $|\psi\rangle$ from the first qubit to the third.

The circuit is small but uses every kind of operation: a state preparation, one- and two-qubit gates, measurements, and gates controlled by classical bits. On real hardware, each of them can go wrong.

Fault-tolerant quantum circuits

A logical circuit is implemented fault-tolerantly by encoding each logical qubit into a quantum error-correcting code and replacing each logical operation with a fault-tolerant gadget. A gadget is a small physical circuit that performs the desired logical operation on one or more encoded qubits while limiting how a physical fault can spread through the code block. It may include physical gates, extra ancillas, measurements, and intermediate error-correction steps.

Error correction is performed throughout the computation rather than only at the end. The goal is not to prevent every physical fault, but to ensure that a small number of faults produces only a small number of errors in the encoded qubits, so that later correction can remove them.

A fault-tolerant implementation starts with a logical circuit: the computation to be performed, before choosing how to protect it against faults.

Here, the logical circuit is the teleportation circuit, with one wire representing each logical qubit.

Each round of error correction is a substantial circuit. It measures the code's stabilizers using extra ancilla qubits, many two-qubit gates, and measurements, then uses a classical decoder to choose the correction. A round runs on every block after each gadget, so a single logical gate can require hundreds of physical operations, while each logical qubit occupies many physical qubits.

With this much overhead, it is not obvious that encoding helps at all. If the physical operations are too noisy, the additional faults introduced by the larger circuit outweigh the errors that correction removes. The encoded circuit can then fail more often than the corresponding unencoded circuit.

Error propagation

Two-qubit gates can spread errors, even when the gates are perfect. A CNOT propagates an $X$ error from its control to its target and a $Z$ error from its target to its control. Thus, an error on one qubit can become a correlated error on both:

$$
\begin{aligned}\mathrm{CNOT}\,(X\otimes I)&=(X\otimes X)\,\mathrm{CNOT}\\[4pt]\mathrm{CNOT}\,(I\otimes Z)&=(Z\otimes Z)\,\mathrm{CNOT}.\end{aligned}
$$

Repeated gates can spread a single error to many qubits, so a single fault may produce more errors within a block than the code can correct. Fault-tolerant gadgets must therefore prevent errors from spreading within a block.

Pauli errorError before the gates: $X$, $Z$, $Y$ or none

Some codes allow transversal implementations of certain gates. A transversal gate acts independently on corresponding qubit positions, without coupling two qubits within the same block.

For example, a transversal CNOT applies a CNOT between each qubit of one block and the corresponding qubit of another block. A single fault can therefore affect at most one qubit in each block, rather than spreading across a block.

Block A: 1 error · Block B: 1 error

Pauli errorError before the gates: $X$, $Z$, $Y$ or noneCode block of three qubits

Different code families support different sets of transversal gates. All stabilizer codes have transversal Pauli gates, while all CSS codes have a transversal CNOT. Some codes support larger sets: the Steane code, for example, supports all Clifford gates transversally.

Transversal gates are an important building block of fault-tolerant computation. They prevent a single fault from spreading to multiple qubits within a code block, allowing error correction to remove the resulting errors. They cannot, however, provide a universal gate set. By the [Eastin–Knill theorem](https://arxiv.org/abs/0811.4262), any quantum error-correcting code with distance at least 2 has only a non-universal set of logical gates that can be implemented transversally.

Magic states

Transversal gates provide a fault-tolerant way to implement many logical operations, but they cannot form a universal gate set on their own. The gate that is usually missing is the non-Clifford $T$ gate, and since Clifford gates together with $T$ form a, a fault-tolerant computer needs another way to implement it.

The key idea is magic-state injection — instead of implementing $T$ directly as a transversal gate, prepare a special ancillary state, the magic state, and use it with Clifford gates and measurements:

$$
T|+\rangle=\frac{1}{\sqrt2}\bigl(|0\rangle+e^{i\pi/4}|1\rangle\bigr).
$$

Let the data qubit hold $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$ and let a second qubit hold the magic state. A CNOT with the data qubit as control and the magic qubit as target flips the magic qubit in every term where the data qubit is $|1\rangle$. Collecting the terms by the value of the magic qubit splits the state into two branches, $T|\psi\rangle$ and, after factoring out $e^{i\pi/4}$, $T^{\dagger}|\psi\rangle$:

$$
\begin{aligned}\mathrm{CNOT}\bigl(\textcolor{#0369a1}{|\psi\rangle}\otimes \textcolor{#a21caf}{T|+\rangle}\bigr)&=\frac{1}{\sqrt2}\,\mathrm{CNOT}\Bigl(\bigl(\textcolor{#0369a1}{\alpha}|0\rangle+\textcolor{#0369a1}{\beta}|1\rangle\bigr)\otimes\textcolor{#a21caf}{\bigl(|0\rangle+e^{i\pi/4}|1\rangle\bigr)}\Bigr)\\[4pt]&=\frac{1}{\sqrt2}\Bigl(\textcolor{#0369a1}{\alpha}|0\textcolor{#a21caf}{0}\rangle+e^{i\pi/4}\textcolor{#0369a1}{\alpha}|0\textcolor{#a21caf}{1}\rangle+\textcolor{#0369a1}{\beta}|1\textcolor{#a21caf}{1}\rangle+e^{i\pi/4}\textcolor{#0369a1}{\beta}|1\textcolor{#a21caf}{0}\rangle\Bigr)\\[4pt]&=\frac{1}{\sqrt2}\Bigl(\bigl(\textcolor{#0369a1}{\alpha}|0\rangle+e^{i\pi/4}\textcolor{#0369a1}{\beta}|1\rangle\bigr)\otimes\textcolor{#a21caf}{|0\rangle}+\bigl(e^{i\pi/4}\textcolor{#0369a1}{\alpha}|0\rangle+\textcolor{#0369a1}{\beta}|1\rangle\bigr)\otimes\textcolor{#a21caf}{|1\rangle}\Bigr)\\[4pt]&=\frac{1}{\sqrt2}\Bigl(\underbrace{\bigl(\textcolor{#0369a1}{\alpha}|0\rangle+e^{i\pi/4}\textcolor{#0369a1}{\beta}|1\rangle\bigr)}_{T\textcolor{#0369a1}{|\psi\rangle}}\otimes\textcolor{#a21caf}{|0\rangle}+e^{i\pi/4}\underbrace{\bigl(\textcolor{#0369a1}{\alpha}|0\rangle+e^{-i\pi/4}\textcolor{#0369a1}{\beta}|1\rangle\bigr)}_{T^{\dagger}\textcolor{#0369a1}{|\psi\rangle}}\otimes\textcolor{#a21caf}{|1\rangle}\Bigr)\\[4pt]&=\frac{1}{\sqrt2}\,T\textcolor{#0369a1}{|\psi\rangle}\otimes\textcolor{#a21caf}{|0\rangle}+\frac{e^{i\pi/4}}{\sqrt2}\,T^{\dagger}\textcolor{#0369a1}{|\psi\rangle}\otimes\textcolor{#a21caf}{|1\rangle}.\end{aligned}
$$

Both branches have weight $1/2$, so measuring the magic qubit gives $0$ or $1$ with probability $1/2$ each, independently of $|\psi\rangle$. Outcome $0$ leaves $T|\psi\rangle$ on the data qubit and needs no correction. Outcome $1$ leaves $T^{\dagger}|\psi\rangle$ up to a global phase, and applying $S$ turns it into $T|\psi\rangle$:

$$
ST^{\dagger}=\begin{pmatrix}1&0\\0&i\end{pmatrix}\begin{pmatrix}1&0\\0&e^{-i\pi/4}\end{pmatrix}=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}=T.
$$

With this measurement-dependent correction, the circuit applies $T$ to $|\psi\rangle$ on every run and consumes one magic state. The same idea implements $S$ using the state $S|+\rangle=|{+i}\rangle$, with $Z$ as the correction. The circuit also works on encoded qubits. With fault-tolerant gadgets and an encoded magic state, it implements a fault-tolerant $T$ gate.

Input

Outcome

After the measurement

$$
T^{\dagger}|\psi\rangle=0.6|0\rangle+(0.566-0.566i)|1\rangle
$$

After S

$$
0.6|0\rangle+(0.566+0.566i)|1\rangle
$$

Equals T|ψ⟩

$$
T|\psi\rangle=0.6|0\rangle+(0.566+0.566i)|1\rangle
$$

Encoded magic states can be prepared through a probabilistic process that does not have to succeed on every attempt. In magic state distillation, several noisy magic states are fed into a distillation circuit, which produces one candidate output while measuring the others. If all measurements give $0$, the output is accepted as a less noisy magic state. If any measurement gives $1$, the attempt is discarded and repeated with a fresh set of noisy states. Repeating the process produces a supply of high-quality magic states from many successful attempts.

Magic-state injection and distillation provide a general way to implement the non-Clifford gates needed for a universal fault-tolerant gate set. Other approaches to fault-tolerant gate implementation include [code deformation](https://arxiv.org/abs/0704.2540) and [code switching](https://arxiv.org/abs/1403.2734).

Fault-tolerant error correction

Error correction is a circuit too, and, as you might expect, straightforward syndrome measurement is not fault-tolerant either. To measure a generator such as $Z\otimes Z\otimes Z$, one ancilla qubit in $|+\rangle$ interacts with each data qubit in turn and is then measured in the $\pm$ basis. A single fault on the ancilla can spread to multiple data qubits, producing an error within the code block that is too large for the code to correct.

There are several ways to avoid this:

- Shor error correction measures each generator using a cat state $\bigl(|000\rangle+|111\rangle\bigr)/\sqrt2$, with one ancilla qubit for each data qubit. The syndrome is then computed from the measurement results.
- Steane error correction, which works only for CSS codes, uses an encoded state such as $|+\rangle_L$ as the ancilla. A transversal CNOT transfers the relevant data information to the encoded ancilla, which is then measured. The syndrome is again extracted classically from the measurement results.

In both schemes, each ancilla qubit interacts with at most one data qubit, so a single fault can cause at most one data-qubit error. Later rounds of error correction can remove such errors. A fault can still corrupt a syndrome bit, so in practice the syndrome is measured multiple times before applying the correction.

1 fault → 2 data errors, too many for the code to correct

FaultWhere the error spreadsData error after the gatesPlace for a fault

Phew! At this point the whole thing can start to look like an endless loop. Protecting the data takes extra ancilla qubits, gates, and measurements, and each of them is one more place where a fault can occur. Protecting those takes even more qubits, which bring faults of their own, which need protecting too… Whether this chase ever ends depends on how noisy the physical components are.

Threshold theorem

Informally, the [threshold theorem](https://arxiv.org/abs/quant-ph/9906129) says that a quantum circuit with $N$ gates can be implemented with arbitrarily high accuracy using noisy gates, as long as the error probability at each physical location is below a fixed, nonzero threshold $p_{\mathrm{th}}>0$. The resulting noisy circuit needs only $O(N\log^c N)$ locations, for some positive constant $c$.

The idea can already be seen with, for example, the, whose error correction removes any single error in a block. A logical location then fails only if at least two faults occur within its fault-tolerant gadget. The probability of this is at most $Cp^2$, where $C$ is a constant that counts the relevant pairs of locations. If $p<1/C=p_{\mathrm{th}}$, this is smaller than $p$: the logical error rate is reduced from $p$ to at most $(Cp)p$.

The key step is concatenation: treat the first-level fault-tolerant circuit as a logical circuit and encode it again. Each gadget and each round of error correction then becomes a fault-tolerant circuit at the next level.

Error rate per location: $p$

Each level squares the ratio of the error rate to the threshold, so the logical error rate falls rapidly with every level:

$$
\begin{aligned}p&\;\mapsto\;Cp^2=(Cp)\,p\\[2pt]&\;\mapsto\;C\bigl((Cp)\,p\bigr)^2=(Cp)^3\,p\\[2pt]&\;\mapsto\;C\bigl((Cp)^3p\bigr)^2=(Cp)^7\,p\\[2pt]&\;\mapsto\;\cdots\;\mapsto\;(Cp)^{2^k-1}\,p.\end{aligned}
$$

Gadget constant $C$

Physical error rate p0.0032

Below the threshold $p_{\mathrm{th}}=1/C$

|  | no encoding | 0.0032 |
| --- | --- | --- |
|  | 1 level | 1.0×10⁻³ |
|  | 2 levels | 1.0×10⁻⁴ |
|  | 3 levels | 1.0×10⁻⁶ |
|  | 4 levels | 1.0×10⁻¹⁰ |

To make the whole circuit succeed with high probability, the logical error rate must become much smaller than $1/N$, since the circuit has $N$ locations. Below the threshold, error correction can reduce the logical error rate rapidly enough that only about $\log\log N$ levels of error correction are needed. Each level increases the circuit size by only a constant factor, so the total overhead is polylogarithmic in $N$, giving the $O(N\log^c N)$ circuit size stated by the theorem.

Congratulations on making it this far!

The road was long: from bits and qubits through measurements, entanglement and quantum algorithms, to channels, error correction and fault tolerance. If something along the way did not make sense, feel free to message me at [hello@annaburd.me](mailto:hello@annaburd.me). I spent a long time working through this material myself.

So what is the takeaway? Quantum computing has another problem beyond the algorithms themselves: making a real quantum computer useful. The hardware is expensive, the qubits are fragile, and useful computations require keeping errors under control. A logical qubit requires many physical qubits, a logical gate requires many physical operations and error-correction steps, and none of this works unless the physical error rate is below the threshold.

So when you see a headline about a quantum computer with thousands of qubits, ask:

- Are they physical or logical qubits?
- What are the gate and measurement error rates, and are they below the code's threshold?
- How many logical qubits does the machine actually provide, and for how long can they run reliably?

A thousand noisy physical qubits may amount to only a handful of logical qubits. If the physical error rate is above the threshold, they may not provide any reliable logical qubits at all.

These notes are based on John Watrous's [Understanding Quantum Information and Computation](https://www.youtube.com/playlist?list=PLOFEBzvs-VvqKKMXX4vbi4EB1uaErFMSO), made with IBM Quantum, with additional explanations, derivations and interactive demos.