Clifford group quantum operations and classical computation

Question

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?

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.