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?

1. The complexity of simulating this circuit continuously approaches some asymptotically lower function in the limit that $x\rightarrow 0$?

2. 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.

Answer 1

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 $t\rightarrow 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)\in\mathbb{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 $|0\rangle$, 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 $t\rightarrow 0$. This reduces the complexity to the Clifford case (EDIT: well, almost. As I said, the details have to be filled out.).