Reversible computing

Last updated

Reversible computing is any model of computation where the computational process, to some extent, is time-reversible. In a model of computation that uses deterministic transitions from one state of the abstract machine to another, a necessary condition for reversibility is that the relation of the mapping from states to their successors must be one-to-one. Reversible computing is a form of unconventional computing.

Contents

Due to the unitarity of quantum mechanics, quantum circuits are reversible, as long as they do not "collapse" the quantum states on which they operate. [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. 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, [5] 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. [6]

Relation to thermodynamics

As was first argued by Rolf Landauer while working at IBM, [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 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. [9]

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 bijective. 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, and that all input/output states are possible).

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 . With , this gives the AND function, and with 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).

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.

Yves Lecerf proposed a reversible Turing machine in a 1963 paper, [10] 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, at IBM Research, showed that a universal Turing machine could be made both logically and thermodynamically reversible, [11] 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 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 [12] 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 transforms in cryptography and computer graphics. Since the 1980s, reversible circuits have attracted interest as components of quantum algorithms, 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. [13] [14] [15] [16] [17]

See also

Related Research Articles

<span class="mw-page-title-main">Logic gate</span> Device performing a Boolean function

A logic gate is a device that performs a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, one that has, for instance, zero rise time and unlimited fan-out, or it may refer to a non-ideal physical device.

<span class="mw-page-title-main">Quantum computing</span> Technology that uses quantum mechanics

A quantum computer is a computer that takes advantage of quantum mechanical phenomena.

Hypercomputation or super-Turing computation is a set of hypothetical models of computation that can provide outputs that are not Turing-computable. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that could correctly evaluate every statement in Peano arithmetic.

In logic circuits, the Toffoli gate, invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any classical reversible circuit can be constructed from Toffoli gates. It is also known as the "controlled-controlled-not" gate, which describes its action. It has 3-bit inputs and outputs; if the first two bits are both set to 1, it inverts the third bit, otherwise all bits stay the same.

An adder, or summer, is a digital circuit that performs addition of numbers. In many computers and other kinds of processors, adders are used in the arithmetic logic units (ALUs). They are also used in other parts of the processor, where they are used to calculate addresses, table indices, increment and decrement operators and similar operations.

<span class="mw-page-title-main">Quantum circuit</span> Model of quantum computing

In quantum information theory, a quantum circuit is a model for quantum computation, similar to classical circuits, in which a computation is a sequence of quantum gates, measurements, initializations of qubits to known values, and possibly other actions. The minimum set of actions that a circuit needs to be able to perform on the qubits to enable quantum computation is known as DiVincenzo's criteria.

In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate is a basic quantum circuit operating on a small number of qubits. Quantum logic gates are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.

<span class="mw-page-title-main">Rolf Landauer</span> American-German physicist, engineer (1927–1999)

Rolf William Landauer was a German-American physicist who made important contributions in diverse areas of the thermodynamics of information processing, condensed matter physics, and the conductivity of disordered media. Born in Germany, he emigrated to the U.S. in 1938, obtained a Ph.D. in physics from Harvard in 1950, and then spent most of his career at IBM.

<span class="mw-page-title-main">Charles H. Bennett (physicist)</span> American physicist, information theorist, and IBM Research fellow

Charles Henry Bennett is a physicist, information theorist and IBM Fellow at IBM Research. Bennett's recent work at IBM has concentrated on a re-examination of the physical basis of information, applying quantum physics to the problems surrounding information exchange. He has played a major role in elucidating the interconnections between physics and information, particularly in the realm of quantum computation, but also in cellular automata and reversible computing. He discovered, with Gilles Brassard, the concept of quantum cryptography and is one of the founding fathers of modern quantum information theory.

The Fredkin gate is a computational circuit suitable for reversible computing, invented by Edward Fredkin. It is universal, which means that any logical or arithmetic operation can be constructed entirely of Fredkin gates. The Fredkin gate is a circuit or device with three inputs and three outputs that transmits the first bit unchanged and swaps the last two bits if, and only if, the first bit is 1.

Landauer's principle is a physical principle pertaining to the lower theoretical limit of energy consumption of computation. It holds that an irreversible change in information stored in a computer, such as merging two computational paths, dissipates a minimum amount of heat to its surroundings.

The mathematical expressions for thermodynamic entropy in the statistical thermodynamics formulation established by Ludwig Boltzmann and J. Willard Gibbs in the 1870s are similar to the information entropy by Claude Shannon and Ralph Hartley, developed in the 1940s.

Unconventional computing is computing by any of a wide range of new or unusual methods. It is also known as alternative computing.

A chemical computer, also called a reaction-diffusion computer, Belousov–Zhabotinsky (BZ) computer, or gooware computer, is an unconventional computer based on a semi-solid chemical "soup" where data are represented by varying concentrations of chemicals. The computations are performed by naturally occurring chemical reactions.

<span class="mw-page-title-main">Boolean circuit</span> Model of computation

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length.

Quantum dot cellular automata are a proposed improvement on conventional computer design (CMOS), which have been devised in analogy to conventional models of cellular automata introduced by John von Neumann.

Adiabatic circuits are low-power electronic circuits which use "reversible logic" to conserve energy. The term "adiabatic" refers to an ideal thermodynamic process in which no heat or mass is exchanged with the surrounding environment, alluding to the ability of the circuits to reduce energy loss as heat.

<span class="mw-page-title-main">Ancilla bit</span> Extra bits required in reversible and quantum computation, as bits cannot be modified arbitrarily

In reversible computing, ancilla bits are extra bits being used to implement irreversible logical operations. In classical computation, any memory bit can be turned on or off at will, requiring no prior knowledge or extra complexity. However, this is not the case in quantum computing or classical reversible computing. In these models of computing, all operations on computer memory must be reversible, and toggling a bit on or off would lose the information about the initial value of that bit. For this reason, in a quantum algorithm there is no way to deterministically put bits in a specific prescribed state unless one is given access to bits whose original state is known in advance. Such bits, whose values are known a priori, are known as ancilla bits in a quantum or reversible computing task.

In quantum computing, a qubit is a unit of information analogous to a bit in classical computing, but it is affected by quantum mechanical properties such as superposition and entanglement which allow qubits to be in some ways more powerful than classical bits for some tasks. Qubits are used in quantum circuits and quantum algorithms composed of quantum logic gates to solve computational problems, where they are used for input/output and intermediate computations.

Dmitri Maslov is a Canadian-American computer scientist known for his work on quantum circuit synthesis and optimization, quantum advantage, and benchmarking quantum computers. Currently, he is the Chief Software Architect at IBM Quantum. Maslov was formerly a program director for Quantum Information Science at the National Science Foundation. He was named a Fellow of the Institute of Electrical and Electronics Engineers in 2021 "for contributions to quantum circuit synthesis and optimization, and compiling for quantum computers."

References

  1. ↑ Williams, Colin P. (2011). Explorations in Quantum Computing. Springer. pp. 25–29. ISBN   978-1-84628-887-6.
  2. ↑ "The Reversible and Quantum Computing Group (Revcomp)".
  3. ↑ Landauer, Rolf (1961), "Irreversibility and heat generation in the computing process" (PDF), IBM Journal of Research and Development, 5 (3): 183–191, doi:10.1147/rd.53.0183 , retrieved 2015-02-18, 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.
  4. ↑ J. von Neumann (1966). Theory of self-reproducing automata. University of Illinois Press. Retrieved 2022-05-21. Third lecture: Statistical Theories about Information
  5. ↑ Bérut, Antoine; Arakelyan, Artak; Petrosyan, Artyom; Ciliberto, Sergio; Dillenschneider, Raoul; Lutz, Eric (March 2012). "Experimental verification of Landauer's principle linking information and thermodynamics". Nature. 483 (7388): 187–189. arXiv: 1503.06537 . Bibcode:2012Natur.483..187B. doi:10.1038/nature10872. PMID   22398556. S2CID   9415026.
  6. ↑ 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).
  7. ↑ Landauer, R. (July 1961). "Irreversibility and Heat Generation in the Computing Process". IBM Journal of Research and Development. 5 (3): 183–191. doi:10.1147/rd.53.0183.
  8. ↑ Frank, Michael P.; Shukla, Karpur (June 1, 2021). "Quantum Foundations of Classical Reversible Computing". Entropy. 23 (6): 701. arXiv: 2105.00065 . Bibcode:2021Entrp..23..701F. doi: 10.3390/e23060701 . ISSN   1099-4300. PMC   8228632 . PMID   34206044.
  9. ↑ Frank, Michael P. (2018). "Physical Foundations of Landauer's Principle". In Kari, Jarkko; Ulidowski, Irek (eds.). Reversible Computation. Lecture Notes in Computer Science. Vol. 11106. Cham: Springer International Publishing. pp. 3–33. arXiv: 1901.10327 . doi:10.1007/978-3-319-99498-7_1. ISBN   978-3-319-99498-7. S2CID   52135244.
  10. ↑ Lecerf (Y.): Logique Mathématique : Machines de Turing réversibles. Comptes rendus des séances de l'académie des sciences, 257: 2597–2600, 1963.
  11. ↑ C. H. Bennett, "Logical reversibility of computation", IBM Journal of Research and Development, vol. 17, no. 6, pp. 525–532, 1973
  12. ↑ Bennett, Charles H. (December 1982). "The thermodynamics of computation—a review". International Journal of Theoretical Physics. 21 (12): 905–940. Bibcode:1982IJTP...21..905B. doi:10.1007/BF02084158. S2CID   17471991.
  13. ↑ 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
  14. ↑ Saeedi, Mehdi; Markov, Igor L. (1 February 2013). "Synthesis and optimization of reversible circuits—a survey". ACM Computing Surveys. 45 (2): 1–34. arXiv: 1110.2574 . doi:10.1145/2431211.2431220. S2CID   6302811.
  15. ↑ 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
  16. ↑ Cohen, Eyal; Dolev, Shlomi; Rosenblit, Michael (26 April 2016). "All-optical design for inherently energy-conserving reversible gates and circuits". Nature Communications. 7 (1): 11424. Bibcode:2016NatCo...711424C. doi:10.1038/ncomms11424. PMC   4853429 . PMID   27113510.
  17. ↑ Ang, Y. S.; Yang, S. A.; Zhang, C.; Ma, Z. S.; Ang, L. K. (2017). "Valleytronics in merging Dirac cones: All-electric-controlled valley filter, valve, and universal reversible logic gate". Physical Review B. 96 (24): 245410. arXiv: 1711.05906 . Bibcode:2017PhRvB..96x5410A. doi:10.1103/PhysRevB.96.245410. S2CID   51933139.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.