Quantum advantage with only Clifford gates (Gottesman Knill theorem)

Let's say I want to solve a computational task which input can be encoded in $$n$$ bits of information.

The look for a quantum advantage is (usually) asking to find a quantum algorithm in which there are exponentially fewer gates and qubits required in order to implement this algorithm compared to the best known classical algorithm.

Gottesman Knill theorem shows that it is possible to simulate in polynomial time a quantum algorithm composed of Clifford gates only. For this reason, it removes the ability to find a quantum advantage with circuits only composed of such gates (the non-Clifford are very "costly" in term of physical resources).

However, if a classical algorithm requires (for instance) $$O(n^{800})$$ gates while the quantum $$O(n)$$, the gain with the quantum algorithm would still be phenomenal.

My question is thus:

Are there examples of quantum algorithms only composed of Clifford operations that show "for all practical purpose" a clear advantage in computational speed over the best known classical algorithm? A reduction in the "same spirit" of the $$n^{800} \to n$$ for instance. Such result would be interesting because fault tolerant quantum computing can be efficiently implemented with only Clifford gates.

Also, my formulation of the quantum advantage is probably a bit "handwavy" so if you believe it is not entirely correct I would be interested in providing me a better way to phrase it.

• There are explicit constructions of algorithms for the Gottesman Knill theorem. I don't know the details right now, but I'm pretty sure they do not have a runtime of $n^{800}$. Oct 10 '21 at 14:49
• @M.Stern Thank you for your answer. Could you elaborate ? I am not sure to understand what you mean. Oct 10 '21 at 15:49

Are there examples of quantum algorithms only composed of Clifford operations that show [...] A reduction in the "same spirit" of the $$n^{800}→n$$ for instance.

No. An $$n$$ qubit Clifford+measure circuit with $$m$$ operations can be simulated in $$O(n^2m)$$ time (arXiv:quant-ph/0406196) with small constant factors (arXiv:2103.02202).

• Might one argue that even a square-root speed-up could be in the "same spirit"? Clearly the gains from something like Grover are appreciated as being potentially huge. (I'm using Grover as an example of a square root speed-up, not a case of Clifford-only) Oct 11 '21 at 9:28
• @DaftWullie I would say there's a pretty clear distinction between cubic time and $n^{800}$. There are cubic time algorithms that people actually use in practice, such as Gaussian elimination. The question was whether Clifford sim fell in the "usable in practice" bucket or not. Oct 11 '21 at 14:32
• @DaftWullie On a quantum computer, accounting for error correction overhead, I think the CPU hours for stabilizer sampling grow like $O(nm)$. So you run into the obstacles discussed by arxiv.org/abs/2011.04149 ; the size of problem you need for the quadratic advantage to outweigh the bad constant factors becomes enormous. A minor obstacle is that some quantum architectures fold Clifford operations into the control system; you have to be careful to turn that off lest the compiler do all the work classically instead of on the quantum machine. Oct 11 '21 at 14:37
• @DaftWullie Also keep in mind the classical algorithm is extremely parallel. It can be built out of bitwise operations applying to $n$ bit pairs in parallel, and for dense circuits you can also be working on $O(n)$ gates in parallel. Probably we don't care about this problem enough to make custom ASICs, the way they do for machine learning, but if we did those ASICs would be very tough competition. Even with just a CPU you can do random circuits with $n=10^3$, $m=10^6$ in a few seconds. Oct 11 '21 at 14:53
• @StarBucK The quantum computer needs error correction which has computational cost scaling with space used. Also, if you're going to allow parallel operation of the quantum computer you should also allow parallel operation of the classical computer. Clifford sims are highly parallelizable. The quantum computer has an advantage, I think, but it's just quadratic. Oct 12 '21 at 21:25

Gottesman-Knill theorem applies to stabilizer circuits only, not to all circuits consisting of Clifford gates. The former satisfy the stronger requirements of having a stabilizer input state and using only stabilizer basis measurements.

Note that availability of magic states enables one to apply non-Clifford gates using Clifford gates, stabilizer measurements and classical control. For example, the state $$(|0\rangle+e^{\frac{i\pi}{4}}|1\rangle)/\sqrt{2}$$ enables one to apply the non-Clifford $$T$$ gate, see the circuit in figure 10.25 on page 486 in Nielsen & Chuang.

Consequently, it is quite possible that quantum advantage can be achieved using circuits consisting of Clifford gates only. Moreover, the advantage is likely to be exponential as in other models of universal quantum computation.

On the other hand, there is no computational task which provides a high-degree polynomial separation between classical and quantum algorithms. This follows from the existence of a very efficient simulation algorithm for stabilizer circuits. Specifically, the tableau algorithm described in this paper simulates $$k$$-qubit stabilizer circuits at the cost of $$O(k)$$ classical operations per unitary gate and $$O(k^2)$$ classical operations per measurement.
Consequently, in the example situation described in the question where a problem admits a classical algorithm with $$O(n^{800})$$ operations and a quantum algorithm with $$O(n)$$ gates, the tableau simulation of the letter would constitute a classical algorithm with low-degree polynomial complexity depending on the details of the quantum circuit but not worse than $$O(n^3)$$.
• Thank you for your answer. Indeed I wasn't very precise but I was thinking about stabilizer circuits. In the same line of thought about the comment I have written for CraigGidney, the quantum algo runtime does not depend on the number of qubits but on the algo depth. Because of that it would not depend on $k$. Cannot we still find some quantum advantage then ? For instance the classical algo simulation runtime would scale linearly with $k$ but the quantum algo runtime would be independent of $k$. Oct 12 '21 at 19:59