Reversible computing: Difference between revisions

Content deleted Content added
(minor) typo broke formatting
m +{{Authority control}} (3 IDs from Wikidata); WP:GenFixes & cleanup on
Line 10:
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 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_26 2]] Preprint available at https://www.osti.gov/servlets/purl/1456440 (PDF).</ref>
 
==Relation to thermodynamics==
Line 29:
 
==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).
Line 82:
* [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}}