108
Part Three · A · Foundations of quantum information

Stabilizer formalism, Clifford group, Gottesman–Knill theorem

A circuit of a million gates on a thousand qubits ought to be impossible to simulate: 210002^{1000} amplitudes. Yet if the gates are only Hadamards, phase gates and CNOTs, a laptop does it in seconds, and Craig Gidney’s Stim simulator does billions of such gates per second. The trick is to stop tracking amplitudes and instead track which Pauli operators leave the state unchanged. Recognizing these easy circuits tells you exactly where quantum hardness has to come from.

On the plate: three qubits, tracked two ways at once: by amplitudes, and by stabilizers.

Stabilizers

The Pauli group on nn qubits is all products of I, X, Y, Z on each qubit, times ±1 or ±i. A state is a stabilizer state if it is the unique +1 eigenstate of nn commuting, independent Pauli operators, its stabilizer generators. ∣0⟩|0\rangle is stabilized by Z; ∣+⟩|+\rangle by X; the Bell state ∣Φ+⟩|\Phi^+\rangle by XX and ZZ; the three-qubit GHZ state by XXX, ZZI, IZZ. Instead of 2n2^n amplitudes, you store nn Pauli strings: about 2n22n^2 bits. Established

Clifford gates update stabilizers

The Clifford group is the set of gates that map Pauli operators to Pauli operators under conjugation, P→UPU†P\to UPU^\dagger. It is generated by H, S and CNOT. If gg stabilizes ∣ψ⟩|\psi\rangle, then UgU†UgU^\dagger stabilizes U∣ψ⟩U|\psi\rangle, so each gate just rewrites the generators: H swaps X and Z on its qubit; S turns X into Y; CNOT spreads X from control to target and Z from target to control. Apply gates: . The tableau and the state vector stay in agreement.

The Gottesman–Knill theorem

Daniel Gottesman showed in 1997 (with credit to Emanuel Knill) that any circuit of Clifford gates, starting from computational basis states and ending in Pauli measurements, can be simulated efficiently classically. Scott Aaronson and Gottesman made it fast in 2004 with the CHP tableau algorithm. Clifford circuits can create highly entangled states, like large GHZ states, so entanglement alone does not make a quantum computer hard to simulate. One qubit has 24 Clifford gates up to phase; two qubits have 11,520. Established

Where hardness lives

Add one non-Clifford gate, such as T, and stabilizer tracking breaks: TXT†TXT^\dagger is not a Pauli operator. Simulations that handle a few T gates exist, with cost growing exponentially in their number. So T gates, or the magic states that supply them (Chapter 140), are the costly resource; contextuality (Chapter 107) is what they supply. Error correction, conversely, runs almost entirely on Clifford operations, which is why decoders and code simulators like Stim are fast.

What you now have

The Pauli group, stabilizer states and generators, Clifford gates as stabilizer updates, the tableau simulator, the Gottesman–Knill theorem, the sizes of the Clifford groups, and why T gates carry the cost.

· · ·

Three questions to carry with you.

What are the stabilizers of |Φ⁺⟩?tap
XX and ZZ.
Does entanglement make a circuit hard to simulate?tap
Not by itself: Clifford circuits make highly entangled states yet are classically easy.
Why is T not a Clifford gate?tap
It maps X to (X + Y)/√2, which is not a Pauli operator.

And one to work out. How many single-qubit Clifford gates are there, up to global phase?

|C₁| =

Sources: D. Gottesman, PhD thesis, Caltech (1997), arXiv:quant-ph/9705052; arXiv:quant-ph/9807006 (1998). S. Aaronson and D. Gottesman, Phys. Rev. A 70, 052328 (2004). C. Gidney, Quantum 5, 497 (2021) (Stim). M. A. Nielsen and I. L. Chuang, §10.5. Checked by code: breadth-first search over H and S finds 24 single-qubit Cliffords mod phase; the tableau updates agree with Book.QSim on every gate in the plate.

Next · Chapter 109
ZX-calculus and graphical reasoning

Draw a circuit, wiggle the wires, and the diagram does the proof.

Turn the page