Weak simulation of Clifford circuits

Question

Quantum circuits composed by Clifford gates can be simulated by classical computation in polynomial time. More precisely, this simulation should be a weak simulation, i.e. it is possible to sample the outcome of measurements of the output state of the circuit. This is stated, e.g., here

An explicit method for sampling the outcome of the measurement is given in the above mentioned paper and here. In both cases, the used formalism is different from the most traditional one, based on normalizer groups and stabilizers.

This latter formalism was used in the seminal paper of Gottesman (with Knill in references.). Very roughly, the original idea was to use the Heisenberg representation. Instead of having a vector $\left|\Psi\right>$ that evolves like $O\left|\Psi\right>$, there is an operator $N$ evolving as $O^{\dagger}NO$. When $N$ is chosen in the Pauli group, and $O$ is the evolution generated by a quantum circuit made of Clifford gates, then $O^{\dagger}NO$ remains in the Pauli group. The representation of $N$ and its evolution under the Clifford gates can be done quickly by classical calculation.

It is thus possible to efficiently compute the expectation values $\left<\Psi\right|O^{\dagger}NO\left|\Psi\right>$, but this should be a task for strong simulation.

To deal with states, it is noticed that a state $\left|\Psi\right>$ is uniquely defined by giving $n$ operators $N_n$ (belonging to the Pauli group), such that $N_n\left|\Psi\right>=\left|\Psi\right>$. If we want to use the Gottesman formalism for weak simulation, it should be possible to classically sample the outcome of the measurements of single qubits of the state $\left|\Psi\right>$, given the operators $N_n$. However, I do not see a proof of this. Is this true? If so, do you have references?

Answer 1

Short story: You can do both strong and weak simulation.

There are several ways of doing the simulation, let's just illustrate one method.

Given a Clifford unitary $U$ (or circuit, doesn't matter), we can efficiently evaluate $U|0\rangle$ by computing $UZ_1U^\dagger,\dots, UZ_nU^\dagger$ in time $O(n^3)$. Of course, this also works if we replace $|0\rangle$ by an arbitrary stabilizer state and the $Z_i$'s by some generators of its stabilizer group.

To compute expectation values, the representation by the stabilizer group can be directly used. However, we can also efficiently compute an actual representation of $U|0\rangle$ in the computational basis, which is of the form $$ U|0\rangle \simeq \frac{1}{\sqrt{|K|}} \sum_{x\in K} i^{b^\top x} (-1)^{q(x)} |x\rangle, $$ where $K\subset \mathbb F_2^n$ is an affine subspace, $b\in\mathbb F_2^n$ is a vector, and $q$ is a quadratic form on $\mathbb F_2^n$. Here "$\simeq$" means up to a global phase (which we could in principle determine).

Hence, we can also efficiently compute the amplitude $\langle x |U| 0\rangle$.

Given such a representation of the final state, it is now trivial to sample from it: The outcome distribution is simply the uniform distribution on $K$. In practice, you will have anyway chosen a basis for $K$ to compute the above representation, so you simple have to pick random binary numbers $y_1,\dots,y_{\dim K}\in\mathbb F_2$ and write them in front of your basis.

There are also slightly different ways to do weak simulation which, however, often boil down to the same thing.

Note that I assumed that you're given a $n$-qubit Clifford unitary. Clearly, every poly-sized Clifford circuit can be efficiently brought into that form. But let's assume that, for some reason, you want to work with the circuit itself. Then, you can do a Markov-like propagation of samples, assuming that you have brought the circuit into a standard form. This is what is described in van den Nest's paper ("HT form"). In terms of efficiency of the algorithm, this is equivalent to computing the output state $U|0\rangle$ and perform the above procedure.

References:

1. The form of stabilizer states in the computational basis, and how it can be derived from its stabilizer group, was first described in Dehaene, De Moor: "The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)". Unfortunately, that paper has a horrible notation. It's basically a projection of the generator matrix. I've also described it in my thesis, but its style is quite technical. I'm not aware of a "simple" paper out there.