Chaitin's halting probabiliy Ω and quantum measurements in an infinite dimensional quantum system (計算機科学基礎理論とその応用 研究集会報告集)

Zhoubo Duan, Jinchuan Hou

暢宏 浅井

Kohtaro Tadaki

Abstract This paper proposes an extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system. Chaitin's Ω is defined as the probability that the universal self‐delimiting Turing machine U halts, and plays a central role in the development of algorithmic information theory. In the theory, there are two equivalent ways to define the program‐size complexity H (s) of a given finite binary string s. In the standard way, H (s) is defined as the length of the shortest input string for U to output s. In the other way, the so‐called universal probability m is introduced first, and then H (s) is defined as –log2 m (s) without reference to the concept of program‐size. Mathematically, the statistics of outcomes in a quantum measurement are described by a positive operator‐valued measure (POVM) in the most general setting. Based on the theory of computability structures on a Banach space developed by Pour‐El and Richards, we extend the universal probability to an analogue of POVM in an infinite dimensional quantum system, called a universal semi‐POVM. We also give another characterization of Chaitin's Ω numbers by universal probabilities. Then, based on this characterization, we propose to define an extension of Ω as a sum of the POVM elements of a universal semi‐POVM. The validity of this definition is discussed. In what follows, we introduce an operator version $ \hat H $(s) of H (s) in a Hilbert space of infinite dimension using a universal semi‐POVM, and study its properties. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

Tadaki, Kohtaro

This paper proposes an extension of Chaitin's halting probability 0to measurement operator in $\mathrm{a}\mathrm{a}\mathrm{n}$ infinite dimensional quantum system.Chaitin's $\Omega$ is defined as the probability that the universal self-delimiting Turing machine $U$ halts, and plays acentral role in the development of algorithmic information theory.Iri the theory, there are two equivalent ways to define the program-size complexity $H(s)$ of agiven finite binary string $\mathrm{s}$ .In the standard way, $H(s)$ is defined as the length of the shortest input string for $U$ to output 8.In the other way, the s0-called universal probability $\Pi \mathrm{L}$ is introduced first, and then $H(s)$ is defined as $-\log_{2}m(\mathrm{I}\mathrm{F})$ without reference to the concept of program-size.Mathematically, the statistics of outcomes in aquantum measurement are described by apositive operator-valued measure (POVM) in the most general setting.Based on the theory of computability structures on aBanach space developed by Pour-El and Richards, we extend the universal probability to an analogue of POVM in an infinite dimensional quantum system, called universal semi-POVM.We also give another characterization of Chaitin's $\Omega$ numbers by universal probabilities.Then, based on this characterization, we propose to define an extension of $\Omega$ as asum of the POVM elements of auniversal semi-POVM.The validity of this definition is discussed.1Introduction Algorithmic information theory is afiamework to apply information-theoretic and probabilistic ideas to recursive function theory.One of the primary concepts of algorithmic information theory is the program-size $compl_{6\mathrm{f}\mathrm{f}\dot{i}}\not\in y$ (or Kolmogorov complez- $\dot{i}ty)\mathrm{H}\{\mathrm{s}$ ) of afinite binary string $s$ , which is defined as the length of the shortest binary input

Karl Svozil

The classical halting probability introduced by Chaitin is generalized to quantum computations. (The quantum omega was invented in a meeting of G. Chaitin, A. Zeilinger and the author (K. S.) in a Viennese coffee house (Cafe Braeunerhof) in January 1991. Thus, the group should be credited for the original invention, whereas any blame should remain with the author.)

Detlev Buchholz A, Erling Størmer