Reversible computation
xantox, 20 January 2008 in ComputationOther Languages:
A computation (from latin computare, “to count”, “to cut”), is the abstract representation of a physical process in terms of states, and transitions between states or events.
The definition of possible states and events is formulated in a computation model, such as the Turing machine or the finite automaton. For example, a Turing machine state is the complete sequence of symbols on its tape plus the head’s position and internal symbol, and an event is the motion between two successive states, defined deterministically as a combination of read, write, move left and move right elementary motions.
In order to perform a computation, a robust mapping is first established between a computation model and a physical system, meaning that states and events in the model are used to label states and events observed in the system, and that the choosen correspondence is sufficiently stable in respect to various kinds of perturbations.
The system is then prepared in an initial state and is allowed to evolve through a path of events within the space of states, until it eventually reaches a state labeled as final. The discretized dynamics of the computational space may be represented with a directed graph, where nodes are possible states of the system and edges are events transforming a state into another.
 |
 |
||
| Irreversible computational dynamics Click image to zoom1 |
|||
Logical reversibility
A function is said reversible (from latin revertere, ‘to turn back’) if, given its output, it is always possible to determine back its input, which is the case when there is a one-to-one relationship between input and output states. If the space of states is finite, such a function is a permutation. Logical reversibility implies conservation of information.
When several input states are mapped onto the same output state, then the function is irreversible, since it is impossible by only knowing the final state to find back the initial state. In boolean algebra, NOT is reversible, while SET TO ONE is irreversible. Two-argument boolean functions like AND, OR, XOR are also irreversible, since they map 22 input states into 21 output states so that information is lost in the merging of paths, like shown in the following graph of a NAND computation, whose reverse evolution is no longer deterministic.
The right side tries to depict the inverse mapping to the left side
Physical reversibility
Known laws of physics are reversible. This is the case both of classical mechanics, based on lagrangian/hamiltonian dynamics, and of standard quantum mechanics, where closed systems evolve by unitary transformations, which are bijective and invertible. As a consequence, when a physical system performs an irreversible computation, the computation model’s mapping indicates that the computing system cannot stay closed.
More precisely, since an irreversible computation reduces the space of physical information-bearing states, then their entropy must decrease by increasing the entropy of the non-information bearing states, representing the thermal part of the system.
In 1961 Landauer studied this thermodynamical argument, and proposed the following principle: if a physical system performs a logically irreversible classical computation, then it must increase the entropy of the environment with an absolute minimum of heat release of kT x ln(2) per lost bit (where k is Boltzmann’s constant and T the temperature, ie. about 3 x 10-21 joules at room temperature),2 which emphasizes two facts:
- the logical irreversibility of a computation implies the physical irreversibility of the system performing it (”information is physical”);
- logically reversible computations may be at least in principle intrinsically nondissipative (which bears a relationship with Carnot’s heat engine theorem, showing that the most efficient engines are reversible ones, and Clausius theorem, attributing zero entropy change to reversible processes).
Reversible embedding of irreversible computations
Landauer further noticed that any irreversible computation may be transformed into a reversible one by embedding it into a larger computation where no information is lost, eg. by replicating every output in the input (’sources’) and every input in the output (’sinks’).
For example, the NAND irreversible function seen above may be embedded in the following bijection, also known as Toffoli gate3 (the original function is indicated in red):
The additional bits of information, like Ariadne’s threads, ensure that any computational path may be reversed: they are the garbage of the forward path and the program of the backwards path. Instead of losing them in the environment, they are kept in the controlled computational space.
Toffoli gates are universal reversible logic primitives, meaning that any reversible function may be constructed in terms of Toffoli gates. The Fredkin gate is another example of universal reversible logic primitive. It exchanges its two inputs depending on the state of a third control input, thus allowing to embed any computation into a conditional routing of paths carrying conserved signals.
Reversible computation models
The billiard-ball model, invented by Fredkin and Toffoli,4 was one of the first computation models focusing on implementation with reversible physical components. Based on the laws of classical mechanics, it is equivalent to the formalism of kinetic theory of perfect gases. The presence of moving rigid spheres at specified points are defined as 1’s, their absence as 0’s. Interactions by means of right-angle collisions allow to construct various logic primitives, like for example the following 2-input, 3-output universal gate due to Feynman,5 who also proposed with Ressler a billiard-ball version of the Fredkin gate.
Feynman switch gate
In practice, these computing spheres would be very unreliable, as instability arising from arbitrarily small perturbations would quickly generate chaotic deviations, producing an output saturated with errors. The errors may be corrected (for example, by adding potentials to stabilize the paths), however the error correction process is itself irreversible and dissipative - since it has to erase the erroneous information. Hence, error correction appears to be the only aspect of computation defining a lower bound to energy dissipation.
A stabler approach is that of the Brownian computation model,6 where thermal noise is on the contrary allowed to freely interact with a computing system near equilibrium. Potential energy barriers define the paths of a computational space, where the system walks randomly until it eventually reaches a final state. RNA polymerase, the enzyme involved in DNA transcription, is an example of a brownian logically reversible tape-copying machine. The DNA replication process also follows a similar mechanism, but adds a logically irreversible error-correcting step.
Lecerf-Bennett reversal
The embedding method is however insufficient to build a physically reversible universal computer, since the growing amount of information needing to be replicated for each event would saturate any finite memory. Then, computation would come to an end - unless the memory would be irreversibly erased, but then dissipation would have been merely postponed, and not avoided.
This seemed to rule out the possibility of useful reversible computing machines, until a remarkable solution was found by Bennett7 (earlier work by Lecerf8 anticipated its formal method), showing that it is possible at least in principle to perform an unlimited amount of computation without any energy dissipation.
The reversible system shall compute the embedding function twice: the first time “forwards” to obtain and save the computation result, and the second time “backwards”, as a mirror-image computation of the inverse function, de-computing the first step and returning the closed system to its initial state.
M. C. Escher, Swans (1956).
All M.C. Escher works (c) 2007 The M.C. Escher Company - the Netherlands.
All rights reserved. Used by permission. www.mcescher.com
Click image to zoom
Logical irreversibility and Maxwell’s demon
In 1867 Maxwell devised a thought experiment involving a finite microscopic “demon” capable of observing the motion of individual molecules. This demon guards a small hole separating two containers, filled with gas at the same temperature. When a molecule approaches, the demon checks its speed and then opens or closes a shutter, so as slower molecules always go in one container (cooling it), and faster molecules go in the other (heating it), in apparent violation of the 2nd law of thermodynamics.
A first important step toward the solution of this controversial paradox was taken in 1929 by Szilard9 who, after avoiding dualistic traps by substituting the intelligent demon with a simple machine, suggested that proper accounting of entropy is restored in the process of measuring the molecule position. This explanation became the standard one until 1981, when Bennett showed6 that the fundamentally dissipative step is surprisingly not the measurement (which can be done reversibly) but the logically irreversible erasure of demon’s memory, to make room for new measurements.
Reversibility in quantum computation
Quantum computation takes advantage of the physical effects of superposition and entanglement, leading to a qualitatively new computation paradigm.10 In quantum mechanical computation models, all events occur by unitary transformations, so that all quantum gates are reversible.
Quantum systems are less susceptible to certains kinds of errors affecting classical computations, since their discrete spectrum prevents trajectories from becoming chaotic, so that, for example, a quantum “billiard ball model” is more reliable than its classical counterpart.
However, quantum systems are also affected by new sources of error, as a consequence of interactions with the environment, such as the loss of quantum coherence. It is possible to correct generic quantum errors up to a limit,11 so as to reconstruct an error-free quantum state, at the price of performing an irreversible quantum erasure of the erroneous quantum information.
I thank Charles H. Bennett for stimulating comments on the draft.
- A. Wuensche, M. Lesser, “The global dynamics of cellular automata“, Ref Vol. I of the Santa Fe Institute Studies in the Sciences of Complexity. Addison-Wesley (1992) [Images of cellular automata state transition graphs]. [↩]
- R. Landauer, “Irreversibility and heat generation in the computing process“, IBM Journal of Res. and Dev., 5:3, 183 (1961) [Logical irreversibility, Landauer’s principle]. [↩]
- T. Toffoli, “Reversible computing“, Tech. Memo MIT/LCS/TM-151, Mit Lab. for Comp. Sci. (1980) [Toffoli gate, reversible automata]. [↩]
- E. Fredkin, T. Toffoli, “Conservative logic“, International Journal of Theoretical Physics, 21:3-4, 219-253 (1982) [Billiard ball model]. [↩]
- R. P. Feynman, “Feynman lectures on computation (1984-1986)”, Perseus Books (2000) [↩]
- C. H. Bennett, “The thermodynamics of computation - a review“, International Journal of Theoretical Physics, 21:12, 905-940 (1982) [Brownian computation model; logical irreversibility and Maxwell’s demon]. [↩]
- C. H. Bennett, “Logical reversibility of computation“, IBM Journal of Res. and Dev., 17:6 525 (1973). [In this paper, related to the problem of the connection between computing and heat generation explored by Landauer, Bennett devised the “save result and reverse” method and proved that any irreversible computation may be simulated reversibly]. [↩]
- Y. Lecerf, “Machines de Turing réversibles“, english translation by M. Frank, “Reversible Turing Machines“, Comptes Rendus Hebdomadaires des Séances de L’académie des Sciences 257:2597-2600 (1963). [In this mathematical paper, unrelated to issues of physical reversibility, Lecerf sought to design a reversible Turing machine. It is the first work proposing the method of saving the computation history and then decomputing it away, though it had initially little impact and was ‘discovered’ only much after Bennett’s results, perhaps because it was not published in english and Lecerf himself did not emphasize it. It has a minor flaw, ie the inverse of a read-write-shift quintuple is a quintuple of different sort, namely shift-read-write]. [↩]
- L. Szilard, “Über die Entropieverminderung in einem thermodynamischen System bei Eingriffen intelligenter Wesen“, Journal Zeitschrift für Physik, 53, 840-856 (1929); english translation “On the decrease of entropy in a thermodynamic system by the intervention of intelligent beings” in Behavioral Science, 9:4, 301-310 (1964). [↩]
- D. Deutsch, “Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer“, Proc. Roy. Soc. Lond., A400, 97–117 (1985). [Foundation of the quantum model of computation, universal quantum Turing machine] [↩]
- A. R. Calderbank, P. W. Shor, “Good quantum error-correcting codes exist“, Phys. Rev. A 54, 1098-1105 (1996). [↩]
