# Weak simulation of Clifford circuits

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?

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.
• 1) You wrote the "representation of U|0⟩ in the computational basis". Is it possible to calculate the state, in this representation, from the "tableau" (the representation of the $n$ Pauli operators $N_j$)? 2) Could you please expand a bit the sentence with "you could simply propagate your samples"? There is something similar in arxiv 0811.0898, but it does not directly refer to generic circuits made of Clifford gates, but rather to a particular form they can be rewritten, called HT. Jan 24 at 21:53
• @DorianoBrogioli 1) Yes, you can compute this representation from the stabilizer "tableau". Having brought this into a standard form, you can read of a basis for the linear part of $K = V + u$. An affine shift $u$ can be constructed from the character/phases of the stabilizer group. Getting the amplitudes is a bit more complicated, see the above paper or Eq. (4.47) ff in my thesis (warning: technical!). Jan 25 at 11:21
• @DorianoBrogioli 2) if you have elementary Clifford gates, i.e. H, S, CNOT, then you can see their action as changing extending the support of the $|0\rangle$ state. Of course, they also change the amplitudes, but for sampling that's irrelevant. While $S$ and other diagonal gates simply add phases, $CNOT$, $X$ (and more) do not extend the support, but merely do a deterministic mapping on the bitstrings $x$ in the support (a linear reversible transformation). $H$ does "branchings": with probability 1/2 you flip the bit, with 1/2 you don't. Jan 25 at 11:25
• I'm not convinced of 2), maybe I did not understand. For what you say, I start from a classical bit 0 and I apply H, I get 0 or 1 with equal probability. Then if I apply H again, I get again 0 or 1 with same probability (two consecutive branchings). But if I apply H twice to |0>, I get |0>, not a superposition of |0> and |1>. But probably I misunderstood your proposed method. Jan 25 at 12:59
• @DorianoBrogioli mmh you're right. I'll think about the proper formulation and update my answer soon. Jan 25 at 15:42