Editing Toffoli gate (section)

== Universality and Toffoli gate ==
Any reversible gate that consumes its inputs and allows all input computations must have no more input bits than output bits, by the [[pigeonhole principle]]. For one input bit, there are two possible [[Reversible computing|reversible]] gates. One of them is NOT. The other is the identity gate, which maps its input to the output unchanged. For two input bits, the only non-trivial gate (up to symmetry) is the [[controlled NOT gate]] (CNOT), which [[XOR gate|XOR]]s the first bit to the second bit and leaves the first bit unchanged.

{| style="text-align:center"
! Truth table !! [[Permutation matrix]] form
|- style="vertical-align:top"
| 
{| class="wikitable" style="margin:0; text-align:center"
! colspan="2" | Input
! colspan="2" | Output
|-
| 0 || 0 || 0 || 0
|-
| 0 || 1 || 0 || 1
|-
| 1 || 0 || 1 || 1
|-
| 1 || 1 || 1 || 0
|}
|
<math>
\begin{bmatrix}
 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 0 & 0 & 1 \\
 0 & 0 & 1 & 0 \\
\end{bmatrix}
</math>
|}

Unfortunately, there are reversible functions that cannot be computed using just those gates. For example, AND cannot be achieved by those gates. In other words, the set consisting of NOT and XOR gates is not [[functional completeness|universal]]. To compute an arbitrary function using reversible gates, the Toffoli gate, proposed in 1980 by Toffoli, can indeed achieve the goal.<ref name="Toffoli1980">Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version:
{{cite conference
 |url = http://pm1.bu.edu/~tt/publ/revcomp-rep.pdf
 |title = Reversible computing
 |first = Tommaso
 |last = Toffoli
 |authorlink = Tommaso Toffoli
 |year = 1980
 |conference = Automata, Languages and Programming, Seventh Colloquium
 |editor = J. W. de Bakker and [[Jan van Leeuwen|J. van Leeuwen]]
 |publisher = Springer Verlag
 |location = Noordwijkerhout, Netherlands
 |pages = 632–644
 |doi = 10.1007/3-540-10003-2_104
 |isbn = 3-540-10003-2
 |url-status = dead
 |archiveurl = https://web.archive.org/web/20100415041123/http://pm1.bu.edu/~tt/publ/revcomp-rep.pdf
 |archivedate = 2010-04-15
}}</ref> It can be also described as mapping bits {''a'', ''b'', ''c''} to {''a'', ''b'', ''c'' XOR (''a'' AND ''b'')}. This can also be understood as a [[modulo operation]] on bit ''c'': {''a'', ''b'', ''c''} → {''a'', ''b'', (''c'' + ''ab'') mod 2}, often written as {''a'', ''b'', ''c''} → {''a'', ''b'', ''c'' ⨁ ''ab''}.<ref>{{Cite book |last1=Nielsen |first1=Michael L. |title=Quantum Computation and Quantum Information |last2=Chuang |first2=Isaac L. |publisher=Cambridge University Press |year=2010 |isbn=9781107002173 |edition=10th |pages=29}}</ref>

The Toffoli gate is universal; this means that for any [[Boolean function]] ''f''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''m''</sub>), there is a circuit consisting of Toffoli gates that takes ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''m''</sub> and some extra bits set to 0 or 1 to outputs ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''m''</sub>, ''f''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''m''</sub>), and some extra bits (called garbage). A NOT gate, for example, can be constructed from a Toffoli gate by setting the three input bits to {''a'', 1, 1}, making the third output bit (1 XOR (''a'' AND 1)) = NOT ''a''; (''a'' AND ''b'') is the third output bit from {''a'', ''b'', 0}. Essentially, this means that one can use Toffoli gates to build systems that will perform any desired Boolean function computation in a reversible manner.