Fredkin reversibility

Consider now the dynamics of the active (i.e., non-decoupled) part of the lattice. It is easy to see that the Fredkin-reversible form of R129 conserves the number of initial state blocks of the form This simple conservation law induces the... 

We recall from the previous section that a second-order Fredkin-reversible rule can always be redefined as a conventional first-order one, but only at a cost of... 

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

Recalling Bennett s and Fredkin s trick to erase the garbage bits, the way in which the reversible logic circuit in figure 6.9 can be made to act as a real reversible serial-adder circuit is to first operate the circuit as shown, store the desired output, and then operate it backwards using the output and all intermediary garbage bits as new input. After all operations are completed in the reverse direction, we will be left with our desired answer stored on the side and with the serial-adder circuit back in its original state ready for another run. 

Since equation 8.4 can be trivially solved for Oi t - 1) (= 4 [aj t) A/)] 0/c ai t + 1)), we see that any pair of consecutive configurations uniquely specifies the backwards trajectory of the system. Moreover, this statement holds true for arbitrary (and, in particular, irreversible) functions < ). An important consequence of this, first pointed out by Fredkin [vich84a], is that a numerical roundoff in digital computers need not necessarily result in a loss of information. In particular, if the computation is of the form given by equation 8.4, where roundoff error, the resulting dynamics will nonetheless be reversible and no information will be lost throughout the computation. ... 

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. 

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.

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. 

---