Toffoli Gate - Universality and Toffoli Gate

Universality and Toffoli Gate

Any reversible gate must have the same number of input and output bits, by the pigeonhole principle. For one input bit, there are two possible 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 is the controlled NOT gate which XORs the first bit to the second bit and leaves the first bit unchanged.

Truth table Matrix form
INPUT OUTPUT
0 0 0 0
0 1 0 1
1 0 1 1
1 1 1 0

\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}

Unfortunately, there are reversible functions that cannot be computed using just those gates. In other words, the set consisting of NOT and XOR gates is not universal (see functional completeness). If we want to compute an arbitrary function using reversible gates, we need another gate. One possibility is the Toffoli gate, proposed in 1980 by Toffoli.

This gate has 3-bit inputs and outputs. If the first two bits are set, it flips the third bit. The following is a table of the input and output bits:

Truth table Matrix form
INPUT OUTPUT
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 0

\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix}

It can be also described as mapping bits a, b and c to a, b and c XOR (a AND b).

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.

Read more about this topic:  Toffoli Gate

Famous quotes containing the word gate:

    “Duns at his lordship’s gate began to meet;
    And brickdust Moll had screamed through half the street.
    The turnkey now his flock returning sees,
    Duly let out a-nights to steal for fees:
    The watchful bailiffs take their silent stands,
    And schoolboys lag with satchels in their hands.”
    —Jonathan Swift (1667–1745)