Cryptography Reference
In-Depth Information
Control
Control
s
t
x
y
Fredkin
Gate
IN
OUT
x y s t
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 1 0
1 1 0 1 0 1
111
111
Figure 8.1: An illustration of a Fredkin gate. If the control line is
on, then the output lines are switched. Otherwise, they're left alone.
(Drawn from Bennett's figure.[BL85])
The
Scientific American
article by Charles
Bennett and Rolf
Landauer makes a good
introduction to
reversible machines.
[BL85]
versed. This gate can be run in reverse because there is only one pos-
sible input for each output.
Figure 8.2 shows an AND gate built out of a Fredkin gate. One
of the two input lines from a normal AND gate is used as the control
line. Only one of the output lines is needed to give us the answer. The
other two bits are wasted. Ordinarily, the information here would be
thrown away by sending the bits to ground, where they would heat
up the chip. A truly reversible machine would store the bits at this
location until the computer was run in reverse. Then the gate would
have all of the information ready to compute the inverse. An OR gate
would be built in the same way, but it would have one input fixed to
be a
1
.
There are a number of other mechanical approaches to building
a reversible computer. Ed Fredkin and Tommaso Toffoli developed
a billiard ball computer that could be made to run in reverse
if
a
suitable table could be found [FT82]. It would need to be perfectly
smooth so the balls would move in synchrony. The table itself must
be frictionless and the bumpers would need to return all of the en-
