The Stabilizer Formalism

Chapter 2 introduced the single-qubit Pauli matrices $X$, $Y$, $Z$ alongside the identity $I$. Their multiplication is closed up to phases — $X^2=Y^2=Z^2=I$, $XY=iZ$, $YX=-iZ$, and so on around the cycle. To make a genuine group we must carry those phases along. The single-qubit Pauli group is

sixteen elements in all. The $n$-qubit Pauli group ${\mathcal{P}}_n$ is built from tensor products of these — one factor per qubit — again with an overall phase $\pm 1,\pm i$:

We write such an element compactly by dropping the tensor signs: $X\otimes X$ becomes XX, and $Z\otimes I\otimes Z$ becomes ZIZ. Every element squares to $\pm I$, and every element is either Hermitian (phase $\pm 1$) or anti-Hermitian (phase $\pm i$); the Hermitian ones with eigenvalues $\pm 1$ are the observables we will measure.

One structural fact powers everything that follows. Take any two elements of ${\mathcal{P}}_n$. On each qubit their single-qubit factors either commute (if either is $I$, or they are equal) or anticommute (two distinct non-identity Paulis). Multiplying the qubits together, the total sign is the parity of the number of anticommuting positions. Hence:

There is no middle ground — two Paulis commute or anticommute, never anything else. That clean dichotomy is exactly what lets us replace a state by a set of commuting operators and track it with single bits.

Here is the move. Instead of describing a state $|\psi ⟩$ by its amplitudes, describe it by the operators that hold it still. We say a Pauli $P$ stabilizes $|\psi ⟩$ when

that is, when $|\psi ⟩$ is a $+1$ eigenstate of $P$. The set of all Paulis that stabilize a given state forms a group, its stabilizer $S$. A stabilizer state on $n$ qubits is one pinned down completely by $n$ independent, commuting Pauli stabilizers: their common $+1$ eigenspace is a single ray. They must commute (a state cannot be a $+1$ eigenstate of two anticommuting operators, since $PQ=-QP$ would force $|\psi ⟩=-|\psi ⟩$), and $n$ of them cut the $2^n$-dimensional space down by a factor of $2^n$ to dimension one.

The canonical example is the Bell state. Take $|{\Phi }^{+}⟩=(|00⟩+|11⟩)/\sqrt{2}$. Check directly: $X\otimes X$ swaps $|00⟩\leftrightarrow |11⟩$ and leaves the sum fixed, while $Z\otimes Z$ gives $+1$ on both $|00⟩$ and $|11⟩$. So $|{\Phi }^{+}⟩$ is stabilized by $\{XX,ZZ\}$ — two commuting Paulis on two qubits, and that pair is the state. No amplitudes appear.

The three-qubit GHZ state $(|000⟩+|111⟩)/\sqrt{2}$ works the same way. It is fixed by $X\otimes X\otimes X$ (which swaps the two terms) and by the parity checks $Z\otimes Z\otimes I$ and $Z\otimes I\otimes Z$ (which read off that all three bits agree). So $\{XXX,ZZI,ZIZ\}$ generates its stabilizer. Note the generating set is not unique — any product of generators is again a stabilizer, so $\{XXX,ZZI,IZZ\}$ names the same group. What matters is the group, not the particular handles we grab it by.

A generating set of $n$ Paulis is a wonderfully compact description. Each generator is $n$ two-bit symbols (one of $I,X,Y,Z$) plus a sign — about $2n$ bits — so $n$ generators fit in $\sim 2n^2$ bits, against $2^n$ complex amplitudes. Section 5.4 turns that observation into an algorithm; the lab pushes it to a thousand qubits.

A description is only useful if we can compute with it. We need to know which gates keep a stabilizer state a stabilizer state — that is, which unitaries $U$ send Paulis to Paulis under conjugation. If $P$ stabilizes $|\psi ⟩$, then $UP{U}^{†}$ stabilizes $U|\psi ⟩$, because

So the whole stabilizer transforms by $P\mapsto UP{U}^{†}$. If that map keeps us inside the Pauli group — if $UP{U}^{†}\in {\mathcal{P}}_n$ for every Pauli $P$ — then $U$ carries stabilizer states to stabilizer states, and we can track its effect on the $n$ generators alone. The unitaries with this property form the Clifford group ${\mathcal{C}}_n$.

Remarkably, the entire Clifford group is generated by just three gates from Chapter 2 — the Hadamard $H$, the phase gate $S$, and the two-qubit $\mathrm{CNOT}$. Their conjugation actions are exactly the Pauli-to-Pauli maps you can verify by hand:

Read (5.6) as the rulebook for updating a tableau: to apply $H$ to qubit $a$, swap the roles of $X$ and $Z$ there; to apply $S$, fold $X$ into $Y$; and $\mathrm{CNOT}$ copies $X$ from control to target and $Z$ from target to control. Each is a handful of bit operations on every generator. What (5.6) does not contain is any gate that leaves the Pauli group — the $T$ gate of Chapter 2, for instance, sends $X$ to $(X+Y)/\sqrt{2}$, which is not a Pauli at all. Hold onto that omission; §5.4 shows why it is the whole story.

Put the pieces together. A stabilizer input is $n$ generators; a Clifford gate is a fixed bit-rule on those generators; so a Clifford circuit of any length is just a sequence of cheap updates to a binary table of order $n$ rows, each $2n$ bits wide plus a sign bit — the lab uses $2n+1$ such rows, for reasons the next paragraph gives. This is the Gottesman–Knill theorem: any circuit built from $H$, $S$, $\mathrm{CNOT}$, and computational-basis measurement, run on a stabilizer input, can be simulated on a classical computer in polynomial time.

The Aaronson–Gottesman representation makes this concrete. Store $2n+1$ rows: $n$ stabilizer generators, $n$ partner destabilizer generators (which make measurement updates efficient), and one scratch row the deterministic branch of a measurement accumulates into. Each row is a bit vector of $X$-parts $x_{ij}$ and $Z$-parts $z_{ij}$ plus a sign bit $r_i$. A single-qubit Pauli on qubit $j$ is read off the pair $(x_{ij},z_{ij})$: $00=I$, $10=X$, $11=Y$, $01=Z$. Play with it — apply gates and watch the generator rows update:

Measurement is the subtle part, and it splits cleanly in two. To measure qubit $a$ in the $Z$ basis, ask whether any stabilizer generator anticommutes with $Z_a$ — equivalently, whether any stabilizer row has its $X$-bit on qubit $a$ set. If none does, the outcome is deterministic: $Z_a$ (or its negative) is already implied by the stabilizer, and we read the sign off by combining the relevant generators — no randomness, the correlation was fixed the moment the state was prepared. If some generator does anticommute, the outcome is a genuine fair coin: we record $0$ or $1$ with equal probability and update the tableau so that $\pm Z_a$ becomes a new generator. This is exactly the $P(0)\in \{0,\frac{1}{2},1\}$ structure a stabilizer state always has — never any other probability.

That moral is the sharp edge promised at the start. A circuit of Cliffords on a stabilizer input, however deep and however entangled, is something your classical laptop keeps up with stride for stride. So whatever gives a quantum computer its power, it cannot be Clifford gates alone — you need at least one non-Clifford gate, the $T$ of Chapter 2 being the usual choice, to escape the tableau and reach states no binary table can name. Where that escape buys real speed, and where it only seems to, is the question of Part II.

The formalism becomes a small, sharp Rust program: the Aaronson–Gottesman CHP simulator. A stabilizer state is a table of bools; each Clifford gate is a loop of XORs over the rows. Here is the core — the tableau and all three Clifford generators of §5.3, $H$, $S$ and $\mathrm{CNOT}$, each a direct transcription of its line in equation (5.6). The ops counter accumulates the elementary row-updates that the scaling chart below plots:

1/// A stabilizer state on `n` qubits, stored as a binary tableau over GF(2).
2///
3/// Rows 0..n are the DESTABILIZER generators, rows n..2n the STABILIZER
4/// generators, and row 2n is a scratch row used during measurement. Each row
5/// is a Pauli operator encoded by its X part `x[row][q]`, its Z part
6/// `z[row][q]`, and a phase bit `r[row]` (false = +1, true = −1).
7struct Tableau {
8    n: usize,
9    x: Vec<Vec<bool>>, // (2n+1) x n
10    z: Vec<Vec<bool>>, // (2n+1) x n
11    r: Vec<bool>,      // 2n+1
12    ops: u64,          // elementary GF(2) row-updates, a work proxy
13}
14
15// …
16
17impl Tableau {
18    // …
19
20    /// Hadamard on qubit a.
21    fn h(&mut self, a: usize) {
22        for i in 0..2 * self.n {
23            self.r[i] ^= self.x[i][a] & self.z[i][a];
24            let t = self.x[i][a];
25            self.x[i][a] = self.z[i][a];
26            self.z[i][a] = t;
27        }
28        self.ops += 2 * self.n as u64;
29    }
30
31    /// Phase gate S on qubit a.
32    fn s(&mut self, a: usize) {
33        for i in 0..2 * self.n {
34            self.r[i] ^= self.x[i][a] & self.z[i][a];
35            self.z[i][a] ^= self.x[i][a];
36        }
37        self.ops += 2 * self.n as u64;
38    }
39
40    /// CNOT with control a, target b.
41    fn cnot(&mut self, a: usize, b: usize) {
42        for i in 0..2 * self.n {
43            self.r[i] ^= self.x[i][a] & self.z[i][b] & (self.x[i][b] ^ self.z[i][a] ^ true);
44            let xb = self.x[i][b] ^ self.x[i][a];
45            let za = self.z[i][a] ^ self.z[i][b];
46            self.x[i][b] = xb;
47            self.z[i][a] = za;
48        }
49        self.ops += 2 * self.n as u64;
50    }
51
52    // …
53}

Measurement is the one place with real branching — the deterministic and random cases of §5.4, each an $O(n^2)$ tableau update rather than a walk over $2^n$ amplitudes:

1/// Measure qubit a in the Z basis, collapsing the tableau. `coin` supplies
2    /// the outcome in the random case. Returns (outcome_bit, was_random).
3    fn measure(&mut self, a: usize, coin: bool) -> (u8, bool) {
4        let n = self.n;
5        let pivot = (n..2 * n).find(|&row| self.x[row][a]);
6        match pivot {
7            Some(p) => {
8                // Random outcome: make p the only anticommuting generator.
9                for i in 0..2 * n {
10                    if i != p && self.x[i][a] {
11                        self.rowsum(i, p);
12                    }
13                }
14                // The old stabilizer p becomes a destabilizer; p becomes ±Z_a.
15                self.row_copy(p - n, p);
16                for j in 0..n {
17                    self.x[p][j] = false;
18                    self.z[p][j] = false;
19                }
20                self.r[p] = coin;
21                self.z[p][a] = true;
22                (coin as u8, true)
23            }
24            None => {
25                // Deterministic outcome: accumulate in the scratch row.
26                let scratch = 2 * n;
27                for j in 0..n {
28                    self.x[scratch][j] = false;
29                    self.z[scratch][j] = false;
30                }
31                self.r[scratch] = false;
32                for i in 0..n {
33                    if self.x[i][a] {
34                        self.rowsum(scratch, i + n);
35                    }
36                }
37                (self.r[scratch] as u8, false)
38            }
39        }
40    }

The lab does not ask you to trust the update rules; it proves them. A from-scratch state-vector simulator plays referee: on hundreds of random Clifford circuits (up to eight qubits) every measurement outcome and its deterministic/random label must match the tableau exactly, sharing the same coin flips. The Bell and GHZ generators are read back and confirmed to hold their states at $+1$ — and the residual there is not merely small but exactly zero, since a Pauli only permutes and negates amplitudes of $\pm 1/\sqrt{2}$.

At a thousand qubits there is no oracle left: the $2^{1000}$-amplitude state vector could never be written down. So the three referees that run there grade predictions against the measurement outcomes themselves, and each of them is a count of how many the tableau got wrong. In a GHZ state, once qubit 0 has been measured every remaining outcome must be flagged deterministic and repeat the first. A measurement repeated immediately must return the same bit, now with certainty — the one check that exercises the destabilizer bookkeeping at that size. And once every qubit of a random Clifford state has been measured, the surviving generators must be exactly the stabilizer group of the recorded bit string: pure $Z$-strings whose signs are its parities. Each doubtful measurement is handed a poisoned coin, the opposite of the required answer, so a branch that wrongly calls an outcome random convicts itself twice over.

What the lab pointedly does not referee is the clock. The tableau's speed is this chapter's whole point, so the times are reported — but a stopwatch measures the machine, not the physics, and a gate on wall time would fail on a busy laptop while passing a simulator that is fast and wrong. Every number below is whatever your last cargo run --release produced:

Run it yourself with cargo run --release in Rust-QML/ch05-stabilizer. The tableau is the working language of quantum error correction, which Part III builds on top of it — and, read the other way, it is a precise map of the territory where quantum computers win nothing at all.