Have an Android phone?

Try our new game!

Toffoli gate

Toffoli gate (CCNOT gate, controlled-controlled-not) is a universal reversible logic gate, named its inventor, Tommaso Toffoli[1].

3 input Toffoli gate, mapping bits a, b and c to a, b and c XOR (a AND b).

The response of the Toffoli gate is such that its input can always be backward computed from its output. "Usual" elements often lack this capability. For instance, it is not clear which of the three possible input combinations (01, 10 or 11) has brought the AND element in the active state. From the other side, the inverter (NOT gate) is reversible: its input has the opposite value than its output. Another common element of the quantum computer is a controlled NOT gate that flips (inverts) the second input only if the first input is 1 (the first input is passed unchanged). However inverter and controlled NOT alone are not sufficient to build the circuit for arbitrary logic.

Toffoli gate maps the input bits a, b and c to a, b and c XOR (a AND b)[2]. It is an universal element: one can use Toffoli gates to build systems that will perform any desired boolean function computation in a reversible manner.

Theoretically, reversible logic should allow to build computers that consume no energy, as there is no entropy dissipation (no information is lost). However while gates themselves can be easily built using recent technologies, implementation using usual non-reversible logic gates gives no advantage in energy consumption.

Multi input Toffoli gate

The number of inputs in the gate can be easily extended, but the majority of inputs xi (excluding the last one, xn) are simply transferred to the matching outputs unchanged. Only the last bit is processed differently as is equal to (x1 AND ... AND xn−1) XOR xn. The number of inputs is always equal to the number of outputs.

See also

Another universal reversible gate is Fredkin gate that performs a controlled-swap operation. It swaps the last two bits if the first bit is 1.

References

  1. 1 Toffoli T (1980) Reversible computing. Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version, 632-644, ISBN 354010003 2
  2. 2 Wikipedia article on Toffoli gate