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).

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]...

Grote, J. G., Digital logic and reconiigurable interconnects using aluminum gallium arsenide electro-optic Fredkin gates, Ph.D. disseitation. University of Dayton, Dayton, OH, 1994. 

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]. 

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. 

Consider a logic gate with 3-iiiput and 3-output lines. Edward Fredkin, motivated by a deep conviction in a fundamental connection between a discrete, finite physics and reversible computation [wrightSS], discovered a simple universal 3-input/ 3-output logic function that now bears his name [fredkin82]. 

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. 

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. 

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. 

---