Universality of the Toffoli gate

Question

Regarding the quantum Toffoli gate:

1. is it classicaly universal, and if so, why?
2. is it quantumly universal, and why?

Answer 1

Toffoli is universal for classical computation (as shown by @Victor). However, Toffoli is NOT universal for quantum computation (unless we have something crazy like $P = BQP$).

To be universal for quantum computation (under the usual definition), the group generated by your gates has to be dense in the unitaries. In other words, given an arbitrary $\epsilon$ and target unitary $U$ there is some way to apply a finite number of your quantum gates to get a unitary $U'$ such that $||U - U'|| < \epsilon$.

Toffoli by itself is clearly not universal under this definition since it always takes basis states to basis states, and thus, for example, it cannot implement something that takes $|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$. In other words, it cannot create superposition.

Answer 2

From the wikipedia article that you cited:

The Toffoli gate is universal; this means that for any boolean function f(x1, x2, ..., xm), there is a circuit consisting of Toffoli gates which takes x1, x2, ..., xm and some extra bits set to 0 or 1 and outputs x1, x2, ..., xm, f(x1, x2, ..., xm), and some extra bits (called garbage). Essentially, this means that one can use Toffoli gates to build systems that will perform any desired boolean function computation in a reversible manner.

Which means in simple terms that any boolean function may be constructed only with Toffoli gates.

Boolean functions are typically constructed from OR, AND and NOT gates, which may be combined to form any boolean function. It is widely know that the same is possible only with NOR gates or only with NAND gates.

The Toffoli gate may be summarized as:

$\rm{Toffoli}(a, b, c) = \begin{cases} (a, b, ¬c) & \mbox{when }a=b=1 \\ (a, b, c) & \mbox{otherwise.}\end{cases}$

Since the first and the second outputs are always equal to the first and second inputs, we may disconsider them. So we have:

$\rm{Toffoli}'(a, b, c) = \begin{cases} ¬c & \mbox{when }a=b=1 \\ c & \mbox{otherwise.}\end{cases}$

With that, it is possible to define the NAND gate as:

$\operatorname{NAND}(a, b) = \rm{Toffoli}'(a, b, 1)$

Since the NAND gate is universal and the NAND gate may be defined as a Toffoli gate, then the Toffoli gate is universal.

There is another way to prove that Toffoli is universal, by direct constructing the AND and NOT gates:

$\operatorname{NOT}(x) = \rm{Toffoli}'(1, 1, x)$

$\operatorname{AND}(a, b) = \rm{Toffoli}'(a, b, 0)$

Then, we may construct the OR gate using De Morgan's laws:

$\operatorname{OR}(a, b) = \operatorname{NOT}(\operatorname{AND}(\operatorname{NOT}(a), \operatorname{NOT}(b)) = \rm{Toffoli}'(1, 1, \rm{Toffoli}'(\rm{Toffoli}'(1, 1, a), \rm{Toffoli}'(1, 1, b), 0))$

---

EDIT, since the question was edited and its scope changed:

First, I don't understand quantical computing, so if there is something wrong, please add a comment. I did a little research to try to make this answer complete and ended with this:

The Toffoli gate is reversible (but the Toffoli' used above is not). This means that any computation did with it can be undone. This is:

$(a, b, c) = \rm{Toffoli}(\rm{Toffoli}(a, b, c))$

Which means that for any triple (a, b, c) if the Toffoli is applied twice, the original input is get as the output.

Reversibility is important because quantum gates must be reversible, so the (classical) Toffoli gate may be used as a quantum gate due to this.

As demonstrated here, the Deutsch gate is defined in a similar way that the Toffoli gate is, but instead of a classical gate, it is a quantical one:

$\operatorname{Deutsch}(a, b, c) = |a,b,c\rangle \mapsto \begin{cases} i \cos(\theta) |a,b,c\rangle + \sin(\theta) |a,b,1-c\rangle & \mbox{for }a=b=1 \\ |a,b,c\rangle & \mbox{otherwise.}\end{cases}$

In this way, the Toffoli gate is a particular case of the Deutsch gate where:

$\rm{Toffoli}(a, b, c) = \operatorname{Deutsch}(\frac{\pi}{2})(a, b, c)$

The Toffoli gate does classical computation, it lacks a phase-shift operation, this would mean that the Toffoli gate may be used only for 90 degrees ($\frac{\pi}{2}$) phase-shifts (and by combining multiple gates, to get multiples of 90 degrees). But this also means that it can't be used to create state sobrepositions because this would require phase-shifts on angles that are not multiple than 90 degrees, hence the Toffoli gate is not a universal quantum gate.

A universal quantum Tgate set may be obtained, if we combine the Toffoli gate whit the Hadamard gate. This is exactly what the Deutsch gate does.

Interesting references can be found here, here and here. A possible valuable reference, showing the foundations of the Deutsch transform should be here, however the link is password-protected.