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.


1 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.).

  • $\begingroup$ Great answer, and thanks for the BBCCGH reference. The section you mentioned says the decomposition into Clifford gates can be found in constant time but this is not so obvious to me - is there an easy explanation for decomposing a unitary into Cliffords? $\endgroup$
    – forky40
    Jan 6, 2021 at 19:54
  • $\begingroup$ should the $||a(t)||_1$ be $||a(t)||_1^2$? $\endgroup$
    – forky40
    Jan 6, 2021 at 19:55
  • 1
    $\begingroup$ Yes, they defined the extent with a square because the 1-norm enters as such in the runtime (doesn't really matter, though). Finding the decomposition is generally a very hard problem which scales super-exponentially in the number of qubits. Above, I simply used it as a tool in the argumentation, not worrying about complexity of finding it. However, for single-qubit gates, it just a constant-sized optimisation problem. Could you elaborate what kind of explanation you're looking for? It is possible, since Cliffords span the space of complex matrices. $\endgroup$ Jan 7, 2021 at 9:28
  • $\begingroup$ My interest was specifically in expanding $\text{CNOT}^t$, in a way that I can derive the Clifford extent from the decomposition as a function of $t$. The first reference stated that this was an easy task by "exhaustive search" but I was wondering if there might be straightforward analytical approaches floating around $\endgroup$
    – forky40
    Jan 7, 2021 at 23:59
  • 1
    $\begingroup$ @forky40 I can hint you to some analytical simplifications of the optimisation problem, but I am pretty sure that you will not be successful in analytically solving it for this family of 2-qubit gates. In particular, my guess is that you would have to rely on numerical solutions. For single-qubit gates, this should in turn be possible since the geometry is very simple. $\endgroup$ Jan 8, 2021 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.