Are almost-Clifford circuits almost easy to simulate?

Question

Circuits consisting entirely of Clifford operations in ${X, Y, Z, H, S, text{CNOT} }$ are "easy" to simulate classically since there is a method that can fully compute such circuits over $n$ qubits with $O(n^2)$ complexity.
I'm curious if circuits that are almost entirely Clifford operations can be shown to approach some lower complexity$^dagger$ with respect to some continuous parameter that dictates how non-Clifford that circuit is. This is different than some work (e.g. Bravyi and Gosset) that has shown efficient simulation methods when a small number of $T$ gates are inserted into an otherwise Clifford circuit.
For example, suppose I have a circuit consisting entirely of Clifford operations but has a set of $text{CNOT}^x$ gates. Can I show either of the following?

The complexity of simulating this circuit continuously approaches some asymptotically lower function in the limit that $xrightarrow 0$?

If $p$ is the distribution over results from my almost-Clifford circuit and $q$ is the distribution over results from the corresponding Clifford circuit taking $x=0$, then $d(p, q) leq epsilon$ for some small $epsilon$ and some choice of statistical distance $d$. Of course this would also depend on the number of parameterized $text{CNOT}$'s occurring in the circuit.

If no such behavior exists - i.e. my circuit is generally $O(2^n)$ complexity even for infinitesmal $x$ - why not?

$^dagger$ This lower limit doesn't need to be $O(n^2)$. Instead of a stabilizer based simulation I could instead use tensor-based simulation for which there is still a large speedup for computing $text{CNOT}$ compared to $text{CNOT}^x$. It seems like this might be more approachable to show something like (1) since the Clifford simulation techniques I'm aware of simply don't generalize to the non-integer $x$ case.

Markus Heinrich · Accepted Answer

Short answer: Yes, this should be possible. However, the details have to be filled out. The key is to relate this to magic monotones.
There has been some development since the 2016 Bravyi-Gosset paper. I think one can use an argumentation based on stabiliser / Clifford extent and the results in the  BBCCGH paper from 2019. Similarly, one can also argue for noisy quantum circuits / arbitrary quantum channels using mixed state versions like Howard-Campbell, Seddon-Campbell, Seddon et al.
Let us focus on a single non-Clifford gate, given by a continuous family $G(t)$ such that (wlog)  $G(t)rightarrow mathbb{I}$ for $trightarrow 0$ . Then, expand it as a linear combination of Clifford unitaries:
$$
G(t) = sum_i a_i(t) C_i,
$$
with coefficients $a_i(t)inmathbb{C}$. Now, the minimal value of $|a(t)|_1^2$ over all possible decompositions of $G(t)$ is called the Clifford extent $xi(G(t))$.
Suppose the input to the whole circuit is, say $|0rangle$, and we measure in the computational basis in the end. Using the stabiliser extent method descriped in the mentioned paper (Sec. 2.3.2), it is possible to sample bitstrings $x$ which approximate the exact outcome distribution.
More precisely, for any $delta > 0$ there is an algorithm with runtime $tilde O(delta^{-2}xi(G(t)))$ which samples bitstrings according to a probability distribution $q$ which is $delta$-close to the exact distribution $p$ in total variation distance:
$$
| p -q |_1 leq delta.
$$
If we have multiple $G(t)$, then the number of those enters as an exponent of $xi(G(t))$.
Finally, it should not be hard to show that $xi(G(t))$ depends continously on $t$, in particular $xi(G(t))rightarrow 1$ for $trightarrow 0$. This reduces the complexity to the Clifford case (EDIT: well, almost. As I said, the details have to be filled out.).

Are almost-Clifford circuits almost easy to simulate?

One Answer

Add your own answers!

Ask a Question