Reversible computing

Reversible computing is any model of computation where every step of the process is time-reversible. This means that, given the output of a computation, it is possible to perfectly reconstruct the input. In systems that progress deterministically from one state to another, a key requirement for reversibility is a one-to-one correspondence between each state and its successor. Reversible computing is considered an unconventional approach to computation and is closely linked to quantum computing, where the principles of quantum mechanics inherently ensure reversibility (as long as quantum states are not measured or "collapsed").^[1]

Reversibility

There are two major, closely related types of reversibility that are of particular interest for this purpose: physical reversibility and logical reversibility.^[2]

A process is said to be physically reversible if it results in no increase in physical entropy; it is isentropic. There is a style of circuit design ideally exhibiting this property that is referred to as charge recovery logic, adiabatic circuits, or adiabatic computing (see adiabatic process). Although in practice no nonstationary physical process can be exactly physically reversible or isentropic, there is no known limit to the closeness with which we can approach perfect reversibility, in systems that are sufficiently well isolated from interactions with unknown external environments, when the laws of physics describing the system's evolution are precisely known.

A motivation for the study of technologies aimed at implementing reversible computing is that they offer what is predicted to be the only potential way to improve the computational energy efficiency (i.e. useful operations performed per unit energy dissipated) of computers beyond the fundamental von Neumann–Landauer limit^[3][4] of kT ln(2) energy dissipated per irreversible bit operation.

The Landauer limit was millions of times below the energy consumption of computers in the 2000s and thousands of times less in the 2010s.^[5] Reversible computing proponents argue that a significant portion of this energy consumption is due to architectural overheads. These overheads are the energy costs associated with non-computational parts of the system, such as wires, transistors, and memory, that are required to make a computer work. They believe that makes it difficult for current technology to achieve much greater energy efficiency without adopting reversible computing principles. ^[6]

Relation to thermodynamics

As was first argued by Rolf Landauer while working at IBM in 1961,^[7] in order for a computational process to be physically reversible, it must also be logically reversible. Landauer's principle is the observation that the oblivious erasure of n bits of known information must always incur a cost of nkT ln(2) in thermodynamic entropy. A discrete, deterministic computational process is said to be logically reversible if the transition function that maps old computational states to new ones is a one-to-one function; i.e. the output logical states uniquely determine the input logical states of the computational operation.

For computational processes that are nondeterministic (in the sense of being probabilistic or random), the relation between old and new states is not a single-valued function, and the requirement needed to obtain physical reversibility becomes a slightly weaker condition, namely that the size of a given ensemble of possible initial computational states does not decrease, on average, as the computation proceeds forwards.

Physical reversibility

Landauer's principle (and indeed, the second law of thermodynamics) can also be understood to be a direct logical consequence of the underlying reversibility of physics, as is reflected in the general Hamiltonian formulation of mechanics, and in the unitary time-evolution operator of quantum mechanics more specifically.^[8]

The implementation of reversible computing thus amounts to learning how to characterize and control the physical dynamics of mechanisms to carry out desired computational operations so precisely that the experiment accumulates a negligible total amount of uncertainty regarding the complete physical state of the mechanism, per each logic operation that is performed. In other words, precisely track the state of the active energy that is involved in carrying out computational operations within the machine, and design the machine so that the majority of this energy is recovered in an organized form that can be reused for subsequent operations, rather than being permitted to dissipate into the form of heat.

Although achieving this goal presents a significant challenge for the design, manufacturing, and characterization of ultra-precise new physical mechanisms for computing, there is at present no fundamental reason to think that this goal cannot eventually be accomplished, allowing someday to build computers that generate much less than 1 bit's worth of physical entropy (and dissipate much less than kT ln 2 energy to heat) for each useful logical operation that they carry out internally.

Today, the field has a substantial body of academic literature. A wide variety of reversible device concepts, logic gates, electronic circuits, processor architectures, programming languages, and application algorithms have been designed and analyzed by physicists, electrical engineers, and computer scientists.

This field of research awaits further development of high-quality, cost-effective, nearly reversible logic device technology, including energy-efficient clocking and synchronization mechanisms, or designs that avoid the need for these through asynchronous operation. Further engineering advances would likely be needed before the large body of theoretical research on reversible computing could find practical application in enabling computer technology to address near-term barriers to energy efficiency, including the von Neumann–Landauer bound. According to the second law of thermodynamics^[9], circumventing this bound may require the use of logically reversible computing.

Logical reversibility

For a computational operation to be logically reversible means that the output (or final state) of the operation can be computed from the input (or initial state), and vice versa. Reversible functions must be injective. This means that reversible gates (and circuits, i.e. compositions of multiple gates) generally have the same number of input bits as output bits (assuming that all input bits are consumed by the operation).

An inverter (NOT) gate is logically reversible because it can be undone. The NOT gate may however not be physically reversible, depending on its implementation.

The exclusive or (XOR) gate is irreversible because its two inputs cannot be unambiguously reconstructed from its single output, or alternatively, because information erasure is not reversible. However, a reversible version of the XOR gate—the controlled NOT gate (CNOT)—can be defined by preserving one of the inputs as a 2nd output. The three-input variant of the CNOT gate is called the Toffoli gate. It preserves two of its inputs a,b and replaces the third c by ${\displaystyle c\oplus (a\cdot b)}$. With ${\displaystyle c=0}$, this gives the AND function, and with ${\displaystyle a\cdot b=1}$ this gives the NOT function. Because AND and NOT together is a functionally complete set, the Toffoli gate is universal and can implement any Boolean function (if given enough initialized ancilla bits).

Surveys of reversible circuits, their construction and optimization, as well as recent research challenges, are available.^{[10][11][12][13][14]}

Reversible Turing machines (RTMs)

The reversible Turing machine (RTM) is a foundational model in reversible computing. An RTM is defined as a Turing machine whose transition function is invertible, ensuring that each machine configuration (state and tape content) has at most one predecessor configuration. This guarantees backward determinism, allowing the computation history to be traced uniquely.^[15]

Formal definitions of RTMs have evolved over the last decades. While early definitions focused on invertible transition functions, more general formulations allow for bounded head movement and cell modification per step. This generalization ensures that the set of RTMs is closed under composition (executing RTM ${\displaystyle A}$ followed by executing RTM ${\displaystyle B}$ results in a new RTM) and inversion (the inverse of an RTM is also an RTM), forming a group structure for reversible computations. This contrasts with some classical TM definitions where composition might not yield a machine of the same class.^[16] The dynamics of an RTM can be described by a global transition function that maps configurations based on a local rule.^[17]

Yves Lecerf proposed a reversible Turing machine in a 1963 paper,^[18] but apparently unaware of Landauer's principle, did not pursue the subject further, devoting most of the rest of his career to ethnolinguistics.

A landmark result by Charles H. Bennett in 1973 demonstrated that any standard Turing machine can be simulated by a reversible one.^[19] Bennett's construction involves augmenting the TM with an auxiliary "history tape". The simulation proceeds in three stages:^[20]

1. Compute: The original TM's computation is simulated, and a record of every transition rule applied is written onto the history tape.
2. Copy output: The final result on the work tape is copied to a separate, initially blank output tape. This copy operation itself must be done reversibly (e.g., using CNOT gates).
3. Uncompute: The simulation runs in reverse, using the history tape to undo each step of the forward computation. This process erases the work tape and the history tape, returning them to their initial blank state, leaving only the original input (preserved on its tape) and the final output on the output tape.

This construction proves that RTMs are computationally equivalent to standard TMs in terms of the functions they can compute, establishing that reversibility does not limit computational power in this regard.^[20] However, this standard simulation technique comes at a cost. The history tape can grow linearly with the computation time, leading to a potentially large space overhead, often expressed as ${\displaystyle S'(n)=O(S(n)T(n))}$ where ${\displaystyle S}$ and ${\displaystyle T}$ are the space and time of the original computation.^[19] Furthermore, history-based approaches face challenges with local compositionality; combining two independently reversibilized computations using this method is not straightforward. This indicates that while theoretically powerful, Bennett's original construction is not necessarily the most practical or efficient way to achieve reversible computation, motivating the search for methods that avoid accumulating large amounts of "garbage" history.^[20]

RTMs compute precisely the set of injective (one-to-one) computable functions. They are not strictly universal in the classical sense because they cannot directly compute non-injective functions (which inherently lose information). However, they possess a form of universality termed "RTM-universality" and are capable of self-interpretation.^[15]

Commercialization

London-based Vaire Computing is prototyping a chip in 2025, for release in 2027.^[21]

See also

References

Further reading

• Frank, Michael P. (2017). "The Future of Computing Depends on Making It Reversible"" (web) / "Throwing Computing Into Reverse" (print). IEEE Spectrum. 54 (9): 32–37. doi:10.1109/MSPEC.2017.8012237.
• Denning, Peter; Lewis, Ted (2017). "Computers That Can Run Backwards". American Scientist. 105 (5): 270. doi:10.1511/2017.105.5.270. hdl:10945/59278. S2CID 125446656.
• Glück, Robert; Yokoyama, Tetsuo (2023). "Reversible computing from a programming language perspective". Theoretical Computer Science. 953 113429. doi:10.1016/j.tcs.2022.06.010.
• Lange, Klaus-Jörn; McKenzie, Pierre; Tapp, Alain (April 2000). "Reversible Space Equals Deterministic Space". Journal of Computer and System Sciences. 60 (2): 354–367. doi:10.1006/jcss.1999.1672.
• Perumalla K. S. (2014), Introduction to Reversible Computing, CRC Press.
• Vitányi, Paul (2005). "Time, space, and energy in reversible computing". Proceedings of the 2nd conference on Computing frontiers – CF '05. pp. 435–444. arXiv:cs/0504088. doi:10.1145/1062261.1062335. ISBN 1-59593-019-1. S2CID 5252384.

External links

• Introductory article on reversible computing
• First International Workshop on reversible computing
• Publications of Michael P. Frank: Sandia (2015-), FSU (2004-'15), UF (1999-2004), MIT 1996-'99).
• Reversible Computation workshop/conference series
• CCC Workshop on Physics & Engineering Issues in Adiabatic/Reversible Classical Computing
• Open-source toolkit for reversible circuit design