Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic Notes in Theoretical Computer Science

From Reversible to Irreversible Computations

Alexander S. Green, Thorsten Altenkirch

Published Jul 1, 2008• 15 citations
Publisher

Abstract

In this paper we study the relation between reversible and irreversible computation applicable to different models of computation — here we are considering classical and quantum computation. We develop an equational theory of reversible computations and an associated theory of irreversible computations which is obtained by marking some inputs as preinitialised heap and some outputs as garbage to be thrown away at the end of the computation. We present three laws which apply to irreversible classical and quantum computations and show that von Neumann's measurement postulate is derivable from them. We discuss the question whether these laws are complete for irreversible quantum computations.

DOI
10.1016/j.entcs.2008.04.018

Related papers

Reversibility and Irreversibility within the Quantum Formalism

T. J. Jacobs, Christian Maes

The discussion on time-reversal in quantum mechanics exists at least since Wigner's ``Uber die Operation der Zeitumkehr in der Quantenmechanik'' paper in 1932. If and how the dynamics of the quantum world is time-reversible has been the subject of many controversies. Some have seen quantum mechanics as fundamentally time-irreversible, see for example von Neumann, and some have seen in that the ultimate cause of time's arrow and second law behavior. In his best-selling book ``The Emperor's New Mind'', Roger Penrose argues similarly and concludes that ``our sought-for quantum gravity must be a time-asymmetric theory'' [p.351]. Not so long ago, we read yet about another project in Physicalia 26: to extend quantum mechanics into new fundamentally irreversible equations, thus proposing a new theory giving ``... une description fondamentale irreversible de tout systeme physique''.

arXiv:quant-ph/0508041•Aug 4, 2005•4 citations

Quantum logic as reversible computing

Basil Evangelidis

The relation between entropy and information has great significance for computation. Based on the strict reversibility of the laws of microphysics, Landauer (1961), Bennett (1973), Priese (1976), Fredkin and Toffoli (1982), Feynman (1985) and others envisioned a reversible computer that cannot allow any ambiguity in backward steps of a calculation. It is this backward capacity that makes reversible computing radically different from ordinary, irreversible computing. The proposal aims at a higher kind of computer that would give the actual output of a computation together with the original input, with the absence of a minimum energy requirement. Hence, information retrievability and energy efficiency due to diminished heat dissipation are the exquisite tasks of quantum computer technology.

arXiv:2111.07431•Nov 14, 2021•0 citations

Irreversibility, equilibrium and measurement in quantum mechanics

Christopher J. N. Coveney, Peter V. Coveney

Quantum mechanics is widely recognised as being incomplete. It is not consistent with the second law of thermodynamics and does not provide a scientifically credible physical account of the measurement process, the means by which coherence is broken and classically observable states are recorded. This has led to many ad hoc assumptions being used to account for various properties of quantum systems, among which is the coherence time of quantum devices that determines their ability to perform computations. Here, we show that all these properties can be accommodated naturally and consistently in the context of mixing quantum systems which exhibit continuous spectra, as arises in the thermodynamic limit in quantum statistical mechanics and quantum gravity. In particular, for isolated systems we show that the time-reversal symmetry associated with unitary time evolution of the quantum state gives rise to time-symmetry breaking and a semi-group evolution which attains thermodynamic equilibrium at long times. Moreover, the emergence of this non-unitary time-asymmetry leads to microcanonical equilibrium states in which all quantum coherence is lost and is accompanied by the transformation of pure states into mixtures, leading in turn to an increase in entropy. Inclusion of a macroscopic measurement apparatus shows how the outcome of a measurement corresponds to the von Neumann projection postulate, arising with probabilities in conformance with the Born rule. The mathematical structure of the theory which applies to quantum systems with continuous spectra is closely analogous to the classical ergodic theory of dynamical systems and the conditions under which they attain equilibrium states.

quant-pharXiv:2607.19142•Jul 22, 2026•0 citations

Measurement Problem

Gennaro Auletta, Shang-Yung Wang

In this chapter we shall consider one of the most difficult problems of quantum mechanics, that is, how it is possible that we have a dynamics ruled by a reversible equation but we obtain random irreversible events when measuring. Many different interpretations have been provided for solving this puzzle. We will discuss some of them by starting with the von Neumann’s projection postulate, one of the first attempts to address the measurement problem and its implications. The role played by the environment in the concept of measurement is then emphasized. We shall also introduce entropy as a measure of the average information content. Finally, the famous Schro¨dinger’s cat paradox will be examined.

•Jun 20, 2014•0 citations

Quantum information effects

Chris Heunen, Robin Kaarsgaard

We study the two dual quantum information effects to manipulate the amount of information in quantum computation: hiding and allocation. The resulting type-and-effect system is fully expressive for irreversible quantum computing, including measurement. We provide universal categorical constructions that semantically interpret this arrow metalanguage with choice, starting with any rig groupoid interpreting the reversible base language. Several properties of quantum measurement follow in general, and we translate (noniterative) quantum flow charts into our language. The semantic constructions turn the category of unitaries between Hilbert spaces into the category of completely positive trace-preserving maps, and they turn the category of bijections between finite sets into the category of functions with chosen garbage. Thus they capture the fundamental theorems of classical and quantum reversible computing of Toffoli and Stinespring.

arXiv:2107.12144•Proceedings of the ACM on Programming Languages•Jan 12, 2022•1 citation

Remarks on the Halting problem, unitarity and reversibility in quantum theory of computations

Alexander Shalyt-Margolin, A. Ya. Tregubovich, В. И. Стражев

The Halting problem for the quantum computer is considered. It is shown, that if the halting for the quantum computer takes place then the corresponding dynamics is described by an irreversible operator.

•Jun 19, 2001•0 citations
In this paper we study the relation between reversible and irreversible computation applicable to different models of computation — here we are considering classical and quantum computation. We develop an equational theory of reversible computations and an associated theory of irreversible computations which is obtained by marking some inputs as preinitialised heap and some outputs as garbage to be thrown away at the end of the computation. We present three laws which apply to irreversible classical and quantum computations and show that von Neumann's measurement postulate is derivable from them. We discuss the question whether these laws are complete for irreversible quantum computations.
The discussion on time-reversal in quantum mechanics exists at least since Wigner's ``Uber die Operation der Zeitumkehr in der Quantenmechanik'' paper in 1932. If and how the dynamics of the quantum world is time-reversible has been the subject of many controversies. Some have seen quantum mechanics as fundamentally time-irreversible, see for example von Neumann, and some have seen in that the ultimate cause of time's arrow and second law behavior. In his best-selling book ``The Emperor's New Mind'', Roger Penrose argues similarly and concludes that ``our sought-for quantum gravity must be a time-asymmetric theory'' [p.351]. Not so long ago, we read yet about another project in Physicalia 26: to extend quantum mechanics into new fundamentally irreversible equations, thus proposing a new theory giving ``... une description fondamentale irreversible de tout systeme physique''.
The relation between entropy and information has great significance for computation. Based on the strict reversibility of the laws of microphysics, Landauer (1961), Bennett (1973), Priese (1976), Fredkin and Toffoli (1982), Feynman (1985) and others envisioned a reversible computer that cannot allow any ambiguity in backward steps of a calculation. It is this backward capacity that makes reversible computing radically different from ordinary, irreversible computing. The proposal aims at a higher kind of computer that would give the actual output of a computation together with the original input, with the absence of a minimum energy requirement. Hence, information retrievability and energy efficiency due to diminished heat dissipation are the exquisite tasks of quantum computer technology.
Quantum mechanics is widely recognised as being incomplete. It is not consistent with the second law of thermodynamics and does not provide a scientifically credible physical account of the measurement process, the means by which coherence is broken and classically observable states are recorded. This has led to many ad hoc assumptions being used to account for various properties of quantum systems, among which is the coherence time of quantum devices that determines their ability to perform computations. Here, we show that all these properties can be accommodated naturally and consistently in the context of mixing quantum systems which exhibit continuous spectra, as arises in the thermodynamic limit in quantum statistical mechanics and quantum gravity. In particular, for isolated systems we show that the time-reversal symmetry associated with unitary time evolution of the quantum state gives rise to time-symmetry breaking and a semi-group evolution which attains thermodynamic equilibrium at long times. Moreover, the emergence of this non-unitary time-asymmetry leads to microcanonical equilibrium states in which all quantum coherence is lost and is accompanied by the transformation of pure states into mixtures, leading in turn to an increase in entropy. Inclusion of a macroscopic measurement apparatus shows how the outcome of a measurement corresponds to the von Neumann projection postulate, arising with probabilities in conformance with the Born rule. The mathematical structure of the theory which applies to quantum systems with continuous spectra is closely analogous to the classical ergodic theory of dynamical systems and the conditions under which they attain equilibrium states.
In this chapter we shall consider one of the most difficult problems of quantum mechanics, that is, how it is possible that we have a dynamics ruled by a reversible equation but we obtain random irreversible events when measuring. Many different interpretations have been provided for solving this puzzle. We will discuss some of them by starting with the von Neumann’s projection postulate, one of the first attempts to address the measurement problem and its implications. The role played by the environment in the concept of measurement is then emphasized. We shall also introduce entropy as a measure of the average information content. Finally, the famous Schro¨dinger’s cat paradox will be examined.
We study the two dual quantum information effects to manipulate the amount of information in quantum computation: hiding and allocation. The resulting type-and-effect system is fully expressive for irreversible quantum computing, including measurement. We provide universal categorical constructions that semantically interpret this arrow metalanguage with choice, starting with any rig groupoid interpreting the reversible base language. Several properties of quantum measurement follow in general, and we translate (noniterative) quantum flow charts into our language. The semantic constructions turn the category of unitaries between Hilbert spaces into the category of completely positive trace-preserving maps, and they turn the category of bijections between finite sets into the category of functions with chosen garbage. Thus they capture the fundamental theorems of classical and quantum reversible computing of Toffoli and Stinespring.