The Gottesman–Knill Theorem
Why Clifford circuits are classically easy.
A Clifford circuit can entangle a thousand qubits into a GHZ state, a cluster state or an error-correcting code, and a laptop can still predict every measurement. The Gottesman–Knill theorem explains why, and pinpoints what a quantum computer needs beyond Cliffords: magic.
What you’ll learn
- Define the Pauli group, the Clifford group and stabilizer states, and state their sizes.
- State and prove the Gottesman–Knill theorem in the stabilizer (Heisenberg) picture, including the measurement update rules.
- Simulate small Clifford circuits by hand by tracking stabilizer generators.
- Explain why entanglement is not sufficient for quantum speedup, and how gates and magic states break efficient simulation.
Paulis, Cliffords and stabilizer states
The counting miracle: a stabilizer state, a vector with amplitudes, is pinned down by signed Pauli strings, only bits. And a Clifford gate maps stabilizers to stabilizers: if , then . You can follow the state through a whole circuit without ever writing down an amplitude.
| Object | General | ||
|---|---|---|---|
| Pauli group | 16 | 64 | |
| Cliffords, up to phase | 24 | 11,520 | |
| Stabilizer states | 6 | 60 |
Conjugation rules: the whole simulator
spreads forward from control to target; spreads backward from target to control.
Conjugation is multiplicative, so images of products are products of images, e.g. .
Under , what does become?
- (unchanged)
Show the answer
B.
, so . The part of the control's operator spreads to the target; its part stays put.
The theorem and its proof
With a bare generator list, each deterministic measurement needs Gaussian elimination, . Aaronson and Gottesman (2004) also track destabilizers (Paulis that pair with the generators the way pairs with ), which brings measurements down to while gates stay ; their CHP simulator handles thousands of qubits.
They also proved that simulating stabilizer circuits is complete for (parity logspace), a class inside that is believed to be strictly smaller.
Entangled but easy
Each stabilizes on its qubit.
and .
This is the GHZ state , maximally entangled across every cut.
The random case. and commute with and survive.
The deterministic case: the outcome is perfectly correlated with the first, all from a few bit operations.
Think first Which state did you just build?
The 3-qubit linear cluster state , the one-dimensional resource of measurement-based quantum computing. All its amplitudes have modulus , with signs . Hadamards on qubits 1 and 3 turn it into the GHZ state: graph states and GHZ states are close cousins.
Measuring a stabilizer state in the computational basis always gives the uniform distribution on an affine subspace of . Which 3-qubit distribution could therefore come from a stabilizer state?
- each on , , ,
- each on , , ,
- on , and each on and
- each on , ,
Show the answer
A. each on , , ,
is the even-parity subspace: it is the support of , stabilized by , and . The second set is not closed under addition ( is missing), the third is not uniform, and three outcomes is not a power of two.
Where the magic comes from
Gottesman–Knill dissolves a tempting story. Clifford circuits produce GHZ states, cluster states and every stabilizer code, so entanglement alone does not make quantum computation hard. What does? Add one non-Clifford gate, such as the T gate. In the Heisenberg picture,
a superposition of Paulis, so each gate can double the number of Pauli terms to track. Circuits with gates can be simulated in time : efficient for , but because Clifford+T is universal, efficient for all circuits only if BQP = BPP.
A non-stabilizer state, a magic state, prepared offline; in fault-tolerant schemes it is purified by magic-state distillation (Bravyi–Kitaev).
Expand and regroup by the value of the ancilla.
Measure the ancilla in ; on outcome apply the Clifford . Every gate used is Clifford: the non-Clifford power is carried entirely by the input state.
Key takeaways
- A stabilizer state is specified by signed Pauli generators ( bits), and Clifford gates map generators to generators.
- Gottesman–Knill: Clifford gates, Pauli measurements and classical feed-forward on basis-state inputs are efficiently simulable ( per gate and per measurement with destabilizers).
- Massive entanglement is therefore not sufficient for a quantum speedup.
- Non-Clifford resources ( gates or magic states) break efficient simulation; known simulators are exponential only in their number.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which circuit is efficiently simulable by the Gottesman–Knill theorem?
- on 50 qubits, a ladder of CNOTs, then -measurement of every qubit
- The same circuit with a gate on every qubit right after the gates
- A circuit of Toffoli and gates
- Any circuit whose output state is highly entangled
Show the answer
A. on 50 qubits, a ladder of CNOTs, then -measurement of every qubit
Only the first uses exclusively Clifford gates and Pauli measurements. Inserting gates leaves the theorem's scope (the state is no longer a stabilizer state), Toffoli is non-Clifford, and entanglement is not the criterion at all.
A stabilizer state has generators (the Bell state ). You measure . What happens?
- Outcome with certainty
- A uniformly random outcome ; afterwards the generators are
- A uniformly random outcome ; afterwards the generators are
- It cannot be simulated classically, because the state is entangled
Show the answer
B. A uniformly random outcome ; afterwards the generators are
anticommutes with (the random case): the outcome is uniform and is replaced by . commutes with and stays, so a later measurement is deterministic and equals .
What is the deepest reason stabilizer circuits are classically easy?
- They create no entanglement
- They only produce real amplitudes
- They are always shallow
- Their action on Pauli operators is linear algebra over on bits, so no state ever needs amplitudes
Show the answer
D. Their action on Pauli operators is linear algebra over on bits, so no state ever needs amplitudes
Cliffords act on the representation as symplectic matrices, and measurements are Gaussian elimination. The exponentially large state is encoded implicitly by generators.
In magic-state injection of a gate, which ingredient is non-Clifford?
- The CNOT
- The -basis measurement
- The resource state
- The correction
Show the answer
C. The resource state
All operations are Clifford (CNOT, Pauli measurement, a classically controlled ); the resource state is not a stabilizer state, and it carries the non-Clifford power.
Further reading
- D. Gottesman, Stabilizer Codes and Quantum Error Correction, PhD thesis, Caltech (1997), arXiv:quant-ph/9705052.
- D. Gottesman, "The Heisenberg representation of quantum computers" (1998), arXiv:quant-ph/9807006.
- S. Aaronson & D. Gottesman, "Improved simulation of stabilizer circuits", Phys. Rev. A 70, 052328 (2004).
- S. Bravyi & A. Kitaev, "Universal quantum computation with ideal Clifford gates and noisy ancillas", Phys. Rev. A 71, 022316 (2005).
- S. Bravyi & D. Gosset, "Improved classical simulation of quantum circuits dominated by Clifford gates", Phys. Rev. Lett. 116, 250501 (2016).