# Clifford group quantum operations and classical computation

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

• Controlled-Z,
• 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?

• Quantum Toffoli gate is universal for quantum computation while Clifford group gates are not universal. – Mohammad Al-Turkistany Nov 23 '10 at 19:34
• In my understanding, Toffoli gate alone isn't universal for efficient quantum computation, since it takes computational basis states into other computational basis states. – Antonio Valerio Miceli-Barone Nov 23 '10 at 20:52
• Toffoli + Clifford group is universal for efficient quantum computation, if I understand correctly – Antonio Valerio Miceli-Barone Nov 23 '10 at 20:54