The Fredkin Gate

Fig. 6.7 Schematic representations and truth tables for the Fredkin gate and Reversible-AND gate. In the Fredkin gate, the c-line is the control line in the reversible-AND gate, lines gi and 92 are the garbage lines (see text).

There is another gate which can be used to prove reversible computation. It is the Fredkin gate it performs a controlled swap operation between two bits [6]. 

Fig. 6.8 Fredkin-gate realizations of conventional OR, NOT and FAN-OUT operations. The desired outputs of each gate are shown in large type the other output lines are the garbage lines.

Fig. 6.9 A conservative-logic realization of a conventional serisJ adder circuit it is built entirely of Fredkin gates. Places along the wires marked with a dot represent unit time delays at those locations. Illustration patterns after [marg88] and [fredkin82]...

Obviously that B and C can be recovered by applying the gate to B and C. Tha-efore, the gate is reversible. Fredkin gate can be used to built an universal set of classical logic gates. 

Note that since the Fredkin-Toffoli gate is reversible and all the states are normalized, U(l) is unitary. Other universal gates like the NAND-gate which is common in classical logic are not reversible. As a consequence, they cannot be described by a unitary matrix and are not directly realizable by quantum means. 

The previous section describes a Turing machine in which the basic computational steps are all reversible. Furthermore, the basic steps take place in a local region of the three tapes. Therefore it is easy to obtain local, unitary transformations Uj for any step i that might occur during a computation. This has already been done in Sect. 5.2 for the Fredkin-Toffoli gate as a simple example. 

Toffoli gate (see Sect. 5.2 and Fig. 5.1), and to shift information on the polymer computer. Since the Fredkin-Toffoli gate is universal, this is obviously sufficient to realize a computer that can simulate any other computer. 

Fig. 5.1 The truth table for the reversible and universal Fredkin-Toffoli gate with three input lines (A, B, C) and three output lines (A , B , C ). If C is set to one, the values of lines A and B are exchanged. Otherwise, the signals are simply passed unchanged.

As a simple example, consider programming a logical gate in this way that acts on a string of three binary digits according to the truth table of a so-called Fredkin-Toffoli gate [14] in Fig. 5.1. 

Fredkin-Toffoli gates are of importance since they are reversible and universal. The reversibility is obvious from the truth table Given the output triple A B C , the unique input corresponding to this can be found. Universal means that a computer can be constructed solely from Fredkin-Toffoli gates and still perform any computation that any other computer can do. 

To implement a Fredkin-Toffoli gate the sequence, and cjjj can... 

Fredkin-Toffoli gate exchanges the bits on A and B only if C is set to 0. 

---