Return to Answer

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. 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 would not be a universal quantum gate.

This way, if we combinie the Toffoli gate whit the Hadamard gate, we may be able to get a complete universal quantum 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.

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.

The wikipedia article claiming that the quantum Toffoli gate is not a universal one is confusing and vague. This claim is not referenced in any source. Digging through the page history, I found this, where the author (an IP) comments: "you also need a set of non-trivial 1 qubit rotations such as Hadamard".

I don't understand quantum computing, but I thought the claim from that IP as doubtful, because the wikipedia states that the CNOT is a universal quantum gate and clearly the Toffoli may be used to implement the CNOT, which leads to a contradiction. Did not found any reference anywhere supporting his claim but did not found any refuting it too. I searched here and here and found no clear claim about the subject.

I searched other material in google to support or refute that claim, but the ones I found needed a very deep technical knowledge in this topic which I don't have, so I couldn't do it. A possible valuable reference, showing the foundations of the Deutsch transform should be here, however the link is password-protected.

Anyway, supposing that the claim of the author is correct (and the claim about the CNOT gate is not), this would mean that the Toffoli gate may be used only for 90 degrees 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 these requires phase-shifts on angles that are not multiple than 90 degrees, hence the Toffoli gate would not be a universal quantum gate.

EDIT 2: As this article states, the Toffoli gate is a universal quantum gate.

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 would not be a universal quantum gate.

This way, if we combinie the Toffoli gate whit the Hadamard gate, we may be able to get a complete universal quantum 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.

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

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

$NAND(a, b) = Toffoli'(a, b, 1)$

$NOT(x) = Toffoli'(1, 1, x)$

$AND(a, b) = Toffoli'(a, b, 0)$

$OR(a, b) = NOT(AND(NOT(a), NOT(b)) = Toffoli'(1, 1, Toffoli'(Toffoli'(1, 1, a), Toffoli'(1, 1, b), 0))$

$(a, b, c) = Toffoli(Toffoli(a, b, c))$

$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}$

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

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

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

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

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

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

$\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))$

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

$\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}$

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