Lecture 7. Phase-sensitive stabilizer circuits simulators

In this Lecture we discussed two ways of simulating stabilizer circuits using which we can track the phases of stabilizer states. The first method relies on the fact that in the coordinate representation a stabiliser state is a quadratic form over an affine subspace of dimension $r$ inside $\mathbb{Z}_2^n$. The matrix and shift describing the affine subspace and the quadratic form can be stored in computer memory. The action of unitary gates is described by updating these matrices and in the worst case takes $\mathcal{O}(n r)$ time per operation. Bit measurements also take $\mathcal{O}(n r)$ time. The second simulator represents the state in the $CH$-form $\alpha U_C U_H |s\rangle$, where the operation $U_C$ consists of $\langle S,CZ,CX\rangle$, the operation $U_H$ is a product of Hadamard gates, $|s\rangle$ the state of the computational basis, and $\alpha$ some complex number. The operation $U_C$ can be stored in memory using a stabilizer tableau. The action of unitary gates on the state is described by updating the $CH$-form, with the update for the action $\langle Z,X, S, CZ, CX \rangle$ taking $\mathcal{O}(n)$ time, and the action of Hadamard $H$ and measurements taking $\mathcal{O}(n^2)$ time.