are used to build computer chips. Reversible logic gates are of interest because they could in principle generate useful results for less heat generated (Landauer 1961). The nand
gate is universal among irreversible logic gates, in the sense that it is possible to simulate any irreversible logic gate with a network of these gates. The Fredkin
gates were the first gates to be proved universal among reversible logic gates. However, this universality is not unusual in the space of 3 input and 3 output reversible gates.
A reversible logic gate of n
input bits must have n
output bits, by the pigeonhole principle. The reversibility requirements means that each of the 2<sup>n</sup> input combinations must have one and only one output combination - they must be a one-to-one map. Thus the outputs for the inputs are simply some permutation of the inputs, and so the number of n-input reversible gates is 2<sup>n</sup>! .
For a three-input gate, this number is 8!, around 40 thousand.
Let us define an define an equivalence relation: two gates are equivalent if the outputs of one can be gotten by rearranging the bits of the outputs of the other. That is, if we simply relabel the wires attached to the output terminals of the gate. Every gate, then, is a member of a 6-member equivalency class bringing the total number of possible gates down to 8000 or so. The three-input identity
is equivalent to this gate:
which merely swaps outputs 0 and... Read More