Chapter 18: The Stabilizer Formalism

18.1 The Pauli Group and Stabilizer States

The stabilizer formalism is built on top of the Pauli group, so we begin there. Recall the four single-qubit Pauli operators:

Each Pauli operator is both Hermitian ($P = P^\dagger$) and unitary ($PP^\dagger = I$). This means each Pauli is its own inverse: $P^2 = I$. Their eigenvalues are $\pm 1$. The physical interpretations are familiar: $X$ is a bit-flip, $Z$ is a phase-flip, and $Y = iXZ$ combines both.

The Single-Qubit Pauli Group

The single-qubit Pauli group $\mathcal{P}_1$ consists of all Pauli operators multiplied by the phases $\{\pm 1, \pm i\}$:

This is a group of order 16 under matrix multiplication. The crucial algebraic property is the commutation relations. Any two Pauli operators either commute or anticommute:

More precisely, for any two single-qubit Paulis $P$ and $Q$, we have either $PQ = QP$ (they commute) or $PQ = -QP$ (they anticommute). There is no middle ground. This binary commutation structure is what makes the entire stabilizer formalism tick.

The $n$-Qubit Pauli Group

For $n$ qubits, the Pauli group $\mathcal{P}_n$ consists of all $n$-fold tensor products of single-qubit Paulis, with overall phases $\{\pm 1, \pm i\}$:

We often write these tensor products as Pauli strings, dropping the $\otimes$ symbol. For example, on three qubits, $X \otimes I \otimes Z$ is written simply as $XIZ$. The group $\mathcal{P}_n$ has order $4 \cdot 4^n$ (four phase choices times $4^n$ Pauli strings).

The commutation rule extends: two $n$-qubit Pauli strings either commute or anticommute, determined by counting the number of positions where the corresponding single-qubit Paulis anticommute. If this count is even, the strings commute; if odd, they anticommute.

Stabilizer States

A stabilizer state is a quantum state $|\psi\rangle$ that is the simultaneous $+1$ eigenstate of a set of commuting Pauli operators. More precisely, suppose $\mathcal{S}$ is an abelian (all-commuting) subgroup of $\mathcal{P}_n$ that does not contain $-I$, generated by $n$ independent generators $g_1, g_2, \ldots, g_n$. Then there is a unique $n$-qubit state $|\psi\rangle$ such that:

This state $|\psi\rangle$ is the stabilizer state defined by $\mathcal{S}$, and $\mathcal{S}$ is called its stabilizer group. The generators $g_i$ are the stabilizer generators.

For example, the single-qubit state $|0\rangle$ is stabilized by $Z$ (since $Z|0\rangle = +|0\rangle$). The state $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ is stabilized by $X$. The two-qubit Bell state $|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ is stabilized by the group generated by $\{XX, ZZ\}$, since $XX|\Phi^+\rangle = |\Phi^+\rangle$ and $ZZ|\Phi^+\rangle = |\Phi^+\rangle$.

The power of this description is its compactness. An $n$-qubit quantum state generally requires $2^n$ complex amplitudes to describe. But a stabilizer state is fully specified by $n$ generators, each a string of $n$ Pauli operators - only $O(n^2)$ bits of classical information. This exponential compression is the engine that drives efficient classical simulation of stabilizer circuits (Section 18.4) and compact descriptions of quantum codes (Section 18.2).

The Stabilizer Tableau

The compact representation of stabilizer states is formalized as a stabilizer tableau: a binary matrix of size $n \times 2n$ where each row represents one generator. For each generator, the first $n$ columns encode whether $X$ appears at each qubit position, and the second $n$ columns encode whether $Z$ appears. A $Y$ at position $j$ is represented by setting both the $X$ and $Z$ bits for that position (since $Y = iXZ$). An additional column of phase bits records the overall sign.

For example, the Bell state $|\Phi^+\rangle$ on two qubits has generators $XX$ and $ZZ$. The tableau is:

Clifford gates act on this tableau by simple binary row operations: the Hadamard gate swaps the $X$ and $Z$ columns for a qubit, the $S$ gate adds the $X$ column to the $Z$ column (modulo 2), and the CNOT gate performs column additions between the control and target. This is why Clifford circuits can be simulated in $O(n^2)$ time per gate - the Gottesman-Knill theorem in action (Section 18.4).

18.2 Stabilizer Codes: A Unified Framework

A stabilizer code is the natural generalization of a stabilizer state to an error-correcting code. Instead of stabilizing a single state, we stabilize a subspace - the code space - in which quantum information is protected.

The $[[n, k, d]]$ Notation

A quantum stabilizer code is characterized by three parameters, written in double-bracket notation as $[[n, k, d]]$:

• $n$ = number of physical qubits used
• $k$ = number of logical qubits encoded (the useful information)
• $d$ = code distance (the minimum weight of an undetectable error)

The code is defined by an abelian subgroup $\mathcal{S} \subset \mathcal{P}_n$ with $n - k$ independent generators $g_1, \ldots, g_{n-k}$, none of which is $-I$. The code space $\mathcal{C}$ is the simultaneous $+1$ eigenspace:

This subspace has dimension $2^k$, encoding $k$ logical qubits. When $k = 0$, we recover a stabilizer state. When $k > 0$, we have a proper error-correcting code with a $2^k$-dimensional code space.

Error Detection via Syndromes

The magic of stabilizer codes lies in how they detect errors. Suppose an error $E$ (which is itself a Pauli operator, since any error can be decomposed into Pauli errors) acts on an encoded state $|\psi\rangle \in \mathcal{C}$. For each stabilizer generator $g_i$, we measure the eigenvalue of $g_i$ on the corrupted state $E|\psi\rangle$. Two cases arise:

• If $E$ commutes with $g_i$, then $g_i(E|\psi\rangle) = E(g_i|\psi\rangle) = E|\psi\rangle$, so the eigenvalue is $+1$.
• If $E$ anticommutes with $g_i$, then $g_i(E|\psi\rangle) = -E(g_i|\psi\rangle) = -E|\psi\rangle$, so the eigenvalue is $-1$.

The list of measured eigenvalues $(s_1, s_2, \ldots, s_{n-k})$, where each $s_i \in \{+1, -1\}$, is called the error syndrome. It tells us which stabilizer generators the error anticommutes with, without revealing any information about the encoded logical state. This is the crucial point: syndrome measurement projects onto an error subspace without collapsing the logical superposition.

The Error Correction Conditions

A stabilizer code with distance $d$ can detect any error of weight up to $d - 1$ (affecting at most $d - 1$ qubits) and correct any error of weight up to $\lfloor(d-1)/2\rfloor$. The weight of a Pauli error is the number of non-identity tensor factors. For example, $XIZ$ has weight 2.

An error $E$ is undetectable if and only if it commutes with every stabilizer generator but is not itself in the stabilizer group. Such operators are called logical operators - they act nontrivially on the encoded information. The code distance $d$ is the minimum weight of any logical operator.

Logical Operators

The normalizer $N(\mathcal{S})$ of the stabilizer group consists of all Pauli operators that commute with every element of $\mathcal{S}$. The logical operators are elements of $N(\mathcal{S})$ that are not in $\mathcal{S}$ itself. For a $[[n, k, d]]$ code, there are $k$ pairs of logical operators $(\bar{X}_j, \bar{Z}_j)$ for $j = 1, \ldots, k$, satisfying the same algebra as physical Paulis:

These logical operators act on the encoded qubits within the code space, performing logical bit-flips and phase-flips on the protected information.

18.3 The Steane Code and the 5-Qubit Code

The $[[7,1,3]]$ Steane Code

Andrew Steane's code, introduced in 1996, encodes one logical qubit into seven physical qubits and can correct any single-qubit error. It is a CSS code (Calderbank-Shor-Steane), meaning its stabilizer generators split neatly into $X$-type and $Z$-type generators. The six stabilizer generators are:

Notice the structure: $g_1, g_2, g_3$ are purely $X$-type and $g_4, g_5, g_6$ are purely $Z$-type, with the same support patterns. This CSS structure arises because the Steane code is built from the classical $[7, 4, 3]$ Hamming code and its dual. The logical operators are $\bar{X} = XXXXXXX$ and $\bar{Z} = ZZZZZZZ$ (all-$X$ and all-$Z$ on every qubit).

Syndrome Decoding Example

Suppose a bit-flip error $X_3$ (an $X$ error on qubit 3) occurs. We measure the syndrome by checking which $Z$-type generators anticommute with $X_3$:

• $g_4 = IIIZZZZ$: qubit 3 has $I$, so $[g_4, X_3] = 0$ - syndrome bit is $+1$.
• $g_5 = IZZIIZZ$: qubit 3 has $Z$, and $ZX = -XZ$, so syndrome bit is $-1$.
• $g_6 = ZIZIZIZ$: qubit 3 has $Z$, so syndrome bit is $-1$.

The syndrome $(+1, -1, -1)$ or equivalently the binary string $(0, 1, 1)$ uniquely identifies qubit 3. In fact, $011$ is the binary representation of 3 - the Hamming code structure makes syndrome decoding as simple as reading off the error location in binary.

The $[[5,1,3]]$ Perfect Code

The smallest possible code that can correct an arbitrary single-qubit error uses five qubits. This $[[5, 1, 3]]$ code, discovered independently by Laflamme, Miquel, Paz, and Zurek (1996) and by Bennett, DiVincenzo, Smolin, and Wootters (1996), is called perfect because it saturates the quantum Hamming bound: with $n = 5$ physical qubits and $k = 1$ logical qubit, we have $n - k = 4$ syndrome bits, which can distinguish $2^4 = 16$ syndromes - exactly the number needed for no error ($1$) plus a single $X$, $Y$, or $Z$ error on any of the 5 qubits ($3 \times 5 = 15$).

The four stabilizer generators are:

Notice the cyclic structure: each generator is a cyclic shift of the previous one (with some sign adjustments). The logical operators are $\bar{X} = XXXXX$ and $\bar{Z} = ZZZZZ$.

Sandbox: The 3-Qubit Bit-Flip Code

The simplest stabilizer code is the $[[3,1,1]]$ bit-flip repetition code (it can correct any single $X$ error, but has distance 1 against general Pauli errors since it cannot detect $Z$ errors). It encodes $|0\rangle \to |000\rangle$ and $|1\rangle \to |111\rangle$. The stabilizer generators are $g_1 = ZZI$ and $g_2 = IZZ$. In the sandbox below, we encode a qubit, introduce a deliberate bit-flip error on the first qubit, measure the syndrome, and correct it. Try modifying which qubit gets the error.

With the error on qubit 0, the syndrome qubits $q[3]$ and $q[4]$ should read $10$ (generator $ZZI$ flipped, $IZZ$ unchanged), correctly identifying the error location. Change x q[0]; to x q[1]; or x q[2]; to see how the syndrome changes for errors on different qubits.

Interactive: Stabilizer Tableau Step-Through

One of the key insights of the stabilizer formalism is that Clifford gates transform stabilizer generators in predictable ways. The widget below lets you step through a GHZ-state preparation circuit gate by gate, watching how the stabilizer generators evolve at each step. The initial state $|000\rangle$ is stabilized by $\{+ZII, +IZI, +IIZ\}$. Each Clifford gate transforms these generators according to the conjugation rules.

After the full circuit, the stabilizers should be $\{+XXX, +ZZI, +ZIZ\}$ - the canonical stabilizers of the 3-qubit GHZ state $\frac{1}{\sqrt{2}}(|000\rangle + |111\rangle)$. Notice how the Hadamard on qubit 0 swaps the $X$ and $Z$ operators on that qubit, and each CNOT propagates the $X$ from control to target while propagating $Z$ from target to control.

Interactive: Clifford Simulator Scalability

The Gottesman-Knill theorem guarantees that Clifford circuits can be simulated efficiently on a classical computer. Goqu's stabilizer simulator demonstrates this directly. The circuit below applies H and CNOT gates to create a GHZ state on 4 qubits. The Clifford simulator tracks the full stabilizer tableau, showing how entanglement propagates through each gate.

18.4 The Gottesman-Knill Theorem

The stabilizer formalism is not only a framework for error correction - it also reveals a deep boundary between classical and quantum computational power. The Gottesman-Knill theorem draws this boundary with remarkable precision.

Clifford Gates

A Clifford gate is a unitary operation that maps Pauli operators to Pauli operators under conjugation. That is, a gate $U$ is Clifford if for every Pauli $P$, the operator $UPU^\dagger$ is also a Pauli (up to phase). The set of all $n$-qubit Clifford gates forms the Clifford group $\mathcal{C}_n$.

The Clifford group is generated by just three gates:

• The Hadamard gate $H$: maps $X \to Z$ and $Z \to X$. $$H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$
• The phase gate $S$: maps $X \to Y$ and $Z \to Z$. $$S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}$$
• The CNOT gate: maps $XI \to XX$, $IX \to IX$, $ZI \to ZI$, $IZ \to ZZ$.

Any Clifford circuit - composed of $H$, $S$, and CNOT gates - transforms stabilizer generators to stabilizer generators. This means that if we start with a stabilizer state (such as $|0\rangle^{\otimes n}$, stabilized by $Z_1, Z_2, \ldots, Z_n$), the output of a Clifford circuit is always another stabilizer state, fully described by the transformed generators.

The Theorem

The proof is constructive. A classical computer maintains a stabilizer tableau: an $n \times 2n$ binary matrix that tracks how each stabilizer generator is expressed as a Pauli string, plus a column of phase bits. Each Clifford gate updates this tableau by simple row operations - no exponentially large state vector is ever needed. Measurements project onto stabilizer eigenspaces and can also be handled with $O(n^2)$ classical operations.

Implications

The Gottesman-Knill theorem tells us that Clifford circuits alone, despite being capable of producing highly entangled states (like GHZ states and cluster states), do not provide quantum speedup. They are classically simulable.

Quantum computational advantage requires going beyond the Clifford group. The most common way is to add a non-Clifford gate such as the $T$ gate:

The $T$ gate maps $X \to (X + Y)/\sqrt{2}$, which is not a Pauli operator. Adding $T$ to the Clifford generating set produces a universal gate set - one that can approximate any unitary operation to arbitrary precision. This is the Clifford + $T$ gate set, and it is the standard gate set for fault-tolerant quantum computing (Chapter 20).

Counting Clifford Gates

The size of the $n$-qubit Clifford group is known exactly:

For $n = 1$, this gives $|\mathcal{C}_1| = 24$ - the 24 single-qubit Clifford gates, which form the symmetry group of the octahedron (the rotations and reflections that map the three Pauli axes to one another). For $n = 2$, $|\mathcal{C}_2| = 11{,}520$. The group grows rapidly, but it remains a vanishingly small fraction of the full unitary group $U(2^n)$ for large $n$.

Beyond Clifford: The Role of $T$ Count

Since Clifford gates are classically simulable, the computational "difficulty" of a quantum circuit is largely determined by its $T$ count - the number of $T$ gates (or more generally, non-Clifford gates) it contains. In fault-tolerant quantum computing, each $T$ gate requires a costly magic state (Chapter 20), so minimizing the $T$ count of a quantum algorithm is a major optimization goal. The field of $T$-count optimization uses the stabilizer formalism and related algebraic tools to rewrite circuits with fewer $T$ gates while preserving their action.

18.5 Decoding: How to Identify and Fix Errors

Measuring the error syndrome tells us something about what went wrong, but translating that syndrome into a specific correction is a computational problem called decoding. The decoder is a classical algorithm that runs alongside the quantum computer, processing syndrome data in real time and issuing correction commands.

The Decoding Problem

Given a syndrome $\mathbf{s} = (s_1, \ldots, s_{n-k})$, the decoder must identify a Pauli correction $R$ such that applying $R$ returns the corrupted state to the code space. The subtlety is that the correction need not match the actual error exactly - it just needs to differ from the actual error by an element of the stabilizer group (which acts trivially on the code space). More formally, if the actual error was $E$ and we apply correction $R$, the net operation is $RE$. This is harmless if and only if $RE \in \mathcal{S}$ (or more generally, $RE$ is a stabilizer times a logical identity).

Minimum-Weight Decoding

The most natural decoding strategy is minimum-weight decoding: given the syndrome, find the lowest-weight Pauli error consistent with it. The rationale is that in a depolarizing noise model, lower-weight errors are more probable, so the minimum-weight correction is the maximum-likelihood correction.

For small codes, minimum-weight decoding can be done by lookup table: precompute the syndrome for every correctable error and store the mapping. For the $[[7,1,3]]$ Steane code, there are only $1 + 3 \times 7 = 22$ single-qubit errors (including no error), so a lookup table with 22 entries suffices.

Challenges for Large Codes

For large codes like the surface code (Chapter 19), minimum-weight decoding becomes an optimization problem. The syndrome is a pattern of "defects" on a lattice, and the decoder must pair them up using paths of minimum total weight. This is equivalent to a minimum-weight perfect matching (MWPM) problem on a graph, which can be solved in polynomial time using Edmonds' blossom algorithm.

Other decoding strategies include:

• Union-find decoders: near-linear time algorithms that group syndrome defects into clusters and correct each cluster independently. They sacrifice some accuracy for speed.
• Belief propagation: iterative message-passing algorithms adapted from classical coding theory, effective for quantum LDPC codes.
• Machine-learning decoders: neural networks trained on syndrome data, potentially offering good accuracy with fast inference times.

Degeneracy: A Quantum Advantage

Quantum codes have a feature absent in classical codes: degeneracy. Multiple distinct physical errors can have the same syndrome and the same effect on the code space. For instance, if errors $E_1$ and $E_2$ have the same syndrome and $E_1 E_2 \in \mathcal{S}$, then they are indistinguishable from the code's perspective and do not need to be distinguished by the decoder. This means a quantum code can effectively correct more errors than a naive counting argument would suggest.

Degeneracy is especially important for topological codes like the surface code, where many different error chains produce the same syndrome pattern. A good decoder exploits degeneracy to achieve higher effective error suppression.