View source for Reversible computing

{{short description|Model of computation in which all processes are time-reversible}}

'''Reversible computing''' is any [[model of computation]] where every step of the [[computational process|process]] is [[time-reversible]]. This means that, given the output of a computation, it's possible to perfectly reconstruct the input. In systems that [[Transition system|progress]] [[Deterministic system|deterministically]] from one state to another, a key requirement for reversibility is a [[injective function|one-to-one]] [[Binary relation|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 state]]s are not measured or "[[wave function collapse|collapsed]]").<ref name="Williams">{{cite book |author=Williams |first=Colin P. |title=Explorations in Quantum Computing |publisher=[[Springer Science+Business Media|Springer]] |year=2011 |isbn=978-1-84628-887-6 |pages=25–29}}</ref>

==Reversibility<!--'Logical reversibility', 'Charge recovery logic', and 'Adiabatic computing' redirect here-->==
There are two major, closely related types of reversibility that are of particular interest for this purpose: [[Reversible process (thermodynamics)|physical reversibility]] and '''logical reversibility'''<!--boldface per WP:R#PLA-->.<ref>{{Cite web | url=http://www.cise.ufl.edu/research/revcomp/ |title = The Reversible and Quantum Computing Group (Revcomp)}}</ref>

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'''<!--boldface per WP:R#PLA-->, [[adiabatic circuit]]s, or '''adiabatic computing'''<!--boldface per WP:R#PLA--> (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 [[Physics|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 [[Efficient energy use|energy efficiency]] (i.e., useful operations performed per unit energy dissipated) of computers beyond the fundamental [[von Neumann-Landauer limit|von Neumann–Landauer limit]]<ref name="landauer">{{Citation |author=Landauer |first=Rolf |title=Irreversibility and heat generation in the computing process |url=http://worrydream.com/refs/Landauer%20-%20Irreversibility%20and%20Heat%20Generation%20in%20the%20Computing%20Process.pdf |journal=IBM Journal of Research and Development |volume=5 |issue=3 |pages=183–191 |year=1961 |doi=10.1147/rd.53.0183 |quote=The entropy of a closed system, e.g., a computer with its own batteries, cannot decrease; hence this entropy must appear elsewhere as a heating effect, supplying 0.6931 kT per restored bit to the surroundings. |accessdate=2015-02-18}}</ref><ref name="neumann">{{cite book|author=J. von Neumann|author-link=John von Neumann|publisher=University of Illinois Press|title=Theory of self-reproducing automata|year=1966|url=https://archive.org/details/theoryofselfrepr00vonn_0|access-date=2022-05-21}} Third lecture: Statistical Theories about Information</ref> of {{Math|''[[kT (energy)|kT]]'' ln(2)}} energy dissipated per irreversible [[bit operation]]. Although the Landauer limit was millions of times below the energy consumption of computers in the 2000s and thousands of times less in the 2010s,<ref>{{cite journal |last1=Bérut |first1=Antoine |last2=Arakelyan |first2=Artak |last3=Petrosyan |first3=Artyom |last4=Ciliberto |first4=Sergio |last5=Dillenschneider |first5=Raoul |last6=Lutz |first6=Eric |title=Experimental verification of Landauer's principle linking information and thermodynamics |journal=Nature |date=March 2012 |volume=483 |issue=7388 |pages=187–189 |doi=10.1038/nature10872 |pmid=22398556 |bibcode=2012Natur.483..187B |arxiv=1503.06537 |s2cid=9415026 }}</ref> proponents of reversible computing argue that this can be attributed largely to architectural overheads which effectively magnify the impact of Landauer's limit in practical circuit designs, so that it may prove difficult for practical technology to progress very far beyond current levels of energy efficiency if reversible computing principles are not used.<ref>Michael P. Frank. Foundations of Generalized Reversible Computing. Conference on Reversible Computation, July 6–7, 2017, Kolkata, India. [[doi:10.1007/978-3-319-59936-6 2]] Preprint available at https://www.osti.gov/servlets/purl/1456440 (PDF).</ref>

==Relation to thermodynamics==
As was first argued by [[Rolf Landauer]] while working at [[IBM]],<ref>{{cite journal |last1=Landauer |first1=R. |title=Irreversibility and Heat Generation in the Computing Process |journal=IBM Journal of Research and Development |date=July 1961 |volume=5 |issue=3 |pages=183–191 |doi=10.1147/rd.53.0183 }}</ref> 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 {{Math|''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 [[CPT symmetry|reversibility of physics]], as is reflected in the [[Hamiltonian mechanics|general Hamiltonian formulation of mechanics]], and in the [[time evolution|unitary time-evolution operator]] of [[quantum mechanics]] more specifically.<ref>{{Cite journal |last1=Frank |first1=Michael P. |last2=Shukla |first2=Karpur |date=June 1, 2021 |title=Quantum Foundations of Classical Reversible Computing |journal=Entropy |language=en |volume=23 |issue=6 |pages=701 |doi=10.3390/e23060701 |issn=1099-4300 |pmc=8228632 |pmid=34206044 |arxiv=2105.00065 |bibcode=2021Entrp..23..701F |doi-access=free }}</ref>

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 gate]]s, [[electronic circuit]]s, processor architectures, [[programming language]]s, and application [[algorithm]]s have been designed and analyzed by [[physicist]]s, [[electrical engineer]]s, and [[computer scientist]]s.

This field of research awaits the detailed development of a high-quality, cost-effective, nearly reversible logic device technology, one that includes highly energy-efficient [[clocking]] and [[synchronization]] mechanisms, or avoids the need for these through asynchronous design. This sort of solid engineering progress will be needed before the large body of theoretical research on reversible computing can find practical application in enabling real computer technology to circumvent the various near-term barriers to its energy efficiency, including the von Neumann–Landauer bound. This may only be circumvented by the use of logically reversible computing, due to the [[second law of thermodynamics]].<ref>{{Cite book |last=Frank |first=Michael P. |title=Reversible Computation |chapter=Physical Foundations of Landauer's Principle |date=2018 |editor-last=Kari |editor-first=Jarkko |editor2-last=Ulidowski |editor2-first=Irek |chapter-url=https://link.springer.com/chapter/10.1007/978-3-319-99498-7_1 |series=Lecture Notes in Computer Science |volume=11106 |language=en |location=Cham |publisher=Springer International Publishing |pages=3–33 |arxiv=1901.10327 |doi=10.1007/978-3-319-99498-7_1 |isbn=978-3-319-99498-7|s2cid=52135244 }}</ref>

==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 are [[bijection|bijective]]. This means that reversible gates (and [[Circuit (computer science)|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, and that all input/output states are possible).

An [[inverter (logic gate)|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 <math>c\oplus (a\cdot b)</math>. With <math>c=0</math>, this gives the AND function, and with <math>a\cdot b=1</math> this gives the NOT function. Because AND and NOT together is a [[functional completeness|functionally complete]] set, the Toffoli gate is universal and can implement any [[Boolean function]] (if given enough initialized [[ancilla bit]]s).

Similarly, in the [[Turing machine]] model of computation, a reversible Turing machine is one whose transition function is invertible, so that each machine state has at most one predecessor.

[[:fr:Yves Lecerf|Yves Lecerf]] proposed a reversible Turing machine in a 1963 paper,<ref>Lecerf (Y.): [http://vadeker.net/corpus/reversible/lecerf.pdf Logique Mathématique : Machines de Turing réversibles.] Comptes rendus des séances de l'académie des sciences, 257: 2597–2600, 1963.</ref> but apparently unaware of Landauer's principle, did not pursue the subject further, devoting most of the rest of his career to ethnolinguistics. In 1973 [[Charles H. Bennett (physicist)|Charles H. Bennett]], at IBM Research, showed that a universal Turing machine could be made both logically and thermodynamically reversible,<ref>C. H. Bennett, "[http://www.dna.caltech.edu/courses/cs191/paperscs191/bennett1973.pdf Logical reversibility of computation]", IBM Journal of Research and Development, vol. 17, no. 6, pp. 525–532, 1973</ref> and therefore able in principle to perform an arbitrarily large number of computation steps per unit of physical energy dissipated, if operated sufficiently slowly. Thermodynamically reversible computers could perform useful computations at useful speed, while dissipating considerably less than ''[[kT (energy)|kT]]'' of energy per logical step. In 1982 [[Edward Fredkin]] and [[Tommaso Toffoli]] proposed the [[Billiard ball computer]], a mechanism using classical hard spheres to do reversible computations at finite speed with zero dissipation, but requiring perfect initial alignment of the balls' trajectories, and Bennett's review<ref>{{cite journal |last1=Bennett |first1=Charles H. |title=The thermodynamics of computation—a review |journal=International Journal of Theoretical Physics |date=December 1982 |volume=21 |issue=12 |pages=905–940 |doi=10.1007/BF02084158 |bibcode=1982IJTP...21..905B |s2cid=17471991 }}</ref> compared these "Brownian" and "ballistic" paradigms for reversible computation. Aside from the motivation of energy-efficient computation, reversible logic gates offered practical improvements of [[bit manipulation|bit-manipulation]] transforms in cryptography and computer graphics. Since the 1980s, reversible circuits have attracted interest as components of [[quantum algorithm]]s, and more recently in photonic and nano-computing technologies where some switching devices offer no [[signal gain]].

Surveys of reversible circuits, their construction and optimization, as well as recent research challenges, are available.<ref>Rolf Drechsler, Robert Wille. From Truth Tables to Programming Languages: Progress in the Design of Reversible Circuits. International Symposium on Multiple-Valued Logic, 2011. http://www.informatik.uni-bremen.de/agra/doc/konf/11_ismvl_reversible_circuit_design_tutorial.pdf</ref><ref>{{cite journal |last1=Saeedi |first1=Mehdi |last2=Markov |first2=Igor L. |title=Synthesis and optimization of reversible circuits—a survey |journal=ACM Computing Surveys |date=1 February 2013 |volume=45 |issue=2 |pages=1–34 |doi=10.1145/2431211.2431220 |arxiv=1110.2574 |s2cid=6302811 }}</ref><ref>Rolf Drechsler and Robert Wille. Reversible Circuits: Recent Accomplishments and Future Challenges for an Emerging Technology. International Symposium on VLSI Design and Test, 2012. http://www.informatik.uni-bremen.de/agra/doc/konf/2012_vdat_reversible_circuits_accompl_chall.pdf</ref><ref>{{cite journal |last1=Cohen |first1=Eyal |last2=Dolev |first2=Shlomi |last3=Rosenblit |first3=Michael |title=All-optical design for inherently energy-conserving reversible gates and circuits |journal=Nature Communications |date=26 April 2016 |volume=7 |issue=1 |pages=11424 |doi=10.1038/ncomms11424 |pmid=27113510 |pmc=4853429 |bibcode=2016NatCo...711424C }}</ref><ref>{{Cite journal|last1 =Ang|first1 = Y. S.|last2 = Yang|first2 = S. A.|last3 = Zhang|first3 = C.|last4 = Ma|first4 = Z. S.|last5 = Ang|first5 = L. K.|date = 2017|title = Valleytronics in merging Dirac cones: All-electric-controlled valley filter, valve, and universal reversible logic gate|journal = Physical Review B|volume = 96|issue = 24|pages = 245410|doi = 10.1103/PhysRevB.96.245410|arxiv = 1711.05906|bibcode = 2017PhRvB..96x5410A| s2cid=51933139 }}</ref>

==Commercialization==
[[London]]-based Vaire Computing is prototyping a chip in 2025, for release in 2027.<ref>{{cite journal |last1=Genkina |first1=Dina |last2=Potter |first2=Ned |last3=Ulrich |first3=Lawrence |last4=Bourzac |first4=Katherine |date=2025-01-01 |title=Reversible Computing Escapes the Lab: Startup Plans the First Chip Based on this Peculiar Power-Saving Scheme |url=https://spectrum.ieee.org/reversible-computing |journal=[[IEEE Spectrum]] |volume=62 |issue=1 |publisher=[[IEEE]] |pages=32–41 |doi=10.1109/MSPEC.2025.10829737}}</ref>

==See also==
{{cols|colwidth=26em}}
*{{annotated link|Adiabatic circuit}}
*{{annotated link|Bidirectional transformation}}
*{{annotated link|Billiard-ball computer}}
*{{annotated link|Fredkin gate}}
*{{annotated link|Generalized lifting}}
*{{annotated link|Janus (time-reversible computing programming language)}}
*{{annotated link|Maximum entropy thermodynamics}}, on the uncertainty interpretation of the second law of thermodynamics
*{{annotated link|Maxwell's demon}}
*{{annotated link|Reverse computation}}
*{{annotated link|Reversible cellular automaton}}
*{{annotated link|Reversible dynamics}}
*{{annotated link|Reversible process (thermodynamics)}}
*{{annotated link|Quantum computing}}
*{{annotated link|Quantum dot cellular automaton}}, a variant of reversible cellular automata
*{{annotated link|Toffoli gate}}
*{{annotated link|Superconducting quantum computing}}
*{{annotated link|Uncomputation}}
*{{annotated link|Unconventional computing}}
{{colend}}

==References==
{{reflist}}

==Further reading==
* Frank, Michael P. (2017). [https://spectrum.ieee.org/the-future-of-computing-depends-on-making-it-reversible "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]].
* {{cite journal |last1=Denning |first1=Peter |last2=Lewis |first2=Ted |title=Computers That Can Run Backwards |journal=American Scientist |date=2017 |volume=105 |issue=5 |pages=270 |doi=10.1511/2017.105.5.270 |s2cid=125446656|hdl=10945/59278 |hdl-access=free }}
* {{cite journal |last1=Glück |first1=Robert |last2=Yokoyama |first2=Tetsuo |title=Reversible computing from a programming language perspective |journal=Theoretical Computer Science |date=2023 |volume=953 |pages=113429 |doi=10.1016/j.tcs.2022.06.010 |doi-access=free }}
* {{cite journal |last1=Lange |first1=Klaus-Jörn |last2=McKenzie |first2=Pierre |last3=Tapp |first3=Alain |title=Reversible Space Equals Deterministic Space |journal=Journal of Computer and System Sciences |date=April 2000 |volume=60 |issue=2 |pages=354–367 |doi=10.1006/jcss.1999.1672 |doi-access=free }}
* Perumalla K. S. (2014), ''Introduction to Reversible Computing'', [[CRC Press]].
* {{cite book |doi=10.1145/1062261.1062335 |chapter=Time, space, and energy in reversible computing |title=Proceedings of the 2nd conference on Computing frontiers – CF '05 |year=2005 |last1=Vitányi |first1=Paul |pages=435–444 |isbn=1595930191 |s2cid=5252384}}

==External links==
* [http://strangepaths.com/reversible-computation/2008/01/20/en/ Introductory article on reversible computing]
* [http://www.eng.fsu.edu/~mpf/CF05/RC05.htm First International Workshop on reversible computing]
* Publications of Michael P. Frank: [https://www.sandia.gov/ccr/staff/michael-p-frank/ Sandia (2015-)], [https://web1.eng.famu.fsu.edu/~mpf/pubs.htm FSU (2004-'15)], [https://revcomp.info/legacy/revcomp/writing.html UF (1999-2004)], [https://revcomp.info/legacy/mpf/rc.html MIT 1996-'99]).
* [https://web.archive.org/web/20080626033214/http://revcomp.jot.com/WikiHome Internet Archive backup] of the "Reversible computing community Wiki" that was administered by Frank
* [http://www.reversible-computation.org/ Reversible Computation workshop/conference series]
* [https://cra.org/ccc/events/physics-engineering-issues-in-adiabatic-reversible-classical-computing/ CCC Workshop on Physics & Engineering Issues in Adiabatic/Reversible Classical Computing]
* [http://www.revkit.org/ Open-source toolkit for reversible circuit design]

{{Authority control}}

{{DEFAULTSORT:Reversible Computing}}
[[Category:Reversible computing| ]]
[[Category:Digital electronics]]
[[Category:Models of computation]]
[[Category:Thermodynamics]] <!-- replace with better variant -->