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.
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.
This short note is closer to an annotated bibliography, than to a real review. We allude to reversible computation, but do not repeat the many existing discussions. We point out that minimal energy dissipation requirements in classical measurement and in the communications channel are now understood as a result of the insights gained from the studies of reversible computation. In all three areas (computation, communication, and measurement) dissipation can be made as small as desired, per step, as long as information is not discarded. Erasure of information is not essential in computation or communication, but is needed to reset the meter after measurement. We speculate on the implications for physical law, arising from the likely limited computational recision available in the universe. We become even more speculative, and suggest that the ultimate physical laws, as a result of their limited precision, have something akin to a built-in noise source, and that this is the ultimate source of irreversibility.
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.