<p>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 <a href="http://arxiv.org/abs/0908.1467">this paper</a> 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 <i>classical</i> computation, then BQP=BPP. Thus we would expect simulable classes of quantum circuits not to be universal for classical computation.</p>

<p>Clifford group circuits themselves are particularly weak, and correspond to the complexity class Parity-L, as was shown <a href="http://arxiv.org/abs/quant-ph/0406196">here</a>.</p>

CC BY-SA 3.0
2018-04-04T02:20:50.457Z
Please consider joining: https://quantumcomputing.stackexchange.com/ .
Rob
CC BY-SA 2.5
2010-11-23T21:03:47.677Z
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).
Antonio Valerio Miceli-Barone
CC BY-SA 2.5
2010-11-23T22:19:39.043Z
Indeed, even just having Toffoli and Hadamard gates is enough (see the paper quant-ph/0301040, for instance).
Ashley Montanaro
CC BY-SA 2.5
2010-11-23T19:53:28.553Z
2010-11-23T19:53:28.553Z
Ashley Montanaro
<p>The <a href="http://arxiv.org/abs/quant-ph/0603226">Clifford group</a> of quantum operators is generated by the quantum operations:</p>

<ul>
<li><em>Controlled-Z</em>,</li>
<li><em>Hadamard</em>, and</li>
<li><em>Phase</em> ($= |0\rangle\langle0| + i |1\rangle\langle1|$).</li>
</ul>

<p>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.</p>

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

CC BY-SA 2.5
2010-11-23T19:34:02.587Z
Quantum Toffoli gate is universal for quantum computation while Clifford group gates are not universal.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-23T20:52:55.903Z
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
CC BY-SA 2.5
2010-11-23T20:54:30.053Z
Toffoli + Clifford group is universal for efficient quantum computation, if I understand correctly
Antonio Valerio Miceli-Barone
<quantum-computing>
Clifford group quantum operations and classical computation
Antonio Valerio Miceli-Barone
# Clifford group quantum operations and classical computation

(Asked by: username_0 on 2010-11-23)

The [Clifford group](http://arxiv.org/abs/quant-ph/0603226) 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?

**Tags:** quantum-computing

> **Comments:**
> **username_1**: Quantum Toffoli gate is universal for quantum computation while Clifford group gates are not universal.  
> **username_0**: In my understanding, Toffoli gate alone isn't universal for efficient quantum computation, since it takes computational basis states into other computational basis states.  
> **username_0**: Toffoli + Clifford group is universal for efficient quantum computation, if I understand correctly  

---

## 1 answers

### Answer by username_2 on 2010-11-23. Score: 24 | Accepted 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](http://arxiv.org/abs/0908.1467) 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](http://arxiv.org/abs/quant-ph/0406196).

> **Comments:**
> **username_0**: 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).  
> **username_2**: Indeed, even just having Toffoli and Hadamard gates is enough (see the paper quant-ph/0301040, for instance).  
> **username_3**: Please consider joining: https://quantumcomputing.stackexchange.com/ .  

---

