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 2² input states into 2¹ 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),² 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 gate³ (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.

Some railroad switches are reversible

Reversible computation models

The billiard-ball model, invented by Fredkin and Toffoli,⁴ 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,⁵ 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,⁶ 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 Bennett⁷ (earlier work by Lecerf⁸ 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 Szilard⁹ 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 showed⁶ 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.¹⁰ 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,¹¹ 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.

1. 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]. [↩]
2. 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]. [↩]
3. T. Toffoli, “Reversible computing“, Tech. Memo MIT/LCS/TM-151, Mit Lab. for Comp. Sci. (1980) [Toffoli gate, reversible automata]. [↩]
4. E. Fredkin, T. Toffoli, “Conservative logic“, International Journal of Theoretical Physics, 21:3-4, 219-253 (1982) [Billiard ball model]. [↩]
5. R. P. Feynman, “Feynman lectures on computation (1984-1986)”, Perseus Books (2000) [↩]
6. 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]. [↩]
7. 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]. [↩]
8. 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]. [↩]
9. 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). [↩]
10. 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] [↩]
11. A. R. Calderbank, P. W. Shor, “Good quantum error-correcting codes exist“, Phys. Rev. A 54, 1098-1105 (1996). [↩]

Share This

Liquid surfaces are pulled by the intermolecular forces, which are unbalanced on the boundary, producing surface tension. When liquid layers with different surface tension get in contact, these forces cause a flow, also known as Marangoni effect,¹ which is also the origin of the beautiful patterns found in the ancient japanese art of Suminagashi (”floating ink”). In this image, a film of oleic acid surfactant (with surface tension 32.5 mN/m) quickly spreads spontaneously about 2.5 mm over a layer of glycerol (with surface tension 63.4 mN/m). Both Marangoni and capillary stresses cause variations in the film thickness, leading to dendritic flow patterns. The contour lines are interference fringes.

Click image to zoom²

1. C. Marangoni, “Über die Ausbreitung der Tropfen einer Flüssigkeit auf der Oberfläche einer anderen”, Ann. Phys. Leipzig, 143:337-354 (1871). [↩]
2. © B. J. Fischer, A. A. Darhuber, S. M. Troian, Department of Chemical Engineering, Princeton University [↩]

Share This

Terrestrial clouds are the result of extraordinarily complex interactions between water and air, with several feedback mechanisms combining the effects of fluid dynamics and thermodynamics.¹

Click image to zoom²

The kind of convective clouds known as cumulus are produced by the vertical winds occurring in regions of warm moist air, according to Archimedes principle. The rapid lifting results in adiabatic expansion and cooling, and consequent accretion of water droplets. The irregular distribution of droplets scatters sunlight geometrically in all directions, producing a bright white appearance like in snow, decaying into gray shades as per their optical thickness. Each cloud is short-lived, lasting approximately 15 minutes in average.

1. H. R. Pruppacher, J. D. Klett, “Microphysics of clouds and precipitation“, Springer (1997); R. A. Houze, “Cloud Dynamics“, Academic Press (1994) [↩]
2. © 2004 Sarah Robinson, Flow Visualization Course, University of Colorado [↩]

Share This

Scientists at the University of Rochester and the J. Craig Venter Institute have discovered a copy of the entire genome of Wolbachia, a bacterial parasite, residing inside the genome of its completely different host species Drosophila Ananassae, the fruitfly. To isolate the fly’s genome from the parasite’s, the flies were fed with a simple antibiotic, killing the Wolbachia, but Wolbachia genes were still there. The scientists found that the genes were residing directly inside the second chromosome of the insect, and that some of these genes are even transcribed in uninfected flies, so that copies of the gene sequence are made in cells that could be used to make Wolbachia proteins.

Share This

Physicists from the University of Texas at Austin found that “a liquid jet can bounce off a bath of the same liquid if the bath is moving horizontally with respect to the jet. Previous observations of jets rebounding off a bath (e.g. Kaye effect) have been reported only for non-Newtonian fluids, while we observe bouncing jets in a variety of Newtonian fluids, including mineral oil poured by hand. A thin layer of air separates the bouncing jet from the bath, and the relative motion replenishes the film of air. Jets with one or two bounces are stable for a range of viscosity, jet flow rate and velocity, and bath velocity. The bouncing phenomenon exhibits hysteresis and multiple steady states”.¹

1. M. Thrasher, S. Jung, Y. Kwong Pang, C. Chuu, H. L. Swinney, “The Bouncing Jet: A Newtonian Liquid Rebounding off a Free Surface“, arXiv:0707.1721v1 [physics.flu-dyn] (2007). [↩]

Share This

From ACQAO through The Quantum Pontiff: “Theorists from the UQ (Ashton Bradley, Simon Haine, Murray Olsen) and ANU Faculties (Joseph Hope) nodes of the ARC Centre of Excellence for Quantum-Atom Optics (ACQAO) have come up with a scheme to teleport quantum states of collections of atoms from one position to another by converting the quantum state to light and back again. The scheme relies on the sender and receiver each having a reservoir of extremely cold atoms, known as a Bose-Einstein condensate [and] it gets around the need for the sender and receiver to share entanglement, as the quantum state to be teleported is never actually measured“.¹

1. A. S. Bradley, M. K. Olsen, S. A. Haine, J. J. Hope, “Teleportation of massive particles without shared entanglement“, arXiv:0706.0062v1 [quant-ph] (2007). [↩]

Share This

Animation showing the interaction of four charges of equal mass¹, two positive and two negative, in the approximation of classical electromagnetism. The particles interact via the Coulomb force, mediated by the electric field represented in yellow. A repulsive “Pauli force” of quantum mechanical origin, which becomes very large at a critical distance of about the radius of the spheres shown in the animation, keeps the charges from collapsing into the same point. Additionally, the motion of the particles is damped by a term proportional to their velocity, allowing them to “settle down” into stable (or meta-stable) states.

When the charges are allowed to evolve from the initial state, the first thing that happens (very quickly, since the Coulomb attraction between unbalanced charges is very large) is that they pair off into dipoles. Thereafter, there is still a (much weaker) interaction between neighboring dipoles (van der Waals force). Although in principle it can be either repulsive or attractive, there is a torque that rotates the dipoles so that it is attractive, eventually bringing the two dipoles together in a bound state. This mechanism binds the molecules of some substances into a solid.

1. © 2004 MIT TEAL/Studio Physics Project, John Belcher [↩]

Share This

From PhysicsWeb News: “The existence of a hypothetical particle called the axion has been put into further doubt now that the team that first claimed its discovery has failed to reproduce their results. Physicists working on the PVLAS experiment in Italy say that the tiny rotation in the polarization of laser light that they reported last year does not support the existence of axions, but rather is an artifact related to how the experiment had been performed”¹.

1. E. Zavattini et al., “New PVLAS results and limits on magnetically induced optical rotation and ellipticity in vacuum“, arXiv:0706.3419v1 (2007) [↩]

Share This