11
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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}$. $\endgroup$
    – M. Stern
    Oct 10, 2021 at 14:49
  • $\begingroup$ @M.Stern Thank you for your answer. Could you elaborate ? I am not sure to understand what you mean. $\endgroup$
    – Marco Fellous-Asiani
    Oct 10, 2021 at 15:49

3 Answers 3

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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) $\endgroup$
    – DaftWullie
    Oct 11, 2021 at 9:28
  • $\begingroup$ @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. $\endgroup$
    – Craig Gidney
    Oct 11, 2021 at 14:32
  • 1
    $\begingroup$ @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. $\endgroup$
    – Craig Gidney
    Oct 11, 2021 at 14:37
  • $\begingroup$ @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. $\endgroup$
    – Craig Gidney
    Oct 11, 2021 at 14:53
  • 1
    $\begingroup$ @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. $\endgroup$
    – Craig Gidney
    Oct 12, 2021 at 21:25
9
$\begingroup$

Quantum advantage using Clifford gates

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.

Quantum advantage using stabilizer circuits

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Marco Fellous-Asiani
    Oct 12, 2021 at 19:59
0
$\begingroup$

Integrated with other time-critical functions inside the (same) superconducting circuit the advantage will be latency as an classical simulator would introduce those.

Compounded latency could create a situation where a set of quantum clifford gates would have an edge not achievable with an external classical simulator.

https://en.wikipedia.org/wiki/Clifford_gates

Improve this answer
$\endgroup$

Your Answer

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

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