| Prev: Introduction to Quantum Effects | Up: Contents | Next: Reversible Computations |
It appears that the laws of physics are completely reversible. That is, from any physical process we can always deduce the inputs from the outputs. Classical computers would at first appear to violate this law as we can easily create functions on classical computers that are not reversible. For instance consider the Boolean AND gate, the truth table for which is shown in Figure 9. There is no way of completely deducing the inputs of an AND gate from the outputs, and thus the AND gate appears not to be reversible.
| Input 1 | Input 2 | Output |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The answer to this riddle lies in waste heat. An AND gate in a classical computer produces waste heat as well as its intended output. The 'lost' information about the inputs contained in this waste heat.
In quantum computers, we cannot allow this situation to occur. The radiation of the heat would depend on the state of the inputs to the quantum gate. Thus, in effect, the radiation of the heat would be a measurement on the inputs and decoherence would ensue. The universes would be so far apart as to be unable to interfere with each and the result, which depends upon the interference of these universes, would be invalid. Thus quantum gates must be reversible. Reversible gates must, by their very definition, have an equal number of inputs and outputs.
Gates are called universal gates if they can be used to create any logic circuit, such as the NAND gate in classical circuits. Three other examples of universal gates are the Universal Toffoli gate, the Fredkin gate and the controlled NOT gate. These gates have the advantage that they are reversible as well as universal.
The Universal Toffoli Gate has three inputs. The first two inputs are copied to the first two output pins and the third output is the Exclusive OR of the third input and the AND of the first two inputs, as shown in Figure 10.
| Input 1 | Input 2 | Input 3 | Output 1 | Output 2 | Output 3 |
| 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 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
The Fredkin gate has three inputs. The last two inputs are swapped if the first input is 0 and is left untouched otherwise, as shown in Figure 11.
| Input 1 | Input 2 | Input 3 | Output 1 | Output 2 | Output 3 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
The Controlled NOT gate has two inputs. The second input is negated only if the first input is true, as shown in Figure 12.
| Input 1 | Input 2 | Output 1 | Output 2 |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 |
The controlled NOT gate has attracted much interest in the field of quantum computation as it is reversible while requiring only two inputs. The difficulty of building a quantum gate greatly rises with the number of inputs to gate. The proof that two input gates are universal for quantum circuits has brought the possibility of building a quantum computer one step closer [DiVincenzo 1995].
The square root of NOT gate is the first purely quantum gate that we shall examine and, from a classical point of view, is unusual in its behaviour. A single square root of NOT gate produces a completely random output with equal probabilities of the output being 0 or 1. However two such gates linked sequentially produce an output that is the inverse of the input, and thus behave in the same way as the a classical NOT gate.
This result is unparalleled in the classical world - one gate produces a random result while two gates linked sequential produce a deterministic result.
The truth table for the square root of NOT gate is shown below.
An input of |0> leads to an equal and opposite amplitude of the output being |0> or |1>. An input of |1> leads to a equal amplitude of the output of the gate being |0> and |1>.
Now lets see what happens when we join two of these gates, X and Y, together. As shown in Figure 13.
Let's say that the input to the first gate is |1>. The universe will split in to two universes, identical in every respect expect that the output to the first gate (X) is |0> in one universe and |1> in the other universe. Lets consider the |0> part of the superposition. This will get transformed in to
and the |1> portion of the superposition will get transformed in to
The total state of the system is then:
Note that the possibility of the output of the system being |1> is cancelled. Here you can see the interference of the quantum universes working. The universes can only interfere because they are identical in every regard except for this superpositioned particle. Suppose that we were to place a detector at M to tell us the value of the output to gate X. One copy of ourselves would note that the value is 0 while another copy in a different universe would note that the value is 1. Thus the universes would be different by billions of particles and could never again interfere. So just to know the value of the output of X invalidates the output of gate Y, even if our detector could measure the output of X accurately without disturbing the system.
| Prev: Introduction to Quantum Effects | Up: Contents | Next: Reversible Computations |
This web page (c) 2000 Jon Marshall. Last updated 1st June 2000