The Theorem

A quantum computation on a register of $n$ qubits is restricted to four kinds of step: it prepares the register in a computational basis state, applies Hadamard, phase and controlled NOT gates, applies Pauli gates, and measures observables that are tensor products of Pauli matrices. The theorem of Gottesman and Knill says that such a computation can be simulated efficiently on a classical computer. The simulation never writes down the $2^n$ amplitudes of the state. It keeps $n$ Pauli operators with signs that each leave the state unchanged, generators of its stabilizer, and after every step it rewrites them so that they leave the new state unchanged. They take $n(n+1)$ numbers to store, and each step costs work of the same order.

The library states the theorem in two parts: the first is the correctness of this bookkeeping through computations without measurements, the second a bound on its cost.

Stabilizer Computations

The Pauli matrices are $\sigma_0 = I$, the identity, and $$\sigma_1 = X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad \sigma_2 = Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \qquad \sigma_3 = Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}.$$(1)^✦

For a string $p = p_1 \cdots p_n$ of labels in $\{0,1,2,3\}$, the Pauli string $\sigma_p$ on the register is the operator $\sigma_{p_1} \otimes \cdots \otimes \sigma_{p_n}$.^✦ In the computational basis $|x\rangle$, labelled by strings of bits $x = x_1 \cdots x_n$, its matrix entries are $$\langle x | \sigma_p | y \rangle = \prod_{k=1}^{n} (\sigma_{p_k})_{x_k y_k}.$$(2)^✦

An elementary Clifford gate on the register is a Hadamard gate $H_j$ on a qubit $j$, a phase gate $S_j$ on a qubit $j$, or a controlled NOT gate $\mathrm{CNOT}_{ct}$ with control qubit $c$ and target qubit $t \neq c$.^✦

A stabilizer operation $o$ on the register is one of four kinds: the preparation of the register in the computational basis state $|0 \cdots 0\rangle$, an elementary Clifford gate, the Pauli gate $\sigma_p$ for a string $p$ of labels, or the measurement $M_p$ of the observable $\sigma_p$.^✦ Only the last kind counts as a measurement: $$o \text{ is a measurement} \iff o = M_p \text{ for some } p \in \{0,1,2,3\}^n.$$(3)^✦

A stabilizer computation $P$ on $n$ qubits is a finite sequence $(o_1, \dots, o_m)$ of stabilizer operations on the register; its length is the number $m$ of its operations.^✦ Each operation acts on the vectors of the register, sending $|\psi\rangle$ to $o|\psi\rangle$. The state $P|\psi\rangle$ after the computation, from a vector $|\psi\rangle$ of the register, is the vector reached by letting the operations act in turn, first to last: $$P|\psi\rangle = o_m \cdots o_2\, o_1 |\psi\rangle.$$(4)^✦

The Tableau

A stabilizer tableau $T$ on $n$ qubits is an $n \times n$ array of labels $g_{ij} \in \{0,1,2,3\}$ together with a column of $n$ complex numbers $s_i$, the signs: $$T = \begin{pmatrix} g_{11} & \cdots & g_{1n} & s_1 \\ \vdots & & \vdots & \vdots \\ g_{n1} & \cdots & g_{nn} & s_n \end{pmatrix}.$$(5)^✦ Row $i$ is the generator $s_i \sigma_{g_i}$, the Pauli string of the labels $g_i = g_{i1} \cdots g_{in}$ with its sign.

The tableau $T$ stabilizes a vector $|\psi\rangle$ of the register when each of its generators leaves the vector unchanged: $$s_i\, \sigma_{g_i} |\psi\rangle = |\psi\rangle, \qquad i = 1, \dots, n.$$(6)^✦

Every operation $o$ also updates a tableau, $T \mapsto o[T]$. The run of a computation $P$ on a tableau $T$ is the tableau $P[T]$ reached by applying the updates of its operations in turn: $$P[T] = o_m\big[ \cdots o_2\big[ o_1[T] \big] \cdots \big].$$(7)^✦

The cost $c(o)$ of an operation $o$ is $n(n+1)$, the number of entries of a tableau, unless $o$ is a measurement, which costs twice as much.^✦ The simulation cost $C(P)$ of a computation is the sum of the costs of its operations: $$c(o) = \begin{cases} 2n(n+1) & \text{if $o$ is a measurement,} \\ n(n+1) & \text{otherwise,} \end{cases} \qquad C(P) = \sum_{k=1}^{m} c(o_k).$$(8)^✦

The Claim

What Is Checked

The first part is stated over a tableau (5) stabilizing a vector (6), its run under a computation (7), the state after the computation (4) and the test for a measurement (3); the second is stated over the simulation cost (8) and the length of the computation.

Both parts are stated for these constructions, (9) and (10).