Simple Algorithm
Quantum Computing · Rydberg State · 30 min

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 TT gates and magic states break efficient simulation.

Paulis, Cliffords and stabilizer states

The counting miracle: a stabilizer state, a vector with 2n2^n amplitudes, is pinned down by nn signed Pauli strings, only n(2n+1)n(2n+1) bits. And a Clifford gate maps stabilizers to stabilizers: if g∣ψ⟩=∣ψ⟩g\ket\psi=\ket\psi, then (UgU†) U∣ψ⟩=U∣ψ⟩(UgU^\dagger)\,U\ket\psi = U\ket\psi. You can follow the state through a whole circuit without ever writing down an amplitude.

Objectn=1n=1n=2n=2General nn
Pauli group ∣Pn∣\abs{\mathcal{P}_n}16644n+14^{n+1}
Cliffords, up to phase2411,5202n2+2n∏j=1n(4j−1)2^{n^2+2n}\prod_{j=1}^{n}(4^j-1)
Stabilizer states6602n∏k=1n(2k+1)2^n\prod_{k=1}^{n}(2^k+1)
Modulo Paulis and phases, the Clifford group is the symplectic group Sp(2n,F2)Sp(2n,\mathbb{F}_2), of order 2n2∏j(4j−1)2^{n^2}\prod_j(4^j-1).

Conjugation rules: the whole simulator

DerivationHow the generators of the Clifford group move Paulis
  1. H:X↦Z,Z↦X,Y↦−YH:\quad X\mapsto Z,\qquad Z\mapsto X,\qquad Y\mapsto -Y
  2. S:X↦Y,Y↦−X,Z↦ZS:\quad X\mapsto Y,\qquad Y\mapsto -X,\qquad Z\mapsto Z
  3. CNOTc→t:Xc↦XcXt,Xt↦Xt,Zc↦Zc,Zt↦ZcZt\mathrm{CNOT}_{c\to t}:\quad X_c\mapsto X_cX_t,\quad X_t\mapsto X_t,\quad Z_c\mapsto Z_c,\quad Z_t\mapsto Z_cZ_t

    XX spreads forward from control to target; ZZ spreads backward from target to control.

  4. CZab:Xa↦XaZb,Xb↦ZaXb,Za↦Za,Zb↦Zb\mathrm{CZ}_{ab}:\quad X_a\mapsto X_aZ_b,\quad X_b\mapsto Z_aX_b,\quad Z_a\mapsto Z_a,\quad Z_b\mapsto Z_b

    Conjugation is multiplicative, so images of products are products of images, e.g. CNOT (X⊗Z) CNOT=(X⊗X)(Z⊗Z)=− Y⊗Y\mathrm{CNOT}\,(X\otimes Z)\,\mathrm{CNOT} = (X\otimes X)(Z\otimes Z) = -\,Y\otimes Y.

Check your understanding

Under CNOT1→2\mathrm{CNOT}_{1\to2}, what does Y⊗IY\otimes I become?

  1. Y⊗IY\otimes I (unchanged)
  2. Y⊗XY\otimes X
  3. Y⊗ZY\otimes Z
  4. − Y⊗X-\,Y\otimes X
Show the answer

B. Y⊗XY\otimes X

Y=iXZY = iXZ, so Y1↦i (X1X2)(Z1)=(iX1Z1) X2=Y1X2Y_1\mapsto i\,(X_1X_2)(Z_1) = (iX_1Z_1)\,X_2 = Y_1X_2. The XX part of the control's operator spreads to the target; its ZZ part stays put.

The theorem and its proof

With a bare generator list, each deterministic measurement needs Gaussian elimination, O(n3)\order{n^3}. Aaronson and Gottesman (2004) also track nn destabilizers (Paulis that pair with the generators the way XjX_j pairs with ZjZ_j), which brings measurements down to O(n2)\order{n^2} while gates stay O(n)\order{n}; their CHP simulator handles thousands of qubits.

They also proved that simulating stabilizer circuits is complete for ⊕L\oplus\mathsf{L} (parity logspace), a class inside P\mathsf{P} that is believed to be strictly smaller.

Entangled but easy

DerivationTracking a GHZ state, measurements included
  1. ∣000⟩:⟨Z1, Z2, Z3⟩\ket{000}:\qquad\langle Z_1,\ Z_2,\ Z_3\rangle

    Each ZjZ_j stabilizes ∣0⟩\ket0 on its qubit.

  2. H1:⟨X1, Z2, Z3⟩H_1:\qquad\langle X_1,\ Z_2,\ Z_3\rangle
  3. CNOT1→2:⟨X1X2, Z1Z2, Z3⟩\mathrm{CNOT}_{1\to2}:\qquad\langle X_1X_2,\ Z_1Z_2,\ Z_3\rangle

    X1↦X1X2X_1\mapsto X_1X_2 and Z2↦Z1Z2Z_2\mapsto Z_1Z_2.

  4. CNOT2→3:⟨X1X2X3, Z1Z2, Z2Z3⟩\mathrm{CNOT}_{2\to3}:\qquad\langle X_1X_2X_3,\ Z_1Z_2,\ Z_2Z_3\rangle

    This is the GHZ state 12(∣000⟩+∣111⟩)\tfrac{1}{\sqrt2}(\ket{000}+\ket{111}), maximally entangled across every cut.

  5. measure Z1:anticommutes with X1X2X3 ⇒ m1=±1 at random;⟨m1Z1, Z1Z2, Z2Z3⟩\text{measure } Z_1:\quad\text{anticommutes with } X_1X_2X_3\ \Rightarrow\ m_1=\pm1\text{ at random};\qquad\langle m_1Z_1,\ Z_1Z_2,\ Z_2Z_3\rangle

    The random case. Z1Z2Z_1Z_2 and Z2Z3Z_2Z_3 commute with Z1Z_1 and survive.

  6. measure Z3:m1Z3=(m1Z1)(Z1Z2)(Z2Z3)∈S ⇒ outcome m1 with certainty\text{measure } Z_3:\quad m_1Z_3 = (m_1Z_1)(Z_1Z_2)(Z_2Z_3)\in\mathcal{S}\ \Rightarrow\ \text{outcome } m_1\text{ with certainty}

    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 CZ12CZ23∣+⟩⊗3\mathrm{CZ}_{12}\mathrm{CZ}_{23}\ket{+}^{\otimes3}, the one-dimensional resource of measurement-based quantum computing. All its amplitudes have modulus 122\tfrac{1}{2\sqrt2}, with signs (−1)x1x2+x2x3(-1)^{x_1x_2+x_2x_3}. Hadamards on qubits 1 and 3 turn it into the GHZ state: graph states and GHZ states are close cousins.

Check your understanding

Measuring a stabilizer state in the computational basis always gives the uniform distribution on an affine subspace of F2n\mathbb{F}_2^n. Which 3-qubit distribution could therefore come from a stabilizer state?

  1. 14\tfrac14 each on 000000, 011011, 101101, 110110
  2. 14\tfrac14 each on 000000, 001001, 010010, 100100
  3. 12\tfrac12 on 000000, and 14\tfrac14 each on 011011 and 101101
  4. 13\tfrac13 each on 000000, 011011, 101101
Show the answer

A. 14\tfrac14 each on 000000, 011011, 101101, 110110

{000,011,101,110}\{000,011,101,110\} is the even-parity subspace: it is the support of 12∑x even∣x⟩\tfrac12\sum_{x\ \mathrm{even}}\ket{x}, stabilized by Z1Z2Z3Z_1Z_2Z_3, X1X2X_1X_2 and X2X3X_2X_3. The second set is not closed under addition (001⊕010=011001\oplus010=011 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,

TXT†=12(X+Y),TXT^\dagger = \tfrac{1}{\sqrt2}(X+Y),

a superposition of Paulis, so each TT gate can double the number of Pauli terms to track. Circuits with tt TT gates can be simulated in time poly⁡(n) 2O(t)\poly(n)\,2^{\order{t}}: efficient for t=O(log⁡n)t = \order{\log n}, but because Clifford+T is universal, efficient for all circuits only if BQP = BPP.

DerivationMagic-state injection: a T gate from Cliffords and a resource state
  1. ∣A⟩=T∣+⟩=12(∣0⟩+eiπ/4∣1⟩)\ket{A} = T\ket{+} = \tfrac{1}{\sqrt2}\big(\ket0+e^{i\pi/4}\ket1\big)

    A non-stabilizer state, a magic state, prepared offline; in fault-tolerant schemes it is purified by magic-state distillation (Bravyi–Kitaev).

  2. ∣ψ⟩∣A⟩ → CNOTψ→A  12[ T∣ψ⟩⊗∣0⟩+eiπ/4 T†∣ψ⟩⊗∣1⟩ ]\ket\psi\ket{A}\ \xrightarrow{\ \mathrm{CNOT}_{\psi\to A}\ }\ \tfrac{1}{\sqrt2}\Big[\,T\ket\psi\otimes\ket0 + e^{i\pi/4}\,T^\dagger\ket\psi\otimes\ket1\,\Big]

    Expand ∣ψ⟩=a∣0⟩+b∣1⟩\ket\psi = a\ket0+b\ket1 and regroup by the value of the ancilla.

  3. m=1:S T†=T⇒apply Sm=1:\quad S\,T^\dagger = T\quad\Rightarrow\quad\text{apply } S

    Measure the ancilla in ZZ; on outcome 11 apply the Clifford SS. Every gate used is Clifford: the non-Clifford power is carried entirely by the input state.

Key takeaways

  • A stabilizer state is specified by nn signed Pauli generators (O(n2)\order{n^2} 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 (O(n)\order{n} per gate and O(n2)\order{n^2} per measurement with destabilizers).
  • Massive entanglement is therefore not sufficient for a quantum speedup.
  • Non-Clifford resources (TT 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.

Question 1

Which circuit is efficiently simulable by the Gottesman–Knill theorem?

  1. HH on 50 qubits, a ladder of CNOTs, then ZZ-measurement of every qubit
  2. The same circuit with a TT gate on every qubit right after the HH gates
  3. A circuit of Toffoli and HH gates
  4. Any circuit whose output state is highly entangled
Show the answer

A. HH on 50 qubits, a ladder of CNOTs, then ZZ-measurement of every qubit

Only the first uses exclusively Clifford gates and Pauli measurements. Inserting TT 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.

Question 2

A stabilizer state has generators ⟨X1X2, Z1Z2⟩\langle X_1X_2,\ Z_1Z_2\rangle (the Bell state ∣Φ+⟩\ket{\Phi^+}). You measure Z1Z_1. What happens?

  1. Outcome +1+1 with certainty
  2. A uniformly random outcome mm; afterwards the generators are ⟨mZ1, Z1Z2⟩\langle mZ_1,\ Z_1Z_2\rangle
  3. A uniformly random outcome mm; afterwards the generators are ⟨X1X2, mZ1⟩\langle X_1X_2,\ mZ_1\rangle
  4. It cannot be simulated classically, because the state is entangled
Show the answer

B. A uniformly random outcome mm; afterwards the generators are ⟨mZ1, Z1Z2⟩\langle mZ_1,\ Z_1Z_2\rangle

Z1Z_1 anticommutes with X1X2X_1X_2 (the random case): the outcome mm is uniform and X1X2X_1X_2 is replaced by mZ1mZ_1. Z1Z2Z_1Z_2 commutes with Z1Z_1 and stays, so a later Z2Z_2 measurement is deterministic and equals mm.

Question 3

What is the deepest reason stabilizer circuits are classically easy?

  1. They create no entanglement
  2. They only produce real amplitudes
  3. They are always shallow
  4. Their action on Pauli operators is linear algebra over F2\mathbb{F}_2 on O(n2)\order{n^2} bits, so no state ever needs 2n2^n amplitudes
Show the answer

D. Their action on Pauli operators is linear algebra over F2\mathbb{F}_2 on O(n2)\order{n^2} bits, so no state ever needs 2n2^n amplitudes

Cliffords act on the (x∣z)(x|z) representation as symplectic matrices, and measurements are Gaussian elimination. The exponentially large state is encoded implicitly by nn generators.

Question 4

In magic-state injection of a TT gate, which ingredient is non-Clifford?

  1. The CNOT
  2. The ZZ-basis measurement
  3. The resource state T∣+⟩T\ket{+}
  4. The correction SS
Show the answer

C. The resource state T∣+⟩T\ket{+}

All operations are Clifford (CNOT, Pauli measurement, a classically controlled SS); the resource state T∣+⟩T\ket{+} 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).