Toffoli Gate

The Toffoli Gate is computational circuit suitable for reversible computing, invented by Tomasso Toffoli. It is universal, which means that any logical or arithmetic circuit can be constructed entirely of Toffoli Gates.

The basic Toffoli Gate is a form of controlled NOT gate that maps three inputs (A, B, I) onto three outputs (A, B, O). The A and B inputs are mapped directly to their corresponding outputs. If A and B are both 1, O = NOT I; otherwise I is copied unchanged to O. It is easy to see that this circuit is reversible, i.e., "undoes itself" when run backwards. A generalized n x n Toffoli Gate passes its first n-1 inputs to the corresponding outputs, and inverts its last outputs if and only if the first n-1 inputs are all 1.

See also the Fredkin Gate, which is a controlled swap gate for reversible computing.