Gottesman-Knill theorem

In plain terms

Not everything a quantum computer does is hard to imitate. Gottesman and Knill drew a startling line, as a large and useful family of quantum circuits, everything built from three gates, the Hadamard gate that creates superpositions, the phase gate that twists the phase of one branch, and the controlled-NOT that flips one qubit depending on another, can be tracked perfectly by an ordinary computer, with no exponential effort.

The trick is to stop watching the quantum state. Describing the state of many qubits takes a number of amplitudes that doubles with every qubit added, which is what makes quantum computers hard to simulate in general, so instead you watch a small set of operations that fix the state completely, its stabilisers, the operations that leave the state exactly as it was. Each stabiliser is described by two strings of bits and a sign, and the remarkable property of the Clifford gates is that they shuffle these descriptions among themselves, so if you push a stabiliser through a Clifford gate out comes another stabiliser, its bit strings updated by a fixed linear rule.

So the whole circuit reduces to bookkeeping on bits, which an ordinary computer does with ease, and quantum advantage, wherever it lives, must come from gates outside this family.

In CSD

Gottesman-Knill is a library layer of the corpus, free of CSD content, in two modules. The first proves the algebra of the Pauli operators, the operations built from bit flips and phase flips on each qubit and labelled by two strings of bits, so they close under composition, with a sign fixed by a pairing of the labels, two of them commute exactly when a certain binary pairing of their labels vanishes, and every Pauli operator other than the identity has trace zero, the seed of the argument that a full set of stabilisers determines a state uniquely. The second module proves the mechanism itself, as pushing any Pauli operator through each generator gate, the controlled-NOT, the phase gate and the Hadamard gate, yields a phase times another Pauli operator, with the rule for updating the labels made explicit and linear over the bits, gate by gate.

The honest scope is that the closure in the Heisenberg picture, tracking the operators rather than the state, is proved in full, while the reading "classically simulable in polynomial time" is a claim about the cost of running the update rule, and the corpus has no model of computation, so that reading stays prose. The stabiliser-group layer built on this is proved in full in the same tree, the projector onto the stabilised states, its trace, the dimension of the code space by the rank-equals-trace argument, uniqueness of the state fixed by a full set of stabilisers, and the complete rule for updating the stabilisers under measurement, in both the deterministic and the fair-coin case, with the post-measurement stabiliser. The Steane code is the first CSS instance built on it, and the magic- state layer is the proved boundary of the mechanism. The standing disclaimer applies, as the algorithm layer consumes the programme's unitary-evolution pillar and doesn't support the foundations.

Mathematically

On the register over Fin n -> Fin 2, pauliOp a b acts by (X^a Z^b psi)(z) = (-1)^(b.(z+a)) psi(z+a). The group law X^a Z^b . X^a' Z^b' = (-1)^(b.a') X^(a+a') Z^(b+b') makes the family closed with F2-symplectic phase bookkeeping, two Paulis commuting exactly when the symplectic form of their labels vanishes, and the character sum over z of (-1)^(b.z) equals 2^n exactly when b = 0, so non-identity Paulis are traceless.

The conjugation theorems (hGate_conj_pauliOp and its CNOT and S counterparts) say CNOT_jk carries (a, b) to (a[k += a_j], b[j += b_k]) with no phase, S_j carries b to b[j += a_j] with phase i^(a_j), and H_j swaps a_j and b_j with sign (-1)^(a_j b_j). Every sign in the development is the character of an F2-valued form, so the bookkeeping reduces to finite F2 identities checked by decision procedure.

The name

Daniel Gottesman introduced the stabiliser formalism in his 1997 Caltech thesis and distilled the simulability observation in "The Heisenberg representation of quantum computers" (1998), crediting the theorem's joint form to a conversation with Emanuel Knill, hence the name. Knill, at Los Alamos, was at the same time laying the foundations of fault-tolerant quantum computation.

The theorem is the reason quantum error correction doesn't by itself grant quantum advantage, as the codes are Clifford objects. Aaronson and Gottesman's 2004 "Improved simulation of stabilizer circuits" made the bookkeeping practical, and stabiliser theory became the common language of the field, including the research programme of David Gross on Clifford orbits and designs.

Related entries

• Steane codeSeven qubits protect one, as the Steane code was the first to correct any single- qubit error by using the same classical Hamming code twice, once for bit flips and once for phase flips.
• Shor codeShor's nine-qubit code was the first proof that quantum information can be protected against any error on any single qubit without ever being read, and the corpus verifies that protection as explicit constructed operations, including the subtle case where two different errors share one repair.
• magic stateA magic state is the fuel of quantum advantage, a single special state that, consumed by otherwise classically trackable Clifford circuits, unlocks the one gate the Gottesman-Knill theorem can't simulate.
• Pauli matricesThree small matrices carry the entire two-level world, and their refusal to commute is the uncertainty principle in its smallest packaging.
• Grover's algorithmGrover's algorithm finds one marked item in an unsorted list in a number of steps proportional to the square root of the list size, and a separate theorem shows that no quantum algorithm can do better.
• stabiliser codeA stabiliser code describes a quantum code by the measurements that leave it alone, which replaces a list of encoded states by a handful of parity checks and turns error correction into linear algebra over the two-element field.
• Clifford plus TClifford plus T is the standard universal gate set, as the Clifford gates alone are classically simulable and adding the single eighth-turn phase gate makes every unitary reachable to any accuracy you ask for.