12
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Quantum Toffoli gate is universal for quantum computation while Clifford group gates are not universal. $\endgroup$ – Mohammad Al-Turkistany Nov 23 '10 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$ – Antonio Valerio Miceli-Barone Nov 23 '10 at 20:52
  • 2
    $\begingroup$ Toffoli + Clifford group is universal for efficient quantum computation, if I understand correctly $\endgroup$ – Antonio Valerio Miceli-Barone Nov 23 '10 at 20:54
21
$\begingroup$

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.

$\endgroup$
  • $\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$ – Antonio Valerio Miceli-Barone Nov 23 '10 at 21:03
  • 4
    $\begingroup$ Indeed, even just having Toffoli and Hadamard gates is enough (see the paper quant-ph/0301040, for instance). $\endgroup$ – Ashley Montanaro Nov 23 '10 at 22:19
  • $\begingroup$ Please consider joining: quantumcomputing.stackexchange.com . $\endgroup$ – Rob Apr 4 '18 at 2:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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