%======================================================================
% physcomp.tex - Physical limits on computation
%======================================================================

\chapter{Physical constraints on computation}
\label{ch:physcomp}
% Should this be broken into 2 chapters, 1 on physical constraints
% and the other on quantum computing?

\def\draftid{$\ $Id: physcomp.tex,v 1.5.2.5.2.5 1999/05/14 21:10:27 mpf Exp $\ $}

In this chapter we briefly review some of the important fundamental
constraints that physical law places on computational capabilities.  These
constraints will serve as the basis for the arguments in
chapter~{\ref{ch:scaling}}, which will establish that reversible models are
necessary for permitting the maximum possible computational power in the
limiting technology.

Most of existing computer science theory today deals not with physics, but
with abstract realms of pure mathematics, exploring a plethora of different
models of computation having wildly varying capabilities.  Sometimes these
theoretical models have capabilities substantially different from those of
physics as we know it.

But real-world computers are physical devices, and their ultimate potential
capabilities are defined not by some arbitrarily-chosen model, but rather
by the hard facts of physical law.  Unfortunately, physics is not yet
completely understood (witness the lack of an accepted unification of
quantum mechanics with general relativity), and even those parts that
{\emph{are}} well understood are not usually described in terms that
facilitate the use of physics itself as a model of computation.

However, physics does constrain information processing in a number of
important ways that can already be identified with fairly high confidence.

\section{Propagation speed limits}
\label{sec:lightspeed}

The most obvious physical limit important to information processing is the
lightspeed bound for the speed at which information may propagate through
space.

Physical dynamics, as currently understood, proceeds purely through
{\emph{local}} interactions; there is no ``action at a distance.''  Even
gravity, thought by Newton to be an instantaneous force, is now understood,
in the context of general relativity, to propagate through space at only
the speed of light, $c\approx3\times10^8\:\meter/\second$.

Even the quantum-mechanical systems that are sometimes interpreted as
demonstrating ``spooky action at a distance'' (such as separated EPR
pairs), can be explained instead in terms of local interactions.  Quantum
dynamics is based on an ``amplitude function'' which is a function of the
global state of a system (the whole universe if you like).  This leads to a
statistical behavior that may at first {\emph{appear}} to require nonlocal
interactions, but the wavefunction actually evolves over time through a
transformation (the Hamiltonian) that can be expressed as a composition of
interaction terms that are entirely spatially local.

In general, due to the locality of underlying physical law, {\emph{all}}
influences are restricted to traveling, at most, at the speed of light.
Thus, the physical transmission of information in a computer is limited to
this speed as well.

This bound is ``tight'' in the sense that it is, of course, already
achieved in practice in our ubiquitous telecommunication systems, and in
optical interconnection networks in some computers.  Signals in typical
electrical transmission lines travel a bit slower, about half the speed of
light.  But propagation times are still linear in the distance traveled.

One important exception is that signals in low-inductance, resistive wires
(such as the wires on integrated circuit chips) do not actually travel at
constant speed, but rather, for long wires, require propagation time that
is proportional to the {\em{square}} of the length $\ell$ of the wire, in
accordance with the diffusion equation.  This unfavorable scaling presents
problems in integrated circuit design today.  However, even with current
technology, this $\ell^2$ scaling is not inevitable, but can be avoided
through simple schemes such as periodic re-buffering of the signal.

\section{Information density limits}
\label{sec:Sdensity}

Another important constraint for computation results from physical limits
on the amount of information that can be stored within a given volume of
space (such as memory in a computer).  We can say with confidence that some
such bounds do exist, but unfortunately their exact value is hard to
determine.  However, these bounds will be very important in our later
arguments about the advantages of reversibility, so we will now take some
time to look at the various possible answers in some detail.

Fundamental quantum mechanics appears to dictate a particular finite upper
bound on the total amount of information (including entropy) that can be
contained in any system, as a function of the system's physical volume and
the amount of energy it contains.  By the amount of information in a
system, we mean simply the logarithm of the number of states that the
system could occupy, given some definition of what constitutes ``the
system.''  (See {\S\ref{sec:entropy}}.)  According to Margolus (1996,
{\cite{MargLev96}}),
\begin{quote}
[The question of the number of states] is really a very old question: the
correct counting of physical states is the problem that led to the
introduction of Planck's constant into physics {\cite{Planck-14}}, and is
the basis of all of quantum statistical mechanics.  The question can be
answered by a detailed quantum mechanical counting of distinct (mutually
orthogonal) states.  It can also be well approximated in the macroscopic
limit {\cite{Huang-63,Wang-86}} by simply calculating the volume of phase
space accessible to the system, in units where Planck's constant is 1.
\end{quote}

Let us look at some particular information density bounds in more detail.

\subsection{Entropy bounds from black hole physics.}
\label{sec:blackhole}

Some particular upper bounds on information content as a function of system
size and energy are given by Bekenstein (1984, {\cite{Bek84}}) and by Joos
and Qadir (1992, {\cite{JQ92}}).  Bekenstein's bounds, which originally
came out of his studies of the entropy of black holes ({\emph{e.g.}},
{\cite{Bek81}}), are fairly loose, in the sense that his bounds may
conceivably be much higher than the maximum information content for systems
{\emph{other}} than black holes.  One bound Bekenstein gives (\cite{Bek84},
eq.~1) is:
\begin{equation}
S < 2\pi ER/\hbar c, \label{eq:S-vs-ER}
\end{equation}
where $S$ is the capacity for entropy or information (in natural log units
or {\defn{nats}}), $E$ is the total energy (including rest mass-energy) in
a system, and $R$ is the radius of the system.  In black holes, the
mass-energy scales in proportion to the radius, so the entropy in
Bekenstein's bound scales in proportion to the hole's surface area.  The
entropy is thought to perhaps reside in the form of quantum fluctuations at
the hole's event horizon.

If this is indeed the case, the information density at the event horizon is
truly enormous: 1/4 nat of entropy for each square of area that is 1 Planck
length, or $\ell_{\rm P} = \sqrt{G\hbar/c^3} = 1.62\times 10^{-35}\:{\rm
m}$, on a side.  That is, an astounding $2.21\times 10^{70}$ bits per square
meter, or $2.21\times 10^{50}$ bits per square {\AA}ngstrom (roughly
atom-size) area.  (It's probably safe to say that DRAM densities won't
reach {\emph{that}} level for a while!)

In any case, black holes are certainly not a very good place to store
information that we might want to retrieve later, although they might
conceivably be a good place to dump unwanted entropy.  Macroscopic black
holes have intrinsic temperatures near absolute zero, and in contrast to
most systems, they get {\emph{cooler}} as you dump more energy and entropy
into them!  ({\textit{Cf.}} eq.~26 in Smith's paper {\cite{SmithWD-95}},
and his references to Hawking, his source.)  So a black hole would be a
sort of natural heat sink, cooler even than the cosmic microwave background
which is at {\about}3 K.  But for the foreseeable future, black holes will
remain rather hard to come by, so it behooves us to also consider where we
stand without them.

\subsection{Entropy bounds for a photon gas.}
Much tighter bounds can be given for the entropy of normal (non black-hole)
systems, given additional assumptions about their composition.  This is
done in Bekenstein's paper {\cite{Bek84}}, as well as in papers by Joos and
Qadir {\cite{JQ92}} and Smith (1995 {\cite{SmithWD-95}}) and the related
literature.  Smith argues that for high-temperature systems (above 1000 K
or so, roughly the melting point of ordinary solids), the maximum entropy
density for a {\emph{given mass density}} is approximately achieved (within
a small constant factor) by a thermal photon gas, in which the entropy
density (entropy per unit volume) is (\cite{SmithWD-95}, eq.~22)
\begin{equation}
\frac{S}{\volume} = \frac{16\sqrt{\pi}}{3\cdot 60^{1/4}}\left(\frac{c}{\hbar}\cdot\frac{M}{\volume}\right)^{3/4} \label{eq:rhoS-vs-rhoM}
\end{equation}
where $M/\volume$ is the energy density of the photon gas, in mass units.  

This equation would appear to allow arbitrarily high entropy densities to
be achieved by raising the temperature and mass-energy density, except that
actually of course the energy density is itself limited as a function of a
system's size, since beyond a certain point the system would form a black
hole.  So even with~\eqref{eq:rhoS-vs-rhoM}, entropy density is still
limited for a system of given size.

\subsection{Entropy bounds at normal temperatures/pressures.}

Another problem with {\eqref{eq:rhoS-vs-rhoM}} is that it would in general
require extremely high temperatures in order to reach the maximum entropy
density for a given mass density.

At ordinary temperatures and pressures, the entropy density of light is
rather low, and we conjecture that the maximum entropy might instead be
achieved by some sort of normal atomic material.

If each atom has enough energy to jiggle around a little, it will have on
average $\kT$ energy (corresponding to 1 nat of entropy) per vibrational
degree of freedom.  For three-dimensional vibrations, there are six degrees
of freedom, three of position and three of momentum, so this gives $6\;{\rm
nats}/\ln 2\approx 8.66\;{\rm bits}$ per atom.  There should also be small
entropy contributions from variability in the nuclear spin orientation, and
from electrons that are free to roam in molecular orbitals or in conduction
bands.  But most atoms are somewhat larger than $1\units{\Ang}$$^3$ in
volume, so $1$--$10\:{\rm bit}/\Ang$$^3$ is still probably the right
overall order of magnitude for entropy density in normal materials.

Table {\ref{tbl:rhoS}} summarizes the above discussion by giving the
average entropy density of a sphere of radius 1 meter that contains the
maximum entropy according to various bounds.  (Keep in mind that entropy
actually scales less rapidly than volume for the systems near black-hole
mass, due to Bekenstein's bound.)

\begin{table}
\centerline{\begin{tabular}{|l|c|l|}
\hline
Material & \begin{minipage}{5in}\begin{tabbing}
		Upper bound on\\
		entropy density\end{tabbing}\end{minipage} & Caveats \\
\hline
Black hole & $\e{4.14}{39}\:\bit/\Ang$$^3$ & Need mass $\approx$ Saturn; can't get info.\ out \\
Non-black hole & $\e{1.53}{22}\:\bit/\Ang$$^3$ & Requires
nearly as much mass \\
Normal density & $\sim \e{3}{5}\:\bit/\Ang$$^3$ & May require billion-degree temperatures\\
Atomic matter & $\sim 1\mbox{--}10\:\bit/\Ang$$^3$ & Hand-waving estimate.\\
\hline
\end{tabular}}
\caption[Limits on entropy density from various analyses]{Theoretical
limits on entropy or information density for a 1-meter-radius sphere, in
various scenarios.  The radius is important because in the high-gravity
regime, the maximum average entropy density decreases with increasing size.
It is difficult to know which of these limits, if any, might someday be
achievable for use in computational systems.}\label{tbl:rhoS}
\vskip\parsep
\hrule
\end{table}

This concludes our discussion of information density limits.  Although we
were unable to determine precisely the maximum density that was possible,
we saw that entropy density does appear to ultimately be limited by some
function of energy density, such as in eq.~({\ref{eq:rhoS-vs-rhoM}}).
Furthermore, much of a system's rest mass-energy may not count for purposes
of this calculation, if it is energy that is tied up in an inaccessible
nucleus, for example.  At this stage I believe it would be premature to
predict that a density greater than say $\sim 10$ bits per cubic
\AA ngstrom could ever actually be achieved for stable, retrievable storage
of information.  I would need more information before I could make a
similar statement regarding achievable thermal entropy densities.

\section{Information flux rate limits}
\label{sec:fluxlim}

Another physical quantity of importance in computation is the maximum flux
(rate of flow per unit area) of information or entropy through any surface
in the computer.  We should point out that one class of bounds on this
quantity immediately follows from the bounds of sections
{\ref{sec:lightspeed}} \& {\ref{sec:Sdensity}}, as follows.

Suppose a material having entropy density $\sdens$ passes through of
surface at velocity $v$.  Then the entropy in that material is crossing the
surface with exactly the flux $\sflux=\sdens v$.  Section
{\ref{sec:Sdensity}} gave us bounds on the maximum value of $\sdens$, and
the maximum $v$ is of course $c$, so this leads immediately to
corresponding bounds on $\sflux$.  A relativistic analysis shows that the
scaling of entropy density with energy density doesn't improve as one nears
the speed of light, so this flux bound holds even at relativistic speeds.

Smith 1995 {\cite{SmithWD-95}}, p.~6, eq.~7 gives an explicit formula for
the maximum entropy flux $\sflux$ using light, given an energy flux $\eflux$:
\begin{equation}
\sflux\leq\frac{4}{3}\oSB^{1/4}\eflux^{3/4}\label{eq:FS-vs-FE}
\end{equation}
This is the formula for the entropy flux emitted by a blackbody that is at
the appropriate temperature to emit energy flux $\eflux$.  As Smith points
out, there is a simple proof that this is the maximum entropy flux that can
be transmitted with photons given that energy flux.  Imagine using photons
to continuously transmit energy and entropy through a small aperture into
an insulated box (a perfect blackbody).  The interior of the box will heat
up, and, at equilibrium, will radiate energy out of the aperture exactly as
fast as it is coming in (since energy is conserved), and will also radiate
entropy out {\emph{at least}} as fast as it comes in (since global entropy
cannot decrease).  Therefore the entropy flux of the thermal blackbody
radiation coming out of the box upper-bounds the achievable entropy flux of
the light coming in, which may be of any form (coherent, {\etc}).

At this point we could go on to calculate upper bounds on information flux
at {\emph{any}} energy based on the black hole limits to entropy density
that we discussed in {\S\ref{sec:Sdensity}}.  For example, for a postulated
minimum-size (Planck-length scale) black hole moving at near the speed of
light, we estimate entropy flux would be around $10^{109}\:{\rm bit}/{\rm
s}\mbox{-}{\rm cm}^2$.  However, this sort of bound is rather far from
anything meaningful, since it does not represent a sustainable rate, or a
rate achievable over an area much larger than a Planck length---black holes
placed near each other would rapidly conglomerate into a larger black hole
with lower entropy density.  Even if we were so bold as to allow for the
use of such exotic objects as black holes as computer components, properly
accounting for gravitational effects in such systems would make our scaling
analysis of chapter~\ref{ch:scaling} much more complex.  So instead, for
the rest of the thesis, we will ignore high-gravity situations, and instead
focus only on the bounds obtained for normal matter.

\section{Computation rate limits}
\label{sec:Margolus-bound}

In chapter~\ref{ch:scaling} we will examine in detail how certain kinds of
limits on computation rates for irreversible and imperfectly-reversible
computers can be derived from the limits on information flux we saw in
{\S\ref{sec:fluxlim}}.  However, there are other limits on processing rates
that apply even to perfectly reversible computers.

In particular, there is the result of Margolus and Levitin (1996,
{\cite{MargLev96}}) that the fundamental laws of quantum mechanics imply
that the maximum rate $\nu_\perp$ at which a system at an average energy
$E$ (above some minimum energy $E_0$) can transition between
distinguishable ({\foreign{i.e.}}, orthogonal) states is
\begin{equation}
\orthrate\leq4(E-\lowestE)/h.\label{eq:marglev}
\end{equation}
This bound is derived in a totally general way, and applies even for
systems traveling at relativistic velocities.  Insofar as any computational
operation requires that some part of a system change from one distinct
state to another, Margolus and Levitin's bound is an absolute upper limit
on the rate at which operations can be performed within a computer.

Further, Margolus suggests [personal communication] that for systems in
which not all the system's energy is accessible for computational purposes
(for example, if some of it is in the form of heat, or tied up in rest
mass), it is the {\emph{free energy}} of the system, rather than its total
energy, that determines the maximum rate at which the system can transition
between useful computational states according to eq.~\eqref{eq:marglev}.

As a simple example, a single electron excited to a potential of 1 Volt
above its ground state contains 1 eV of accessible energy and thus can
never perform computational steps (or any state change) more rapidly than
at a rate of $4\units{\eV/h} = \e{9.67}{14}\;\Hz$, or about once per
femtosecond.

\section{Reversibility of physics}
\label{sec:revphys}

Another physical constraint of great importance for computation is that all
physical dynamics is reversible (invertible), that is, it is deterministic
looking backwards in time.  (See figure~\ref{fig:determ}.)

\begin{figure}
\centerline{\psfig{file=determ.epsi,width=4in}}
\caption[Forward and reverse determinism]{Forward and reverse determinism
in physics.  Normal forward determinism means that a single state cannot
evolve to become one of two different states at any single later time, and
similarly, reverse determinism or just {\emph{reversibility}} means that
two initially-distinct states cannot evolve to become the {\emph{same}}
state at some later time.  Physics is both forward and reverse
deterministic, and so the possible trajectories of a system through
configuration space-time never intersect.}
\label{fig:determ}
\vspace{.1in}
\hrule
\end{figure}

Quantum mechanics is sometimes described in nondeterministic terms, but it
is actually perfectly deterministic (and reversible) at the level of the
evolution of the quantum wave function.  The apparent nondeterminism of
quantum events can be interpreted as merely a subjective, emergent
phenomenon that is predicted perfectly well by the underlying deterministic
theory {\cite{Everett-73}}.

One possible exception to reversibility may be black holes, which, in some
theoretical arguments, are found to destroy information (see Preskill 1992
{\cite{Preskill-92}} for a review of the situation).  However, there is
currently no accepted, complete theory of black hole physics from which we
could draw indisputable theoretical conclusions, and there is no
experimental evidence that supports information loss.  The truth of the
issue is still being actively debated (\eg,
{\cite{Englert-97,Mashkevich-97}}).  Moreover, it appears that some recent
developments in string theory would allow reversibility to be maintained,
if the theory is correct (Myers 1997, {\cite{Myers-97}}).

In any case, it seems to be the general consensus among physicists that
reversibility is certainly maintained in at least all areas of mechanics
that do not involve extreme situations such as black holes.  So regardless
of the black hole situation, physics remains reversible for all practical
purposes.

\subsection{Physical reversibility and information erasure}
\label{sec:reverase}

Another way of characterizing physical reversibility is that two states (of
a classical system, or of a quantum wavefunction) that are initially
distinct can never evolve to become the {\emph{same}} state at some later
time.  Thus the number of possible states of a system is irreducible over
time.  A popular way of expressing this is with the slogan, ``state space
is incompressible.''

The incompressibility of state space has an important consequence for
information erasure within a computer, first described explicitly by
Landauer {\cite{Landauer-61}}.  Whenever we attempt to irreversibly erase a
piece of information from a computer, that information is not truly
destroyed, but instead is simply {\emph{transferred}} to another part of
the system, typically to the uncontrolled thermal state of the computer and
its environment.  We explain in more detail with reference to
figure~\ref{fig:erase}.

\begin{fig}
\psfig{file=erase2.epsi,width=\textwidth}
\caption[Information ``erasure'' under reversible physics]{Information
``erasure'' under reversible physics.  In order to erase an unknown bit and
thereby reduce the number of possible digital states of the computer by a
factor of 2, one has to make up for this by increasing the number of
possible thermal states of the rest of the system by a factor of 2.}
\label{fig:erase}
\end{fig}

The figure illustrates a 1-bit piece of computational state within a
computer.  We wish to perform an ``erasure'' operation, which we may
characterize as an operation that transforms that bit to a zero regardless
of whether it was originally a 0 or a 1.

In addition to the bit in question, the computer also contains some amount
of other information in the form of other bits in memory, together with the
entropy of its thermal state.  Let $\nstates$ denote the number of possible
states of the system, apart from the bit in question.

We want our ``erase'' operation to operate correctly, independently of
which of the $2\nstates$ possible states the combined system is in.  Due to
physical reversibility, each of these $2\nstates$ states must be mapped to
a distinct state after the erase operation---but all of those states have
value 0 in the erased bit.  Thus there must be $2\nstates$ possible states
of the rest of the system, after the operation.  The amount of information
in the rest of the system has therefore increased by
$\lg2\nstates-\lg\nstates=1\:{\rm bit}$.

So the presumably erased information has not really been destroyed, but is
still present somewhere, either in some other part of the computational
state or in the thermal state.  The original value of the bit could
{\emph{in principle}} be retrieved by, for example, running the laws of
physics backwards.

However, if the information has been lost in a sea of thermal chaos, then
{\emph{in practice}} there is {\emph{no}} way to reconstruct the original
value of the bit.

\subsection{Reversibility, entropy, and the second law}
\label{sec:entropy}

We now see how physical reversibility can be understood to imply the second
law of thermodynamics.

The second law of thermodynamics states that the total entropy of any
closed system cannot decrease.  What is entropy?  Quantitatively, it is the
logarithm of the number $\nstates$ of possible states of a system.  The
base of the logarithm determines the unit of entropy: if the base is
$e\approx2.718\ldots$, the base of natural logarithms, then we might call
the corresponding unit of entropy 1~{\defn{nat}}, equal to Boltzmann's
constant {\kB}.  If the base is 2, then the unit of entropy is called 1
{\defn{bit}}.  Thus, $1\;{\rm bit}=(\ln2)\;{\rm nat}\approx0.693\;\nat$.

If entropy is the log of the number of possible states, what, then, do we
mean by a ``possible state?''  This depends entirely on the context,
specifically on how we define what constitutes a legal example of ``the
system'' in question.

However, even with this broad definition of entropy, we can already make
some meaningful statements about entropy in connection with reversibility.
First, it is clear that if the entropy of a system were to decrease over
time, then the system would not be reversible, because we would have an
example of multiple possible initial states evolving to become a smaller
number of resulting final states, violating the incompressibility of state
space that is implied by reversibility.  Therefore, the reversibility of a
system immediately implies that its entropy can never decrease over time.

There is a similar connection between entropy increase and determinism.  In
a deterministic system, state space is ``inexpandable'' since a given state
can not evolve to more than one possible new state in a given amount of
time.  Thus the number of possible states cannot increase, in this strict
sense, and so deterministic systems undergo no ``true'' increases in
entropy.

However, even if a system is deterministic, we may find it convenient to
label more and more states as ``possible'' over a system's time evolution,
simply because, given an incomplete model of a system's initial state, we
may lose track of the exact trajectories of the initially possible states
over time, and so many additional states may become possible over time from
the point of view of the model.  In such circumstances, it is convenient to
say that entropy increases.  An example is the situation in
{\mbox{figure~\ref{fig:erase}}} (p.~\pageref{fig:erase}).  Suppose we have
constructed an initial condition in which only the ``1'' value of the bit
is possible, so the entropy before the ``erase'' operation is just
$\ln\nstates$.  But since we fail to model what becomes of the information
{\emph{that}} the bit is 1 after the ``erase'' operation is performed, the
entropy of the system under the model increases to $\ln2\nstates$.  This
increase will happen whenever a non-entropy bit turns into thermal form,
because the evolution of the micro-state of a thermal system is, by
definition, un-trackable by us.

We thus can state the following principle: Total entropy increases
(permanently) by at least 1 bit's worth any time a bit that is originally
non-entropic moves to reside in a thermal system.  Furthermore, this
happens whenever a digital bit is erased, unless (a)~the bit was
{\emph{already}} entropy, in which case moving it to thermal form does not
necessarily increase total entropy, or (b)~the bit is canceled out instead,
by un-computing it from other bits of state with which it is correlated.

\subsection{Entropy and energy}
\label{sec:SandE}

As we just saw, the second law of thermodynamics states that the entropy of
a closed system cannot decrease over time.  We saw that it also cannot
increase, except in the sense that our incomplete model of the system may
lose track of what happens to a state over time, so that more states become
``possible'' from the point of view of the model.  However, entropy
{\emph{can}} be moved from one subsystem to another.

Correspondingly, the {\emph{first}} law of thermodynamics states that the
{\emph{energy}} of a closed system can neither increase nor decrease, but
can only be moved from one subsystem to another.

How are these conservation laws for energy and entropy related?  We find
empirically that in order to increase or decrease the entropy of any
subsystem (not counting increases due to deficiencies in our model), we
generally must also increase or decrease its energy (given a closed,
constant-volume system).  For sufficiently small changes in entropy, we
find that the change in energy required is proportional to the change in
entropy.  The constant of proportionality is called the
{\defn{temperature}} $T$ of the subsystem.  Formally,
\begin{equation}
T = \partial E/\partial S.
\end{equation}
This is a perfectly valid definition of temperature, in terms of the
relation between a system's energy and its number of states.

Under this definition, 1 Kelvin of absolute temperature is definable as a
requirement of {\mbox{$\approx\e{1.38}{-23}\;\Joule$}} of energy per 1-nat
increase in entropy.  A nat of entropy can therefore also be expressed in
units of energy per unit temperature, such as
$\e{1.38}{-23}\;\Joule/\Kelvin$.  In such form, 1 nat of entropy is often
referred to as {\defn{Boltzmann's constant}} $\kB$.

From all this, it follows immediately that the amount of energy $E$ that
must be added to system in order to double its number of possible states is
just
\begin{equation}
E = \kB T\ln 2
\end{equation}
since $\kB\ln 2$ is just a 1-bit increase in entropy, and multiplying by
the system's temperature just converts this entropy increase to the
required change in energy, by the definition of temperature.

\subsection{Logical irreversibility and energy dissipation}
\label{sec:ktdiss}

We saw in section~\ref{sec:Sdensity} that in any system with particular
size and energy there is a consequent upper bound on the entropy that
system can contain.  If a given system is found to contain less entropy
than the maximum given the amount of energy in the system, then that must
mean our model of the system is imposing further structure on the system,
ruling out some of the states that would otherwise be possible.

For such a system with non-maximal entropy, only a portion of the energy of
the system is actually needed for permitting the entropy that is actually
present.  This portion of the total energy will be referred to as the
amount of {\defn{dissipated energy}} in the system.  The rest of the
system's energy will be referred to as its {\defn{free energy}}.  The
difference between the entropy of the system and its maximum entropy will
be termed the {\defn{negentropy}} or {\defn{information capacity}} of the
system.  Some of this information capacity may become allocated for storing
computational information.  (See fig.~\ref{fig:entropy}.)

\begin{fig}
\centerline{\psfig{file=entropy.epsi,width=0.75\textwidth}}
\caption[Venn diagram of entropy and information]
{Venn diagram of entropy and information.  Any system of finite size and
energy has a finite maximum entropy; however, if the system expands without
bound, the maximum entropy may also.  The maximum entropy may be considered
the total amount of information of all kinds in the system.  However, much
of it may be redundant and cross-correlated.  Bits of information that are
uncorrelated, or whose correlations have become lost beyond all hope of
recovery, are entropy, which can only increase in a reversible universe.
Some portion of the system, and the information in it, is within our
ability to manipulate and control, such as bits within a computer.  These
bits, too, may either be entropy or not, depending on our ability to know
their correlations.}
\label{fig:entropy}
\end{fig}

As we discussed in {\S\ref{sec:entropy}}, even in the context of a
perfectly deterministic underlying physics, the entropy of a system can be
seen to increase, through a failure to completely model the determinism
inherent in the system's physical evolution.  When this happens, the amount
of the system's energy that is needed to support this entropy will increase
by some amount, and the free energy will decrease by the same amount.  We
say this amount of energy has been {\defn{dissipated}}.

We are now in a position to accurately state and explain the central
statement on which the field of reversible computing is based:

\paragraph{Landauer's principle.}
{\emph{The irreversible loss of 1 bit of computational information requires
the dissipation of $\kB T\ln 2$ energy}}, where $T$ is the temperature of
the subsystem in which the lost bit finally ends up.  By the ``irreversible
loss,'' we mean that some bit of {\emph{computational information}} (not a
bit that is already entropy!) becomes transformed in such a way that our
computational models can not track it, for example by becoming mixed up
with parts of the system whose state is already {\defn{thermal}}, or
unknown.  Thus by definition the bit has become entropy, and the entropy of
the system as a whole is increased by 1 bit.  This increase is eventually
reflected in some subsystem at temperature $T$, and by definition of
temperature, the energy of this subsystem must be increased by $\kB T\ln
2$.  The energy invested in the entropy increase is heat.  If $T$ is the
lowest available temperature, then this energy must come out of the free
energy, because all the dissipated energy in the system is already fully
occupied with containing the pre-existing entropy.  Thus the free energy is
decreased by $\kB T\ln 2$.

The above principle was first explicitly conjectured by Landauer
{\cite{Landauer-61}}.

\noheading
Note that since $T$ is the temperature of the system where the entropy
finally ends up, not the temperature of the device that held the entropy
originally, cooling a computer cannot in the long run decrease the total
energy dissipation required to erase bits, if the dissipation in the
cooling system is taken into account.  The entropy that is generated can
not build up indefinitely in the cooling system, or else it would not stay
cool.  Instead, it ultimately ends up in some natural thermal reservoir in
the environment.  The coolest thermal reservoir of effectively unlimited
capacity that might be available in the foreseeable future is the
interstellar microwave background, at a temperature of \mbox{\about 2.73
K}.  Thus, no process that generates entropy can, in the long run, sustain
an energy dissipation cost less than
$\kB(2.73\:\Kelvin)\ln2\approx\e{2.6}{-23}\;\Joule$ per bit generated, and
this can only be attained if the entropy can be transmitted directly into
space.  For earthly systems that use the atmosphere as their thermal
reservoir, the relevant temperature is in the neighborhood of room
temperature or 300 K, for a minimum energy dissipation of
$\sim\e{3}{-21}\;\Joule/\bit$.

\section{Quantum computation}
\label{sec:qc}

One area in which physics may actually constrain computation {\emph{less}}
than might be expected is in the possibility of quantum computation (\cf\
{\cite{Feynman-85,Deutsch-Jozsa-91,Berthiaume-Brassard-92a,Berthiaume-Brassard-92b,Bernstein-Vazirani-93,Simon-94,Shor-94}}),
that is, computation using large, complex, coherent superpositions of
states.  If it can be implemented successfully, quantum computation seems
likely to be strictly asymptotically faster than classical computation on
certain problems, by as much as an exponential factor.  But it is not yet
known if quantum computation would be beneficial for purposes other than
obsoleting the RSA cryptosystem, or simulating physical quantum systems.
Still, if the recent progress on implementing quantum computers
{\cite{Pellizzari-et-al-95,Turchette-et-al,Cirac-Zoller-95,Cory-etal-96,Gershenfeld-Chuang-97,Cory-etal-98,Teich-et-al-88,DiVincenzo-95a,Sleator-Weinfurter-95,Barenco-et-al-95b,Chuang-Yamamoto-95}}
eventually culminates in success, then we would certainly like to consider
quantum computation as a physically possible means of computation.  But
even a quantum computer would still need to obey the fundamental
constraints discussed above affecting the maximum density and propagation
speed of information.

\section{Physical constraints---conclusion}

This concludes our discussion of fundamental physical limits on
computation.  Table~\ref{tbl:phsum} summarizes the limits we discussed, and
the presumed effect on the form of a physically-realistic model of
computation, which we will discuss further in ch.~\ref{ch:ultimate}.

\begin{table}
\centerline{\begin{tabular}{|l|l|c|l|l|}
\hline
{\bf Fundamental}& {\bf Constrained}	& 		& {\bf Quantitative}				& {\bf Impact on}          \\
{\bf principle}	& {\bf quantity}	& {\bf Symbol}	& {\bf constraint}				& {\bf our model}          \\
\hline\hline %=================================================================================================================
Quantum		& Entropy		& $\sdens$	& $\lesssim$ 1--10 {$\bit/\Ang$}{$^3$}?	& Finite state/      \\	
mechanics	& density	 	&		&						& processor	     \\
		\cline{2-5} %-------------------------------------------------------------------------------------------------
		& Entropy flux		& $\sflux$	& $\leq\sdens v$				& Finite info.	     \\
		&			&		&						& flux		     \\
		\cline{2-5} %-------------------------------------------------------------------------------------------------
		& Rate of state		& $\orthrate$   & $\leq 4(E-\lowestE)/h$			& Finite oper.	     \\
		& change		& 		& 						& frequency	     \\
\hline %-----------------------------------------------------------------------------------------------------------------------
Locality	& Info. prop.		& $v$		& $\leq c\approx\e{3}{8}\units{m/s}$		& Mesh arch.         \\
		& velocity		&		&						& (Vit\'anyi '88)    \\
\hline %-----------------------------------------------------------------------------------------------------------------------
3-dimensionality& Connec-		&               & $\Atmost(t^3)$				& 3-D mesh	     \\
of space        & tivity             	&		&						&		     \\
\hline %-----------------------------------------------------------------------------------------------------------------------
Micro-		& Entropy		& $\Delta S$	& $\geq 0$ always,				& Logical  \\
reversibility,	& change		& 		& $\geq
1\units{bit}$/bit erasure				& reversibility,     \\
		\cline{2-4} %---------------------------------------------------------------------------
thermodynamics	& Energy		& $\Delta E$	& $\geq 0$ always,				& entropy	     \\
		& dissipation		&		& $\geq \kB T\ln 2$/eras.			& accounting	     \\
\hline %-----------------------------------------------------------------------------------------------------------------------
Frictional	& Entropy		& $\entco$	& $>0\units{b/Hz}$?				& Time-prop.	     \\
effects		& coefficient		&		&						& reversibility	     \\
\hline %-----------------------------------------------------------------------------------------------------------------------
\end{tabular}}
\caption[Physical constraints on computation]{Fundamental physical
constraints on computation, and their effects on the form of a
physically-realistic model of computation.  The value of the bound on
$\sdens$ is very uncertain, but the assertion that some such bound exists
is not.  For any particular computing technology through the foreseeable
future, there will generally be much stricter limits than the above on most
of these quantities.}
\label{tbl:phsum}
\vskip\parsep
\hrule
\end{table}

In chapter~\ref{ch:scaling} we will see how these limits affect the scaling
of computation speeds in reversible and irreversible computers.  But first,
in the next chapter, we review the non-physical theoretical underpinnings
of reversible computing, and show that in an imagined non-physical
computational framework, reversibility leads to unfavorable scaling.  The
contrast between that result and the results of chapter~\ref{ch:scaling}
underscores that traditional non-physical theoretical frameworks for
computation are inadequate for realistically modeling the advantages of
reversibility, and thus, more sophisticated models of computation that take
the above-described physical constraints into account are required for a
correct analysis.  Such models will be discussed in
chapter~\ref{ch:ultimate}.

\cleardoublepage
