Fortunately, the primitive ERASE is not absolutely essential in computation. To see why, consider what is required to compute arbitrary functions using reversible logic (where the primitive ERASE is forbidden). Landauer showed how any function could be made one-to-one by keeping a copy of the input:

Here the parentheses represent an ordered set of values, in this case, two. Extra ``slots'' will be added (or removed) as required in our discussion below.

How can this trick be used to perform reversible logic? One solution, known as the Toffoli gate, is shown in Fig. 4 [8,10,11]. The output of this gate may be decomposed into various gates:

where represents an AND gate, represents an XOR gate and represents a NOT gate. We see that this gate is universal, because it performs AND, XOR, NOT or FANOUT depending on its inputs. A combination of many such gates could then be used for any computation and would still be reversible.

**Fig. 4** Three-input three-output universal reversible Toffoli gate.
This gate is clearly reversible since a second application of it
retrieves the original input.

As noted by Landauer, this procedure leads to an immediate problem because of the absence of the primitive ERASE. The more gates we employ, the more ``junk'' bits we accumulate: At each gate we must save input bits in order to preserve reversibility. In other words a computer built out of reversible logic instead of conventional, irreversible logic gates would behave like

with many extra junk bits .

Bennett solved this problem by showing that the junk bits could be
* reversibly * erased at intermediate steps with minimal run-time and
memory costs [12,13]. The spirit of Bennett's
solution may be understood in terms of the following procedure:

where denotes uncomputing **f**, as opposed to computing
. First, **f** is computed, producing both junk bits and the
desired output. Then the FANOUT gate is applied to duplicate the output.
Finally, we uncompute the original function **f** by running
its computation backwards. This procedure removes the junk bits and
the original output. The duplicate, however, remains!

This completes our discussion of the construction of classical, reversible computers. We have found that reversibility does not bar the logical design of computing machines. Before mapping these ideas to quantum systems, however, we introduce some elementary quantum mechanical notation.

Wed Aug 23 11:54:31 IDT 1995