2 Information and Computation are Physical
An operation is “logically
reversible" if it can be run backwards, that is, if its inputs can always be deduced from
the outputs. Most logical gates are irreversible; a typical example is the
NAND gate
 |
(1) |
which has two input bits and only one output
bit. We cannot recover a unique input from the output bit because the result
1 can be obtained from three distinct inputs: 
.
Assume we operate the gate NAND with two Boolean variables, 
, and suppose that the four
initial states, 
, have the
same probability distribution, 
. Then, the initial entropy, which is calculated with Shannon’s
formula
is then
The result will be a system with only two possible states, 
and 
, the
outcome appearing with probability and the outcome appearing with probability 
. Consequently, the final entropy
is
which means a loss of
Assume now that we operate the gate
and, again, suppose that the four initial states of the Boolean variables
have the same probability
distribution, . This gate
has finally only three final states, namely 
, two of them with probability and one with probability 
. Consequently, the final entropy
is
In this case, the gate decreases the entropy by 
bits.
The first gate is “more irreversible" than the second one, since it decreases
the entropy more.
In thermodynamics the entropy is defined by
Von Neumann noticed that the two entropies are related by some constant factor,
so they are in fact the same notion. Hence a natural question arises: what is the minimum energy required to carry out
a computation? In 1961 Landauer [81] (see also [84] and also Feynman [61]) had a first answer. To operate a
computer we have to ensure that distinct logical states are represented by
distinct physical states. Each bit has two values, 0, 1, so it has one degree
of freedom; it corresponds to one or more degrees of freedom of physical
states. In general, a set of 
bits has
degrees of freedom; they correspond to
physical states. If we erase bits (which could be in any of the possible logical states), say we reset all
to 0, then we have compressed logical
states into a single state, a loss of entropy. The irreversible loss information
increases the temperature of the system, which means heat dissipation. Consequently,
operations which are not one-to-one cost
energy. This cost is expressed by
Landauer’s principle: erasure of
information is a dissipative process.
Here is a simple “home" example. We
need two basketballs to design a system of representing information. Put
one on the floor by your left foot and hold the other in your (right) hand.
Zero (0) is represented by the ball on the floor; one (1) is represented
by the ball in your hand. Assume that we want to erase the bit 1, that is the bit in your hand. To do this you have to drop the ball. Simple? Not really, as the ball does not get directly into the floor (to become a 0), but in fact bounces for a while.
With a perfectly elastic basketball and a good hard floor the ball may bounce
close to your hand, i.e., to the 1 position! To settle down into 0 the ball
has to encounter friction, with the air molecules and the floor. Eventually
friction slows down the ball, so 1 has been erased. We could do it because
the energy from bouncing the ball has
been transmitted to the floor and the air. In a vacuum with a perfect frictionless floor erase would be
impossible! Energy is consumed in the process of erasure.
Here is another example: the gate 
dissipates at least 
joules of energy if we assume that the process is isothermal
at temperature 
.
The energy dissipation has been reduced
by approximately a factor of ten every five years, so a rough extrapolation
suggests that a reduction of the energy dissipation per logic operation below
(thermal noise, that is of the order of
picojoule at room temperature) may become
relevant in about 10-15 years. This issue may cause a variety of problems
for classical computers, e.g. cooling may be difficult (according to current
day knowledge/technology).
Irreversible operations as the NAND gate (1
), the binary addition 
(sum
and carry) and the real addition 
, dissipate energy. Is logical reversibility dissipation free?
First, let us note that the above irreversible operations can be easily simulated
by reversible ones. A reversible version of the NAND gate
is, for
example, Toffoli’s gate
 |
(2) |
Indeed, (2) is a reversible 3-bit gate that flips
the third bit if the first two take the value 1 and does nothing otherwise.
Hence, the third output bit becomes the NAND of 
and 
in case 
. The price paid to get reversibility consisted
of adding a new variable 
.
Similar tricks can be used to produce reversible versions of the binary addition,
and real addition 
. In the first case we replicated
the first variable ; in the second case
we added a new component storing some additional value.
A computer may be fully reversible and yet dissipate energy! The important
point is that the laws of physics allow for technologies to make reversible
computers operate with negligible dissipation. To build a reversible computer
one needs only two types of logical gates, say AND and NOT (because any other
gate can be constructed from these two types – they are universal). Clearly, the NOT gate is reversible as its composition with
itself gives the initial input. However, the AND gate is irreversible. Reason:
it has two inputs and only one output, so it has to lose information (it
is impossible to tell exactly what inputs must have been if all one is told
is the output 0: any of the three combinations , could have been the “real input").
To make a reversible variant of the gate AND we need to make sure that we
have the same number of output lines as input ones, so, in principle, we
can just add some “garbage" output lines to solve the problem. However, this
may not be enough, as we want to guarantee also universality! One possibility
is Toffoli’s [63] reversible 3-bit gate
which uses in addition to a control bit . Input bits
and
do not change their states; the control bit, however, will change its state,
but only when 
. Toffoli’s truth table is
given in Table 1.
| input
|
output |
 |
 |
 |
|
|
|
| 0 |
0
|
0
|
0
|
0
|
0
|
| 0
|
1
|
0
|
0
|
1
|
0 |
| 1
|
0
|
0
|
1
|
0
|
0
|
| 1
|
1
|
0
|
1
|
1
|
1 |
| input
|
output |
| |
|
|
|
|
|
| 0 |
0
|
1
|
0
|
0
|
1 |
| 0
|
1
|
1
|
0
|
1
|
1 |
| 1
|
0
|
1
|
1
|
0
|
1 |
| 1
|
1
|
1
|
1
|
1
|
0 |
Table 1: Toffoli’s
gate.
Fredkin’s [63] reversible 3-bit
gate also uses in addition to a control bit in the following
way: (a) if 
, then the values of are transmitted unaltered,
i.e. the output is the pair 
, (b) if , then the values
of are switched to the
opposite output, i.e. the output is the pair 
. Its truth table is the following:
| input
|
output |
| |
|
|
|
|
|
| 0 |
0
|
0
|
0
|
0
|
0
|
| 0
|
1
|
0
|
0
|
1
|
0 |
| 1
|
0
|
0
|
1
|
0
|
0
|
| 1
|
1
|
0
|
1
|
1
|
0 |
| input
|
output |
| |
|
|
|
|
|
| 0 |
0
|
1
|
0
|
0
|
1 |
| 0
|
1
|
1
|
1
|
0
|
1 |
| 1
|
0
|
1
|
0
|
1
|
1 |
| 1
|
1
|
1
|
1
|
1
|
1 |
Table 2: Fredkin’s
gate.
Fredkin’s gate is universal in the sense that it can be used to construct
reversible variants of all Boolean gates, and satisfies one additional requirement:
the number of 1s and 0s never changes. (Toffoli’s gate does not satisfy this
condition; for example, 
is transformed into 
.) It
is not difficult to show that the gates NOT and AND can be represented using
Fredkin’s gate FREDKIN with particular inputs:
 |
(3) |
and
 |
(4) |
so FREDKIN is universal.
Fredkin’s gate has often been used for photon based gates where a 1 represents
a photon and a 0 simply denotes the absence of a photon; nonlinear optics
is used to control the output of an interferometer (see Milburn [101]). The number
of 1s cannot change as the number of photons cannot change – absorption is
not allowed for reversible gates.
In both formulae (3) and (4) there are more outputs than are required
for the computed functions (one for NOT and two for AND): these outputs,
called garbage bits, are a necessary consequence of reversible logic.
Consequently, one may wonder whether we have only postponed the energy cost;
garbage bits can be irreversibly erased, but that would require to pay Landauer’s
price …
Bennett [11] found in 1973 that any computation
can be performed using only reversible steps, and so “in principle" requires
no dissipation and no power expenditure: we do not need to erase the garbage bits! By pointing out that a reversible computer can run
forward to the end of a computation, print out a copy of the answer (a logically
reversible operation) and then reverse all of its steps to return to its
initial configuration, Bennett invented a procedure to remove the garbage
without any energy cost. Consequently, in principle, we need not pay any
“power bill" to compute reversibly. The moral we draw from the above discussion
is, once again, that, to use Landauer’s [84] words, information is inevitably physical. So, let us explore what physics, especially quantum
physics, has to tell us about information.
Here 
is the logarithm in base 2.
2Here k is Boltzmann’sconstant.
Recall that 
is
1 only if 
and 
have different values, i.e. 
or 
.
A single NAND gate is as good as having both
AND and NOT: 
NAND
, AND
NAND 
NAND
NAND
.
