Lecture 6. Graph states and simulation of stabilizer circuits

In this Lecture we discuss how graph states can be used to simulate stabilizer circuits. Any stabilizer state is locally Clifford (LC) equivalent to a graph state. Moreover, two graph states are locally LC-equivalent if and only if their graphs are equivalent under the action of local complementation. Pure stabilizer states can be stored in memory as an adjacency table, such a table occupies $\mathcal{O}(n d)$ of memory, where $n$ is the number of qubits and $d$ is the maximum degree of the graph. The action of one-qubit Clifford gates in this case takes $\mathcal{O}(1)$ time. To update the state under the action of $CZ$, it may be necessary to act on the graph by local complementations, this takes $\mathcal{O}(d^2)$ time. Likewise, single-qubit measurements also take $\mathcal{O}(d^2)$ time. In practice, the described simulator works not much slower than stabilizer tableau method, but in some instances it is considerably faster.