Clifford group quantum operations and classical computation

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?

• Quantum Toffoli gate is universal for quantum computation while Clifford group gates are not universal. Nov 23, 2010 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. Nov 23, 2010 at 20:52
• Toffoli + Clifford group is universal for efficient quantum computation, if I understand correctly Nov 23, 2010 at 20:54

1 Answer

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.

• 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). Nov 23, 2010 at 21:03
• Indeed, even just having Toffoli and Hadamard gates is enough (see the paper quant-ph/0301040, for instance). Nov 23, 2010 at 22:19
• Please consider joining: quantumcomputing.stackexchange.com .
– Rob
Apr 4, 2018 at 2:20