IBM Thomas J. Watson Research Center, Yorktown Heights, New York 10598
International Journal of Theoretical Physics. Vol. 21. Nos. 3/4, 1982
Received May 6, 1981
Reversible computation is briefly reviewed, utilizing a refined version of the Bennett-Fredkin-Turing machine, invoked in an earlier paper. A dissipationless classical version of this machine, which has no internal friction, and where the computational velocity is determined by the initial kinetic energy, is also described. Such a machine requires perfect parts and also requires the unrealistic assumption that the many extraneous degrees of freedom, which contribute to the physical structure, do not couple to the information-hearing degrees of freedom, and thus cause no friction. Quantum mechanical computation is discussed at two levels. First of all we deplore the assertion, repeatedly found in the literature, that the uncertainty principle. E Deltat ~ h-bar, with Delta t equated to a switching time, yields any information about energy dissipation. Similarly we point Out that computation is not an iterated transmission and receiving process. and that considerations, which avoid the uncertainty principle, and instead use quantum mechanical channel capacity considerations, are equally unfounded. At a more constructive level we ask whether there is a quantum mechanical version of the dissipationless computer. Benioff has proposed one possible answer. Quantum mechanical versions of dissipationless cotnputers may suffer from the problems found in electron transport in disordered one-dimensional periodic potentials: The buildup of internal reflections may give a transmission coefficient, through the whole computation. which decreases exponentially with the length of the computation.
Some authors cite the uncertainty principle Delta E Delta Tau ~ h and, with varying degrees of certainty, imply that if Delta Tau represents a switching time, then Delta E must represent an energy dissipation. This is sometimes presented as an obvious and incidental fact, without even an argument, in papers largely addressed to other matters. We can cite only a sampling of this somewhat varied literature (Bate, 1978; Cottey, 1978; Keyes, 1975; Ligomenides, 1967; Mead, 1980; Mundici, 1981; Stein, 1977, 1978; Triehwasser, 1974). Only Keyes’ (1975) discussion is distinguished by the fact that it states "It is hard to demonstrate that the energy ... must be irreversibly dissipated to heat," and is the only one of our citations to voice such a clear doubt. The use of the uncertainty principle can he answered at two levels. First of all Delta E, in the uncertainty principle, represents a spread in energy measurements, and not a dissipation, and the burden is on those invoking that argument, to show that the spread leads to a dissipation. Additionally, however, a particle obeying the Schrodinger equation can pass a highly localized feature, in space, very quickly, and still be in an energy eigenstate. Only if we try to measure the time of occurrence of ,that passage does the uncertainty principle play a role. Thus rapid switching of a particular logic variable, in a long sequence of events, does not, in any obvious fashion, require a spread in energy. Finally if we do construct a wavepacket with a spread in energy, it can pass many successive points in its path with relatively well-defined timing. The succession of events does not require a cumulative growth in energy spread. All these remarks show that an uncritical application of the uncertainty principle is unwarranted. The reader will see, however, that we do not have a counterexample and cannot guarantee that the conclusions are incorrect.
A second group of papers relies explicitly on quantum mechanical channel capacity theory. Starting with the pioneering papers of Gordon (1961) and Lasher (1961) quantum channel capacity theory has grown into a major industry (Harger, 1977; Helstrom, 1976; Yu, 1976). Papers by Bledsoe (1961) and Levitin (1982) discuss computational energy losses on this basis, and are closely related to discussions by Brernermann (1962, 1966, 1977). Bremermann finds the maximum rate of information transmission, obtainable with a given amount of energy. As discussed elsewhere (Landauer and Woo, 1973) the maximum rate is obtained in a burst of energy release which is So short that the total amount of information transmitted is only about one hit. Bekenstein (1981) has provided an independent approach, yielding results similar to Bremmermann's. It is reasonable to invoke channel capacity limitations if the computational process repeatedly requires the transmission, receipt, and detection of signals. The fact, however. that classical computers are not necessarily restricted by classical channel capacity restrictions (Bennett, 1973; Landauer, 1976a, 1981), can be taken as evidence that computation is not equivalent to a highly iterated signal transmission process. The fact that the application of channel capacity theory requires careful analysis of the physical receiving process can he demonstrated by a very elementary example: A massive roll of magnetic tape. with many hits, can he shot through space at almost relativistic velocity. The minimal energy dissipation that is required, however, consists of at most a modest number of kT (and perhaps not even that), related to the control of the tape’s orientation and center of gravity, and unrelated to its information content. Alternatively, we could receive a message in electromagnetic form and store it between reflecting mirrors, for eventual later controlled release.
Some existing discussions of the quantum mechanical computational process defy the simple dichotomy established above. Likharev (1977) proposed a particular superconducting computational scheme which, supposedly, has no classical minimal energy limits at all, hut does have quantum limits. We believe that Likharev’s classical analysis is in error, and in contradiction to our own closely related earlier discussion (Keyes and Landauer, 1970), because Likharev neglected the hack influence of logic stages on preceding stages. Likharev (1982) now agrees, and has provided a corrected analysis. He shows how time-modulated potential wells, cycled hack and forth between a monostable state and a bistable state (Keyes and Landauer, 1970) can be used to build a reversible computer. very much like the Bennett-Fredkin-Turing machine we will discuss in the next section. Likharev’s computer thus becomes the first reversible computer model based on electrical devices. Benioff (1980) has a sophisticated quantum mechanical description of a Turing machine which goes far beyond the other quantum mechanical discussions we have cited, and anticipates much of what we will have to say. We will return, subsequently, to comment on Benioff’s work.
In the following we shall first review how reversible computation, i.e., classical computation with arbitrarily small energy losses, can be accomplished. We then go on to ask how such machinery must he modified to permit classical dissipationless computing, in machinery with no friction at all. Finally we go on to ask, but without providing clear answers, whether there are equivalent quantum mechanical procedures.
Before proceeding to the details, motivated by the possibility of dissipationless quantum mechanical computation, we must also ask, is it desirable? To answer that, from a more practical view than the rest of this paper, let us admit that while we question the unconditional validity of the Delta E Delta t ~ h argument, we have little question that most practical schemes would, in fact, be characterized by such a limitation. In that case, to replace kT by h-bar / Delta t, as a phase space measure, which characterizes minimal energy requirements at high speeds, seems unprofitable. It is, after all, the total amount of computation carried out, which usually counts, and the speed of the individual event is secondary, in most cases. Admittedly, here, we are implying that we can use parallel circuitry to offset slow components, and computer science has, to date, been able to do that to a surprisingly limited extent. In this somewhat more practical vein than the rest of this paper, we also add an additional observation. Bistable optical devices have, in recent years, become a very fashionable field of investigation (Smith, 1981). Unfortunately the proponents of optical bistability generally do not ask themselves how to incorporate their inventions into a total system. As explained elsewhere (Landauer, 1976b), such system considerations quickly rob optical schemes of their initial appeal.
The basic logic element in the BET machine is a Fredkin gate shown in
Figure 1, a logically reversible function, i.e., one which provides a one-to-one
mapping, without loss of information. The Fredkin gate is, in fact, its
own inverse function. Figure 2 shows a particular physical embodiment of
this function for a computer in which information is carried by balls moving
along pipes or other guiding machinery, and where information is denoted
by the absence or presence of a ball. Landauer (1976a) describes how a
complete Turing machine can be built out of such gates and some auxiliary
mechanisms of a closely related kind. A key point: All of the degrees of
freedom of this computer are locked together, in particularly all the information
carrying balls advance together. Thus we can he sure that the controlling
ball along the upper channel in Fig. 1 arrives with the correct timing
to control the motion of the halls along the lower controlled tracks. (The
mechanism can, obviously, he designed to tolerate modest timing errors
and therefore limited thermal fluctuations in the coupling linkage.) One
possible coupling mechanism which locks the halls together is the comb
structure described in the Appendix. Alternatively, of course, we can simply
invent a formal Hamiltonian which keeps the particles synchronized. As
a third alternative we can assume charged information-hearing particles
whose motion is paced through charges which are moved along the outer surfaces
of the tubes which guide the information hearing particles.

Fig. 1. Fredkin gate has three inputs and three outputs. The uppermost input is transmitted unchanged and controls whether the two lower tracks arc also transmitted unchanged, or caused to cross over. This logic function loses no information and is its own inverse. (Fredkin’s original version has uncrossed tracks when a "I" is led into the top channel. This difference is not consequential.)
The springs, in Figure 2, are required to insure that the switch
remains in its intended, uncrossed, position if there is no ball in the
split pipe. The reliability of the computation depends on the probability
of thermal errors, and thus on the energy required for an unintended spring
compression. By choosing this spring energy large enough, we can obtain
any desired immunity to thermal errors. The necessity to store spring energy.
in a way which depends on the information manipulations, i.e., on how many
halls are passing through springs in a given machine cycle is unappealing.
We can eliminate this blemish by using complementary logic, in which
all Fredkin gates have a redundant partner carrying out the same step,
at the same time, but with the absence and presence of balls interchanged.
In the complementary device the tracks are crossed when there is no ball
present in the split control pipe. The addition of the complementary gates
leads to a predictable variation of stored energy, which is the same in
each machine cycle, and independent of information content. We can then
easily balance out the variation in stored energy by some other mechanism,
which stores the energy during the remaining parts of the cycle, and the
computation can proceed at constant stored energy.

Fig. 2. The ball moving along the top channel controls the gate and arrives at the split pipe, shown at the top, before the balls along the two bottom channels arrive at the "Switch Box" A ball entering the top split pipe pushes the two halves apart and, in doing so, does work against the springs. This energy is. however, retrieved after the ball leaves the split pipe at the right-hand end. The springs exist to insure that the split pipe remains closed if a 0 signal enters. The split pipe is in turn coupled to the switch box by a hard linkage, which controls the internal structure in the switch box, giving the switching action shown in Fig 1.
We will assume that there is no static friction and that the frictional
forces are proportional to velocity. Thus, if the computation is carried
out slowly enough, the energy losses, per step, can be made as small as
required. Note that in the presence of a small driving force the computation
will he primarily diffusive, with a small net drift. This, however, constitutes
no problem since the motion backwards and forwards is along the same unbranched
one-dimensional track, resulting from our total reliance on reversible
functions. As stressed in the earlier discussion (Landauer, l976a) a number
of kT must be dissipated in the final step to insure that the process
halts there and does not diffuse backwards again from there.
Computation can now be visualized as illustrated in Figure 3. Different horizontal rows correspond to different programs or initial conditions. Each of the circles corresponds to a given state for the tape and the Turing machine, and the forward progress of the computation consists of motion to the right.
We have described only one of several reversible computers that
have been invented. The others have been listed elsewhere (Landauer, 1981),
and are discussed in other papers at this conference (Bennett, 1982; Fredkin
and Toffoli, 1982; Likharev, 1982). One of these, proposed by Fredkin,
is a machine in which logic is accomplished through the collision of hard
billiard balls, guided by reflecting walls. This proposal is distinguished
by the fact that the information-bearing particles are the only moving
entities. On the other hand, it requires perfectly placed parts. and perfect
initial velocities, for the interacting particles. Furthermore, if we connect
such a computer to an infinite memory. our machine has an infinite stored
kinetic energy.

Fig. 3. The left-hand end of a horizontal chain represents the initial state. and forward computation represents motion to the right, through a sequence of states represented by successive circles. l)ifferent letters correspond to different initial states. i e.. different programs.
As an incidental point, we remind the reader that a reversible computer
can simulate any physical process, and remain close to equilibrium in this
simulation. This includes the simulation of scenarios leading to the origin
of life, and biological evolution, processes which are frequently assumed
to require serious departures from thermal equilibrium. The reader may
object that simulation on a computer is not equivalent to the real physical
process. Nevertheless, the two processes are equally effective in the development
of organization, and both processes require preliminary equipment to be
initiated. In one case, the proper soup of organic materials is required;
in the other, a computer Structure with a program representing the initial
state and the dynamics of the system. It’s not clear that this is a very
fundamental distinction.
The second reason for the delicacy of dissipationless systems is more fundamental. If we assume that the information-bearing degrees of freedom are imbedded in a physical structure, with a great many other degrees of freedom, is it reasonable to assume that the extraneous degrees of freedom remain innocuous and do not pick up any of the computational energy? If we have solid pipes, or mirrors, guiding information-hearing particles, is it reasonable to assume that the phonons in the guiding stnicture are uncoupled to the motion of the information-hearing particle? The answer to that is undoubtedly negative, but, to make some progress, we will cheat, and assume it is positive. A better alternative would he a computer which involves few or no extraneous degrees of freedom for the guiding machinery. I do not know whether such an invention is possible, and certainly have not seen it described. Thus we are not in a position to demonstrate that the universe permits the realization of a dissipationless computation, but only want to argue that such processes are not contrary to the laws of classical physics.
We will not try to construct a completely dissipationless computer, hut will allow ourselves a brake, to he thrown at the end of the computation, to halt the process, and prevent it from rebounding. It is not clear that this is necessary; possibly one could have a, way of storing the kinetic energy needed for the progress of the computation, in a fly wheel. Thus we will only argue that there is no energy dissipation requirement proportional to the number of steps in the computation.
What are the modifications required in the BET machine by the absence of friction? Let us continue to assume that the information-bearing particles are locked together. (An alternative possibility would depend on synchronization resulting from perfect particle velocities, combined with a guiding structure laid out so as to equalize all delays between successive gates. This would return us to the Fredkin billiard ball collision proposal, of the preceding section, or some still undescribed alternative to Figure 2.) If the particles are all locked to a comb, hut follow different paths, which are not all parallel to the motion of the comb, then the velocity, and the kinetic energy of a particular particle, cannot he constant. That is no problem, and can he handled either by letting the total comb velocity vary, in such a way that the total kinetic energy is constant, or else by additional offsetting energy storage schemes. The switching apparatus of Figure 2 must be left in a stationary position while it is controlling the motion of particles. The switching apparatus cannot he left with excess kinetic energy once it is brought to the correct position for crossed tracks. (This kind of problem is avoided in the colliding billiard ball scheme of Fredkin, where the only degrees of freedom with kinetic energy arc those of the information-bearing particles.) Thus the parts of the switch must approach their final position with zero velocity, as is the case for a typical classical turning point. This can he done by an intentional modulation of the velocity of the whole locked together computational apparatus. It can also be done at constant computational velocity, if the information-hearing particles are really circular in the cross-sectional shape that controls the pipe opening. Actually the circular shape, or smooth curvature, need only be present near the maximal portions of the cross section. Furthermore the variation in stored spring energy must dominate over the kinetic energy variation, i.e., we are driving the spring loaded switch below its resonance frequency. Thus the excess kinetic energy gained by the switch parts, when the hail first enters, will be used up in subsequent compression of the spring. If we are squeamish about velocity discontinuities, then we will also have to be careful about contours when the information-hearing particle first enters the split section, and equivalently when it leaves. Continuous velocity changes can he achieved by giving the leading and trailing edge of the particle the shape of a hollow ground knife edge. This, however, requires an exact control of lateral placements, when the information-hearing particle first starts inducing a separation between the split pipes.
When the particles emerge from the Turing head, and are deposited on the tape, they must be left at an exact position, and with no residual kinetic energy. This can he accomplished, for example, by modulating the computational velocity, and letting it go through zero at the time when information-bearing particles are released at the tape, and also when they are picked up. Alternatively, the particle can he released with its full velocity, and its kinetic energy then delivered to a storage system, e.g., a particle in a circular track or a flywheel. The kinetic energy delivered to this storage system is passed on, later, to another particle being picked up from the tape. By invoking the complementary logic, mentioned earlier, we can insure that the stored kinetic energy is independent of the information content. Again we note that no tolerances are allowed; the device storing the kinetic energy must he at the exact position, at the required time, and the mass of the information particle related exactly to the relevant parameter of the flywheel storage system. The device structure which locks the information-bearing particles together. e.g., the comb structure described in the Appendix, causes further tolerance problems of this kind. We want this structure to control the particle position exactly, without looseness. At the same time when the structure is inserted into, or otherwise grabs hold, of a particle on the tape, this must be a frictionless process, despite the exact fit. It is conceivable that our stated requirements for perfect machinery are the result of inadequate ingenuity, and that it is not really a fundamental aspect of dissipationless ballistic computing.
The dissipationless machine has not been described in the same detail,
nor is it really understood at the same level of detail, as the original
viscous BET machine. We can only assert that we see no real problems, as
long as we demand consistency with the laws of mechanics, rather than physical
realizability.
If one asks for a more specific description of the apparatus, and tries to invoke the kind of machinery sketched for ballistic dissipationless computation, in the preceding section, we run into severe problems. The uncertainty principle will prevent the exact positioning of kinetic energy storage devices with zero initial momentum. More generally: As long as we have independent degrees of freedom of that sort rattling around, including all the stored information-bearing particles along the Turing machine, how can we he certain we have left them in their ground state, without excess energy, when they are not in active use? There may he a solution to all this; I do not have it. Fredkin’s colliding billiard ball computer does avoid the extra rattling parts. As stated earlier, however, it needs to he supplemented by additional invention, to turn it into a complete computer, and also, of course, into a quantum mechanical device not dependent on the exact specification of both momentum and position. for independent particles.
Let us now be optimistic and assume that one of the approaches discussed above is possible, and permits a dissipationless quantum mechanical progression along the states of a chain, as shown in Figure 3. This still leaves some problems to he discussed. Figure 3 may suggest motion along a periodic lattice, translationally invariant except for the existence of terminations. This, however, would he an inappropriate interpretation. The successive states in the computation are not equivalent; they are distinguishable through their information content. We know, however, that the transmission coefficient of a long one-dimensional chain, which is complicated, and not periodic, tends to go to zero exponentially with the length of the chain (Anderson et al., 1980; Andereck and Ahrahams, 1980; Abrahams and Stephen, 1980; Ai.hel 1980a, 1980b, 1980c). Thus we note that dissipation-less quantum mechanical computation, at fixed internal kinetic energy. need not correspond to a fixed computational velocity. The lowered computational velocity results from the internal reflections. A small transmission coefficient, for the whole computation, viewed as one event, requires many successive attempts to achieve a completed computation. The exponential rise of the time required, with the length of the computation, would–in any serious practical sense–render many computations impossible. Possibly the effect of the reflections we have discussed, which depend predictably on the information being handled, can be offset by additional devices, analogous to antireflection coating on lenses, or tuning stubs in electrical transmission lines. Such matching devices will work perfectly only at a particular energy. Furthermore, it is far from clear what the nature of such devices would have to he. If we need a single such device or action, for each step of the Turing machine, and if its choice depends on the totality of events taking place in that step, that may he a rather difficult recipe. As Bennett asks, if the way of handling the computational step depends on all of its details, are we accomplishing anything? Such a question would disappear if the matching can he accomplished more locally, e.g., by suitable machinery at each Fredkin gate.
If we go on and, additionally, allow for some imperfections in our machinery,
then the existence of an exponentially decreasing transmission coefficient
seems inevitable, If we also allow for inelastic scattering events, however,
we restrict the range of the computation over which coherent internal reflections
can he effective. Taking our cue once again from the theory of electronic
transport in disordered potentials, we can then expect a mobility, and
can conduct computation at a velocity proportional to an applied force,
and with accompanying energy dissipation (Chaudhari and Habermeier, 1980;
Giordano, 1981; Thouless, 1981).
There is another general observation that seems appropriate. We, and
others,
in discussing fundamental computer limitations, have stressed the need
to consider schemes which can be made part of a Turing machine, or else
have access to unlimited storage in some other way. This requirement arises
because a finite machine has a limited number of programs it can execute,
all of which can, in principle, be foreseen by the designer. In other words,
a finite machine looks too much like a table lookup mechanism to seem interesting.
But our emphasis on machines of unlimited size seems really very unreasonable,
when we know (or at least strongly suspect) that nature will not allow
that. What we need here is a mode of analysis which comes closer to the
real world, where finite machines can do a great many tasks not understood
in advance by their designer; finite machines are really more than table
lookup devices. We need to characterize finite machines by a figure of
merit which characterizes the universe of calculations they can do (including,
perhaps, the rate at which these can be carried out), compared to the complexity
of the machine’s own structure.
Let the basic plane of operation, in which the information-bearing particles are moving, be the x–y plane. We will invoke occasional excursions in the z direction to solve the crossover problem. For further clarity, let us assume that there are a group of Fredkin gates lined up along x = 0, additional gates lined up along x = 1,2.3,4.... Thus, the particles moving from one Fredkin gate to the next must move along the x direction. Additional motion in the y direction may’ also be necessary since a given gate at, say, x = 0, y = 0 may provide input for a gate at x = 1, y = 17. Now, in this motion along the y direction, paths have to cross. How do we handle that?
The information-hearing particles (or "balls") have a comb of rods inserted into their structure, and this controls their progress in the x direction. The teeth of the comb point in the z direction, and are separated from each other along they direction. The comb will he at a given value of x at a specific time. Motion of the comb along x represents the forward (or backward) evolution of the computation. The comb is made up of many small teeth or rods, such that a given information-bearing particle is engaged, at any one time, by a number of these rods. For a particle in its normal position, taken to he at z = 0, in the plane of the Frcdkin gates, there will, in fact, be two combs coupling to a particle. The tubes, guides, or tracks do not surround the information-hearing particle completely, and permit the teeth to contact the particle, via a notch cut into the particle. One comb comes from positive values of z, the other from negative values of z. These two combs will move together and their combined motion represents one degree of freedom. We will assume that the crossovers are handled between successive Fredkin gates, and not near the integral values of x. The crossovers are handled with one track deviating out of z = 0, and going above that plane and the other track going below that plane. In that process we will assume that for the particle moving up in z, the comb guides coming from negative values of the z will lose contact with the particle and the particle will only be guided by the comb coming from positive values of z. That should be enough to keep the particle moving. Similarly the particle which goes below the z = 0 plane will continue to make contact only with the comb coming from negative values of z. The teeth can he considered to be pushed toward the z = 0 plane by springs. so that if the particle is taken out of the z = 0 plane we do work against these springs. That, in turn, will be regained when the particle comes hack toward zero or when the particle leaves a given guiding tooth. The comb teeth should he pointed, as they actually are in a real comb. Thus a particle which is pushed up against a nonelevated tooth will automatically raise that tooth. The particles, during their departure from the z = 0 plane, will always he guided by at least one of the two sets of combs. This scheme requires compression and decompression of the springs, behind the teeth, hut the energy dissipation can be made arbitrarily small, by sufficiently slow motion.
Let us now view our overall logic scheme as a complementary one, in
which all logic stages are duplicated, except that in the duplication the
"0" is replaced by a "1" and visa versa. In such a scheme we can be sure
that along two complementary crossover tracks one, and only one, set of
comb teeth will be pushed against their springs. Thus the total energy
required by the springs will be independent of the information content,
and we can then provide balancing forces along the remainder of the motion,
so that the total stored energy remains constant, and independent of the
springs being compressed.