Reversible computing: Difference between revisions

Revision as of 19:08, 16 March 2022

Revision as of 19:09, 16 March 2022

Line 29:

==Logical reversibility==

Logical reversibility means that the output can be computed from the input, and vice versa. This implies [[bijection]]. In this modeling framework, anAn [[inverter (logic gate)|inverter]] (NOT) gate is logically reversible because it can be ''undone''. The [[exclusive or]] (XOR) gate is irreversible because its two inputs cannot be unambiguously reconstructed from its single output, 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. 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. Thus, the Toffoli gate is universal and can implement any reversible [[Boolean function]] (given enough zero-initialized [[Ancilla bit|ancillary bits]]). More generally, reversible gates that consume their input have no more inputs than outputs. A reversible circuit connects reversible gates without [[fanout]]s and loops. Therefore, such circuits contain equal numbers of input and output wires, each going through an entire circuit. 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'' 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 }}</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]].