# Universality of the Toffoli gate

Regarding the quantum Toffoli gate:

1. is it classicaly universal, and if so, why?
2. is it quantumly universal, and why?
-
In non-quantum logic, you show that another set of boolean operators that is known to be universal can be simulated by the set at hand. I don't know wether it is the same in the quantum world, but I would think so. –  Raphael Mar 13 '12 at 7:43
In quantum logic, the Toffoli gate is not universal, because you can only do classical computations with it. You also need some quantum gate that, if the input is in a basis state, puts the output into a superposition of basis states. –  Peter Shor Mar 13 '12 at 15:18
I realize the question might be confusing, maybe it should be edited to ask the difference between universality in the quantum/classical world. –  Ran G. Mar 13 '12 at 17:08
I edited my answer to cover the quantum case. What do you think now? –  Victor Mar 14 '12 at 1:30
@RanG. We are supposed to show the way for future questions, this question is tagged homework, yet it appears that you do not explain why you could not solve it yourself (and where lies the problem). I think it is not a good question for the private beta (see the meta discussion). I vote to close this question. –  Gopi Mar 14 '12 at 16:24

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 you 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 can not implement something that takes $|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ for example. In other words, it cannot create superposition.

-

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.

-
Toffolli is not universal for quantum computation, neither is CNOT by themselves. This is easy to see since they cannot create superposition. –  Artem Kaznatcheev Mar 14 '12 at 2:09
The classical part of your answer is great, I'm not sure the quantum parts make as much sense. There is no need to argue that Toffoli gate is a reversible, since it is a valid quantum gate and thus, by definition, reversible. As for Edit2: that article says that $\{$Hadamard, Toffoli$\}$ is a universal set, but I don't think it says Toffoli is q-universal on its own (or did I miss anything?) –  Ran G. Mar 14 '12 at 2:09
Your reference in EDIT 2 is wrong. That article clearly states that Toffoli + Hadamard is universal, not Toffoli by itself –  Artem Kaznatcheev Mar 14 '12 at 2:10
@ArtemKaznatcheev: The article says "Toffoli and Hadamard". Then I thought that this meant "Toffoli is an example and Hadamart is another one". Anyway it is clear now. –  Victor Mar 14 '12 at 4:14
I edited it, should be ok now. –  Victor Mar 14 '12 at 4:29