Chapter 2

Physical constraints on computation

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 5, 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 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.

2.1 Propagation speed limits

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 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 ≈ 3 × 10^{8} m/s.

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 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, 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 square of the length ℓ 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 ℓ^{2} scaling is not inevitable, but can be avoided through simple schemes such as periodic re-buffering of the signal.

2.2 Information density limits

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 §2.5.2.) According to Margolus (1996, [96]),

[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 [112], 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 [72, 155] by simply calculating the volume of phase space accessible to the system, in units where Planck’s constant is 1.

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

2.2.1 Entropy bounds from black hole physics.

Some particular upper bounds on information content as a function of system size and energy are given by Bekenstein (1984, [15]) and by Joos and Qadir (1992, [73]). Bekenstein’s bounds, which originally came out of his studies of the entropy of black holes (e.g., [14]), are fairly loose, in the sense that his bounds may conceivably be much higher than the maximum information content for systems other than black holes. One bound Bekenstein gives ([15], eq. 1) is:

S < 2πER/ℏc,  (2.1)

where S is the capacity for entropy or information (in natural log units or 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 ℓ_{P} = \sqrt{Gℏ/c^{3}} = 1.62 × 10^{−35} m, on a side. That is, an astounding 2.21 × 10^{70} bits per square meter, or 2.21 × 10^{50} bits per square Ångstrom (roughly atom-size) area. (It’s probably safe to say that DRAM densities won’t reach 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 cooler as you dump more energy and entropy into them! (Cf. eq. 26 in Smith’s paper [126], 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 ∼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.

2.2.2 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 [15], as well as in papers by Joos and Qadir [73] and Smith (1995 [126]) 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 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 ([126], eq. 22)

\frac{S}{V} = \frac{16\sqrt{π}}{3 · 60^{1/4}} (\frac{c}{ℏ} · \frac{M}{V} )^{3/4}  (2.2)

where M/V 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 (2.2), entropy density is still limited for a system of given size.

2.2.3 Entropy bounds at normal temperatures/pressures.

Another problem with (2.2) 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 k_{B}T 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 nats/ ln 2 ≈ 8.66 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 Å^{3} in volume, so 1–10 bit/Å^{3} is still probably the right overall order of magnitude for entropy density in normal materials.

Material Upper bound on entropy density

Caveats

Black hole  4.14×10^{39} b/Å^{3} Need mass ≈ Saturn; can’t get info. out
Non-black hole 1.53×10^{22} b/Å^{3} Requires nearly as much mass
Normal density ∼ 3×10^{5} b/Å^{3} May require billion-degree temperatures
Atomic matter  ∼ 1–10 b/Å^{3} Hand-waving estimate.

Table 2.1: 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.

Table 2.1 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.)

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. (2.2). 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 ∼ 10 bits per cubic Å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.

2.3 Information flux rate limits

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 2.1 & 2.2, as follows.

Suppose a material having entropy density ρ_{S} passes through of surface at velocity v. Then the entropy in that material is crossing the surface with exactly the flux F_{S} = ρ_{S}v. Section 2.2 gave us bounds on the maximum value of ρ_{S}, and the maximum v is of course c, so this leads immediately to corresponding bounds on F_{S}. 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 [126], p. 6, eq. 7 gives an explicit formula for the maximum entropy flux F_{S} using light, given an energy flux F_{E}:

F_{S} ≤ \frac{4}{3}σ_{SB}^{1/4}F_{E}^{3/4}  (2.3)

This is the formula for the entropy flux emitted by a blackbody that is at the appropriate temperature to emit energy flux F_{E}. 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 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 any energy based on the black hole limits to entropy density that we discussed in §2.2. 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} bit/s-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 5 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.

2.4 Computation rate limits

In chapter 5 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 §2.3. 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, [96]) that the fundamental laws of quantum mechanics imply that the maximum rate ν_{⊥} at which a system at an average energy E (above some minimum energy E_{0}) can transition between distinguishable (i.e., orthogonal) states is

ν_{⊥} ≤ 4(E − E_{0})/h.  (2.4)

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 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. (2.4).

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 eV/h = 9.67×10^{14} Hz, or about once per femtosecond.

2.5 Reversibility of physics

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 2-1.)

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 [46].

One possible exception to reversibility may be black holes, which, in some theoretical arguments, are found to destroy information (see Preskill 1992 [113] 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 (e.g., [44, 98]). Moreover, it appears that some recent developments in string theory would allow reversibility to be maintained, if the theory is correct (Myers 1997, [106]).

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 Figure 2-1: 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 reversibility means that two initially-distinct states cannot evolve to become the 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. situations such as black holes. So regardless of the black hole situation, physics remains reversible for all practical purposes.

2.5.1 Physical reversibility and information erasure

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 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 [79]. Whenever we attempt to irreversibly erase a piece of information from a computer, that information is not truly destroyed, but instead is simply 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 2-2.

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 N 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 2N possible states the combined system is in. Due to physical reversibility, each of these 2N 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 2N 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 lg 2N − lg N = 1 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 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 in practice there is no way to reconstruct the original value of the bit.

2.5.2 Reversibility, entropy, and the second law

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

Figure 2-2: 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.

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 N of possible states of a system. The base of the logarithm determines the unit of entropy: if the base is e ≈ 2.718 …, the base of natural logarithms, then we might call the corresponding unit of entropy 1 nat, equal to Boltzmann’s constant k_{B}. If the base is 2, then the unit of entropy is called 1 bit. Thus, 1 bit = (ln 2) nat ≈ 0.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 figure 2-2 (p. 40). 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 N. But since we fail to model what becomes of the information that the bit is 1 after the “erase” operation is performed, the entropy of the system under the model increases to ln 2N. 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 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 uncomputing it from other bits of state with which it is correlated.

2.5.3 Entropy and energy

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 can be moved from one subsystem to another.

Correspondingly, the first law of thermodynamics states that the 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 temperature T of the subsystem. Formally,

T = ∂E/∂S.  (2.5)

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 ≈ 1.38×10^{−23} J 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 1.38×10^{−23} J/K. In such form, 1 nat of entropy is often referred to as Boltzmann’s constant k_{B}.

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

E = k_{B}T ln 2  (2.6)

since k_{B} 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.

Figure 2-3: 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.

2.5.4 Logical irreversibility and energy dissipation

We saw in section 2.2 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 dissipated energy in the system. The rest of the system’s energy will be referred to as its free energy. The difference between the entropy of the system and its maximum entropy will be termed the negentropy or information capacity of the system. Some of this information capacity may become allocated for storing computational information. (See fig. 2-3.)

As we discussed in §2.5.2, 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 dissipated.

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

Landauer’s principle. The irreversible loss of 1 bit of computational information requires the dissipation of k_{B}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 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 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 k_{B}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 k_{B}T ln 2.

The above principle was first explicitly conjectured by Landauer [79].

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 ∼2.73 K. Thus, no process that generates entropy can, in the long run, sustain an energy dissipation cost less than k_{B}(2.73 K) ln 2 ≈ 2.6×10^{−23} J 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 ∼ 3×10^{−21} J/b.

2.6 Quantum computation

One area in which physics may actually constrain computation less than might be expected is in the possibility of quantum computation (cf. [48, 39, 22, 21, 20, 123, 121]), 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 [45, 142, 31, 33, 64, 34, 132, 41, 124, 10, 30] 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.

2.7 Physical constraints—conclusion

This concludes our discussion of fundamental physical limits on computation. Table 2.2 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. 4.

In chapter 5 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 5 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 4.

Fundamental Constrained  Quantitative  Impact on
principle  quantity  Symbol constraint  our model
Quantum  Entropy  ρ_{S}  ≲ 1–10 b/Å^{3}?  Finite state/
mechanics  density  processor
Entropy flux  F_{S}  ≤ ρ_{S}v  Finite info.

flux

Rate of state ν_{⊥} ≤ 4(E − E_{0})/h Finite oper.
change  frequency
Locality Info. prop. v ≤ c ≈ 3×10^{8} m/s Mesh arch.
velocity  (Vitányi ’88)
3-dimensionality Connec- O(t^{3}) 3-D mesh
of space  tivity
Micro-  Entropy  ΔS  ≥ 0 always,  Logical
reversibility,  change  ≥ 1 bit/bit erasure reversibility,
thermodynamics Energy  ΔE  ≥ 0 always,  entropy
dissipation  ≥ k_{B}T ln 2/eras.  accounting
Frictional  Entropy  k_{S}  > 0 b/Hz?  Time-prop.
effects  coefficient  reversibility

Table 2.2: Fundamental physical constraints on computation, and their effects on the form of a physically-realistic model of computation. The value of the bound on ρ_{S} 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.