Reversible Gates


Now what about operationscomputing something with the numbers? It is known that if you can only do a few operations of the right kind, then by compounding the operations again and again in various combinations, you can do anything you want with numbers.

The usual way of discussing this fact is to have these numbers as voltages on a wire instead of states in an atom, so we'll start with the usual way. [Feynman draws a two-input AND gate at the blackboard.] We would have a device with two input wires A and B, and one output wire. If a wire has a voltage on it, I call it a "one"; if it has zero voltage, it's a "zero." For this particular device, if both wires are ones, then the output turns to one. If either wire is one, but not both, or if neither is one, the output stays at zerothat's called an AND gate. It's easy to make an electric transistor circuit that will do the AND gate function.

There are devices that do other things, such as a little device that does NOTif the input wire is a one, the output is a zero; if the input wire is a zero, the output is one. Some people have fun trying to pick one combination with which they can do everything, for example, a NAND gate that is a combination of NOT and ANDit is zero when both input wires are ones, and one when either or both inputs are not ones. By arranging and wiring NAND gates together in the correct manner, you can do any operation. There are a lot of questions about branchings and so forth, but that's all been worked out. I want to discuss what happens if we try to do this process with atoms.

First, we can't use classical mechanics or classical ideas about wires and circuits. We have atoms, and we have to use quantum mechanics. Well, I love quantum mechanics. So, the question is, can you design a machine that computes and that works by quantum-mechanical laws of physicsdirectly on the atomsinstead of by classical laws.

We find that we can't make an AND gate, we can't make a NAND gate, and we can't make any of the gates that people used to say you could make everything out of. You see immediately why I can't make an AND gate. I've only got one wire out and two in, so I can't go backwards. If I know that the answer is zero, I can't tell what the two inputs were. It's an irreversible process. I have to emphasize this fact because atomic physics is reversible, as you all know, microscopically reversible. When I write the laws of how things behave at the atomic scale, I have to use reversible laws. Therefore, I have to have reversible gates.

Bennett from IBM, Fredkin, and later Toffoli investigated whether, with gates that are reversible, you can do everything. And it turns out, wonderfully true, that the irreversibility is not essential for computation. It just happens to be the way we designed the circuits.

It's possible to make a gate reversible in the following cheesy way, which works perfectly. [Feynman now draws a block with two inputs, A and B, and three outputs.] Let's suppose that two wires came in here, but we also keep the problem at the output. So we have three outputs: the A that we put in, the B that we put in, and the answer. Well, of course, if you know the A and the B along with the answer, it isn't hard to figure out where the answer came from.

The trouble is that the process still isn't quite reversible, because you have two pieces of information at the input, that is, two atoms, and three pieces of information at the output. It's like a new atom came from somewhere. So I'll have to have a third atom at the input [he adds a third input line, labeled C]. We can characterize what happens as follows:

Unless A and B are both one, do nothing. Just pass A, B, and C through to the output. If A and B are both one, they still pass through as A and B, but C, whatever it is, changes to NOT C. I call this a "controlled, controlled, NOT" gate.

Now this gate is completely reversible, because if A and B are not both ones, everything passes through either way, while if A and B are both ones on the input side, they are both ones on the output side too. So if you go through the gate forward with A and B as ones, you get NOT C from C, and when you go backward with NOT C as the output, you get C back again at the input. That is, you do a NOT twice, and the circuit, or atom, is back to itself, so it's reversible. And it turns out, as Toffoli has pointed out, that this circuit would enable me to do any logical operation.

So how do we represent a calculation? Let's say that we have invented a method whereby choosing any three atoms from a set of N would enable us to make an interaction converting them from a state of ones and zeros to a new state of ones and zeros. It turns out, from the mathematical standpoint, that we would have a sort of matrix, called M. Matrix M concerts one of the eight possible combination states of three atoms to another combination state of the three atoms to another combination state of the three atoms, and it's a matrix whose square is equal to one, a so-called unitary matrix. The thing you want to calculate can be written as a product of a whole string of matrices like Mmillions of them, maybe, but each one involves only three atoms at a time.

I must emphasize that, in my previous example with AND gates and wires, the wires that carried the answer after the operation were new ones. But the situation is simpler here. After my matrix operates, it's the same registerthe same atomsthat contain the answer. I have the input represented by N atoms, and then I'm going to change them, change them, change them, three atoms at a time, until I finally get the output.




Nanotechnology. Science, Innovation, and Opportunity
Nanotechnology: Science, Innovation, and Opportunity
ISBN: 0131927566
EAN: 2147483647
Year: 2003
Pages: 204

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net