Toffoli gate

It is obvious to see from Table 1.5 that the input bits can be recovered by applying the gate to the output Therefore, the Toffoli gate is reversible. Now, if a basic set of gates could be built from Toffoli, then it will be demonstrated that computation can be made reversible. In fact, it is a simple matter to implement NAND from Toffoli. All we have to do is to set the target bit as 1 at the input, and Toffoli will work just as NAND. In Table 1.5, these correspond to the 2nd, 5th, 6th and 8th lines. The first two entries of these lines, plus the corresponding bits on the last column, is just NAND logic (see Table 1.6). 

P4.5 - Exemplify the action of the three-qubit Toffoli gate of 4.2.19 in some selected computational basis states. 

Taking the operator that represents the Toffoli gate with the first qubit as the target ... 

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. 

In general the Hadamard, Phase and NOT gates are 1-qubit operations, the CNOT gate is a 2-qubit operation, and the Toffoli is a 3-qubit operation... 

---