Toffoli Gate - Background

Background

A logic gate L is reversible if, for any output y, there is a unique input x such that applying L(x) = y. If a gate L is reversible, there is an inverse gate L′ which maps y to x for which L′(y) = x. From common logic gates, NOT is reversible, as can be seen from its truthtable below.

The common AND gate is not reversible however. The inputs 00, 01 and 10 are all mapped to the output 0.

Reversible gates have been studied since the 1960s. The original motivation was that reversible gates dissipate less heat (or, in principle, no heat). In a normal gate, input states are lost, since less information is present in the output than was present at the input. This loss of information loses energy to the surrounding area as heat, because of thermodynamic entropy. Another way to understand this is that charges on a circuit are grounded and thus flow away, taking a small quantity of energy with them when they change state. A reversible gate only moves the states around, and since no information is lost, energy is conserved.

More recent motivation comes from quantum computing. Quantum mechanics requires the transformations to be reversible but allows more general states of the computation (superpositions). Thus, the reversible gates form a subset of gates allowed by quantum mechanics and, if we can compute something reversibly, we can also compute it on a quantum computer.