nLab reversible computation

Redirected from "reversible computing".

Contents

Context

Computing

Idea
Related concepts
References

Idea

In as far as a computation is a function from input data to output result, a reversible computation is an invertible function, where the input may be recovered from knowledge of the output. More generally, as far as a computation is any morphism (under the computational trilogy), a reversible computation is an isomorphism.

Typical operations of a classical computer are not reversible: For example standard logical gates such as AND, XOR etc. are functions of the form $\{0,1\}^2 \longrightarrow \{0,1\}$ and as such not invertible. Standard classical gates which are invertible include the NOT-gate $\{0,1\} \xrightarrow{\sim} \{0,1\}$ (which switches its single input bit) and the CNOT-gate $\{0,1\}^2 \xrightarrow{\sim} \{0,1\}^2$ (which keeps the first “control” bit and switches the second bit if the first equals 1).

Using just these reversible NOT- and CNOT-gates one may for instance implement the operation of incremental addition $(-)+n \;\colon\; \mathbb{Z} \xrightarrow{\sim} \mathbb{Z}$ by a fixed natural number $n$ (e.g. Kaye 2004). As opposed to binary addition $(-) + (-) \,\colon\, \mathbb{Z}^2 \xrightarrow{\;} \mathbb{Z}$ , this operation is invertible, the inverse being the corresponding incremental subtraction $(-)-n \;\colon\; \mathbb{Z} \xrightarrow{\sim} \mathbb{Z}$ .

This state of affairs was reflected, for instance, in Gottfried Leibniz‘s stepped reckoner machine, which performs incremental addition when its crank is turned in one direction, and the inverse incremental subtraction when the crank is turned back in the opposite direction.

But the NOT- and CNOT-gates by themselves are not universal. On the other hand, the CCNOT gate $\{0,1\}^3 \xrightarrow{\sim} \{0,1\}^3$ (which regards the first two inputs as control bits and switches the third input if these two are both 1) is both invertible as well as universal (e.g. Nielsen & Chuang 2000, §1.4.1), in that any function of the form $\{0,1\}^{n_1} \xrightarrow{\;} \{0,1\}^{n_2}$ is equal to a circuit of CCNOT gates pre-composed with some cartesian power of $\{0\} \xhookrightarrow{\;} \{0,1\}$ (introducing auxiliary “bath” or “ancilla” bits) and post-composed with some cartesian power of $\{0,1\} \to \ast$ (deleting auxiliary bits). In other words: Every irreversible classical computation on some computing system may be understood as a reversible computation on the system coupled to an ambient “bath” together with a loss of information of computation output into this bath.

Indeed, in terms of physical implementation of computation, the distinction between reversible and irreversible computation is essentially that of reversible or irreversible dynamical processes as known from thermodynamics: Fundamentally and under idealized conditions, physical processes are invertible, but “at finite temperature” there is entropy-increase associated with most processes, making them irreversible. This relation between (non-)reversible computation and thermodynamics is known as Landauer’s principle (due to Landauer 1961, review e.g. in Nielsen & Chuang 2000, §3.2.5).

While the notion of reversible computation was originally conceived in the context of classical computation, more recently its key example is understood to be quantum computation: Here the logical gates (excluding the final quantum measurement which collapses the quantum state) are linear functions which are unitary operator and hence necessarily invertible (see Frank 2003 for emphasis).

Therefore, the practical problem of implementing quantum computation faces analogous thermodynamical issues as embodied by Landauer’s principle, which are the reason for the need of quantum error correction and/or topological quantum stabilization.

Related concepts

References

Original articles:

Rolf Landauer, Irreversibility and Heat Generation in the Computing Process, IBM Journal of Research and Development 5 3 (1961) 183–191 [doi:10.1147%2Frd.53.0183]
Charles H. Bennett, Logical Reversibility of Computation, IBM Journal of Research and Development 17 6 (1973) [doi:10.1147/rd.176.0525]

Review:

Charles H. Bennett, The thermodynamics of computation – a review, International Journal of Theoretical Physics 21 (1982) 905–940 [doi:10.1007/BF02084158]
Rolf Landauer, Charles H. Bennett: The Fundamental Physical Limits of Computation, Scientific American 253 1 (1985)
Rolf Landauer: Computation: A Fundamental Physical View, Phys. Scr. 35 (1987) 88 [doi:10.1088/0031-8949/35/1/021]
Charles H. Bennett, Notes on the history of reversible computation, IBM Journal of Research and Development 32 1 (1988) [doi:10.1147/rd.321.0016]
Charles H. Bennett, Notes on Landauer’s principle, reversible computation, and Maxwell’s Demon, Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics, 34 3 (2003) 501-510 (doi:10.1016/S1355-2198(03)00039-X)

Review of current developments (as of 2020):

B. Aman et al., Foundations of Reversible Computation, in: Reversible Computation: Extending Horizons of Computing. RC 2020 Lecture Notes in Computer Science 12070, Springer (2020) [doi:10.1007/978-3-030-47361-7_1]