Gottesman Knill theorem: why $O(n^2)$ classical operation to keep track of a Clifford gate

Question

Starting from a state stabilized by Pauli matrices, and using only Clifford operations Gottesman Knill theorem ensures us that such algorithm can be classically simulated.

Indeed, if I call my initial state $|\psi \rangle$, I can define a Stabilizer group $S$ having for generators elements of the n-Pauli matrix group. I have $S=\langle g_1,...,g_n \rangle$

I consider $U$ a clifford gate. Then $U |\psi \rangle$ is stabilized by the stabilizer group $U S U^{\dagger}$.

Then $U |\psi \rangle$ is stabilized by $USU^{\dagger} = \langle U g_1 U^{\dagger},...,U g_n U^{\dagger}\rangle$

I simply have to compute $\{U g_i U^{\dagger}\}_{i=1..n}$ to keep track of my state.

My question:

It is said that such operation requires $O(n^2)$ classical operations (for instance in Nielsen & Chuang). Where does this $n^2$ comes from ? I can understand that I have $n$ calculations to compute each $U g_i U^{\dagger}$ for $1 \leq i \leq n$, but why exactly computing each of those would require additional $n$ calculations giving rise to the $O(n^2)$ ? I guess it depends on what we call an elementary operation.

Answer 1

You can pretty easily prove by counting that specifying a stabilizer operation or a stabilizer state requires $\Omega(n^2)$ bits. If you're not tracking some of those bits, your simulator is definitely wrong. So clearly tracking one generator or ten generators ($\Theta(n)$ bits) is not enough. The tricky trouble then is that for certain gates we don't know how to avoid looking at the majority of the bits to simulate that gate.

In "Improved Simulation of Stabilizer Circuits" by Aaronson and Gottesman, only measurements require $\Theta(n^2)$ operations. CNOT, H, and S use $\Theta(n)$ operations. In fact, although they don't do it in that paper, I'm pretty sure only the measurements with random results truly require $\Theta(n^2)$ operations. I believe measurement being expensive is also the case in more recent papers. For example, in "Simulation of quantum circuits by low-rank stabilizer decompositions" by Bravyi and others, everything is linear cost except measurement and Hadamards being quadratic.

I don't know of a proof that $\Omega(n^2)$ operations are required to simulate at least one of the stabilizer gates. But to me it appears that the basic obstacle is that measurements that are individually random can form groups with deterministic parity. The problem of finding these parity groups looks extremely similar to the problem of doing a partial Gaussian elimination of a boolean matrix (with measuring all $n$ qubits corresponding to a full elimination). Gaussian elimination of an $n \times n$ matrix apparently requires $\tilde{\Omega}(n^3)$ operations, which suggests some of the $n$ measurements have to cost $\Omega(n^2)$. That being said, I don't know how to turn this intuition into a proper reduction proof that reduces a Gaussian elimination problem into a stabilizer circuit simulation problem in a way that makes the Gaussian elimination run faster than $\tilde{\Omega}(n^3)$ if the stabilizer simulation outperforms $\tilde{\Omega}(n^2)$ per measurement.

It's also conceivable that there may be a distinction between online simulations (which must provide measurement results as they are requested) and offline simulations (which can delay returning results, allowing them to e.g. combine measurements into groups in some hypothetical beneficial fashion). Also, when you want multiple samples from a circuit, you may be able to deal with the core quadratic difficulty once overall instead of once per sample. Oh, and there are contexts in error correction where you can simulate a noisy circuit while only tracking whether or not measurements are flipped relative to their (unknown) true value, and these simulations are constant time per operation instead of linear or quadratic.