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.