For reversible computation entropy does not increase. Since entropy is provides an order by which events occur, if an operation can occur and then reversed, then that operation gives an output with the same entropy as the input. In terms of what the user can observe, if the use is able to deduce the input based on the output, then the user can perform the operation in reverse with the output and obtain the input. That is, the operation can be performed reversibly, over and over again. One logical operation that is reversible is NOT: given an output of 1, it can be deduced that the input was 0, and vice-versa.
So then, is it possible to build a computer based on reversible gates? The answer is yes and the logic is very similar to that of irreversible gates. The reversibility of an operation is dependent on its ability to be backtracked, its ability for the user to determine its inputs given its output. Therefore it is fundamentally important that there is only a one to one mapping of input-output binary strings. If there are multiple inputs mapped to the same output, there would be no way of determining the input given that output. As a result, it can be seen that there must be as many input strings as there are output strings. This also implies that there must be as many input variables as there are output variables, given that the input and output have the same number of states (for binary, 0 and 1). Thus, one of the basic requirements for a reversible gate is that there are as many output variables as there are input variables.
Due to its applications in quantum computing the Fredkin gate and the Toffoli gate have received the most attention. Both gates have 3 inputs and 3 outputs. The Fredkin gate has two control bits that do not change. The third input changes (from 1 to a 0 or 0 to a 1) if the two control bits are both 1. The Toffoli gate has one control bit and interchanges the value of the other two bits if it’s a 1. Their truth tables are shown below
Toffoli Gate
|
Input |
Output |
||||
|
A |
B |
C |
A |
B |
C |
|
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 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
0 |
Fredkin Gate
|
Input |
Output |
||||
|
A |
B |
C |
A |
B |
C |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
1 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
0 |
Using specific input values for the Fredkin gate, it is possible to produce reversible gates for operations that were previously deemed irreversible, such as AND. Since such operations only required one output and multiple inputs (the reason for its irreversibility), the reversible version must then contain other output values to separate the many-to-one mapping. This is usually done in the form of retaining the initial input. Since these inputs might no longer be of use to the actual computation, they are dubbed as “junk bits”.
If it is possible to make reversible versions of irreversible gates, then it should also be possible to make a computer based wholly on reversible gates (i.e. a reversible computer). A reversible computer operates like a normal one with the exception of that it generates a significant amount of junk bits during its computation. The final result is then copied (without increasing entropy) and then the computation is wholly reversed giving the initial state without an increase in entropy at the same time resetting all the junk bits to 0.
The most well known possible application for reversible computing is quantum computing, which will increase the speed and power of computation possible enormously. However, there already is a limited application of reversible computing found in just about any computer. A CMOS (complementary metal oxide semiconductor) circuit uses reversible computing in its design. However, the catch is that - as stipulated in Bennet's original design of a reversible circuit - dissipation only tends to zero as the speed tends to zero (but any computer's dissipation is zero when its speed is zero!). In a quantum computer, this takes the form of external matter interacting with the qubits and increasing the chance of an error occuring.