The Clifford group of quantum operators is generated by the quantum operations:

  • Controlled-Z,
  • Hadamard, and
  • Phase ($= |0\rangle\langle0| + i |1\rangle\langle1|$).

A circuit composed only of these gates can be simulated efficiently on a classical computer. However, if I understand correctly, not all classical algorithms can be implemented efficiently using Clifford group operations, at least as far as we know.

Is there a construction to implement, even inefficiently or approximately, a classical algorithm using Clifford group operations? For instance, how do you implement a Toffoli gate using Clifford group gates, if it's possible?

  • 2
    $\begingroup$ Quantum Toffoli gate is universal for quantum computation while Clifford group gates are not universal. $\endgroup$ Nov 23, 2010 at 19:34
  • 2
    $\begingroup$ In my understanding, Toffoli gate alone isn't universal for efficient quantum computation, since it takes computational basis states into other computational basis states. $\endgroup$ Nov 23, 2010 at 20:52
  • 2
    $\begingroup$ Toffoli + Clifford group is universal for efficient quantum computation, if I understand correctly $\endgroup$ Nov 23, 2010 at 20:54

1 Answer 1


As pointed out in a comment above, if it were possible to coherently implement a Toffoli gate using Clifford group gates, then the Clifford group would be universal for quantum computation. It was noted in Section 5 of this paper that something even stronger is true: informally speaking, if there exists a class of quantum circuits which can be simulated efficiently classically, and which is universal for classical computation, then BQP=BPP. Thus we would expect simulable classes of quantum circuits not to be universal for classical computation.

Clifford group circuits themselves are particularly weak, and correspond to the complexity class Parity-L, as was shown here.

  • $\begingroup$ Thanks for the references. Now that you mention, I seem to remember that Nielsen & Chuang describe a Toffoli + Clifford group construction that is universal for quantum computation (I can't access the book at the moment). $\endgroup$ Nov 23, 2010 at 21:03
  • 4
    $\begingroup$ Indeed, even just having Toffoli and Hadamard gates is enough (see the paper quant-ph/0301040, for instance). $\endgroup$ Nov 23, 2010 at 22:19
  • $\begingroup$ Please consider joining: quantumcomputing.stackexchange.com . $\endgroup$
    – Rob
    Apr 4, 2018 at 2:20

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.