Gottesman–Knill theorem

Remarks

Proof idea: the gates $H$, $S$ and CNOT generate the Clifford group, which maps the Pauli group to itself under conjugation. The state at each time is the common $+1$ eigenvector of an abelian group of $n$ independent Pauli operators, its stabilizer. The algorithm stores $n$ generators as an $n \times 2n$ binary matrix with signs, and updates them under each gate in $O(n)$ steps. A measurement outcome is either determined, or uniformly random, and both cases are read off from the generators with polynomial work.

Example: $H$ on qubit $1$ and then CNOT from qubit $1$ to each of qubits $2, \dots, n$ gives the GHZ state $(\lvert 0 \cdots 0 \rangle + \lvert 1 \cdots 1 \rangle)/\sqrt2$, which is highly entangled. Its stabilizer is generated by $X_1 X_2 \cdots X_n$ and $Z_i Z_{i+1}$ for $1 \le i < n$, and the simulation predicts that measuring all qubits gives all $0$s or all $1$s with probability $1/2$ each.

Hypothesis 2 is essential. Adding the gate $T = \operatorname{diag}(1, e^{i\pi/4})$ gives a universal gate set, and no efficient classical simulation of such circuits is known.

Going deeper

For a student

The theorem rests on the stabilizer formalism that also underlies stabilizer codes. Encoding, decoding and syndrome measurement for these codes use only Clifford operations, so they are classically simulable. To reach universality, fault-tolerant schemes add a non-Clifford gate such as $T$, often through magic state injection. The simulation cost grows with the number of non-Clifford gates, a measure used in resource theories of magic.