This paper proposes an extension of Chaitin's halting probability 0to measurement operator in aan infinite dimensional quantum system.Chaitin's Ω 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 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 ΠL is introduced first, and then H(s) is defined as −log2m(IF) 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 Ω numbers by universal probabilities.Then, based on this characterization, we propose to define an extension of Ω 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 compl6ffi˙∈y (or Kolmogorov complez- i˙ty)H{s ) of afinite binary string s , which is defined as the length of the shortest binary input
We apply algorithmic information theory to quantum mechanics in order to shed light on an algorithmic structure which inheres in quantum mechanics. There are two equivalent ways to define the (classical) Kolmogorov complexity K(s) of a given classical finite binary string s. In the standard way, K(s) is defined as the length of the shortest input string for the universal self-delimiting Turing machine to output s. In the other way, we first introduce the so-called universal probability m, and then define K(s) as -log_2 m(s) without using the concept of program-size. We generalize the universal probability to a matrix-valued function, and identify this function with a POVM (positive operator-valued measure). On the basis of this identification, we study a computable POVM measurement with countable measurement outcomes performed upon a finite dimensional quantum system. We show that, up to a multiplicative constant, 2^{-K(s)} is the upper bound for the probability of each measurement outcome s in such a POVM measurement. In what follows, the upper bound 2^{-K(s)} is shown to be optimal in a certain sense.
We apply algorithmic information theory to quantum mechanics in order to shed light on an algorithmic structure which is inherent in quantum mechanics.There are two equivalent ways to define the (classical) Kolmogorov ∞mplexityK(s) of agiven classical finite binary string s .In the standard way, K(s) is defined as the length of the shortest input string for the universal self-delimiting Turing machine to output s .In the other way, we first introduce the so-called universal probability m , and then define K(s) as −log2m(s) without using the concept of program-size.We generalize the universal probability to amatrix-valued function, and identify this function with apositive operator-valued measure (POVM), which describes the statistics of outcomes in aquantum measurement in the general set- ting.Based on this identification, we study acomputable POVM measurement with countable measurement outcomes performed upon afinite dimensional quantum system.We show that, up to amultiplicative constant, 2−K(s) is the upper bound for the probability of each measurement outcome s in such aquantum measurement.In what follows, the upper bound 2−K(s) is shown to be optimal in acertain sense.
Contrary to the classical case, the relation between quantum programming languages and quantum Turing Machines (QTM) has not been fully investigated. In particular, there are features of QTMs that have not been exploited, a notable example being the intrinsic infinite nature of any quantum computation. In this paper, we propose a definition of QTM, which extends and unifies the notions of Deutsch and Bernstein & Vazirani. In particular, we allow both arbitrary quantum input, and meaningful superpositions of computations, where some of them are “terminated” with an “output”, while others are not. For some infinite computations an “output” is obtained as a limit of finite portions of the computation. We propose a natural and robust observation protocol for our QTMs, which does not modify the probability of the possible outcomes of the machines. Finally, we use QTMs to define a class of quantum computable functions—any such function is a mapping from a general quantum state to a probability distribution of natural numbers. We expect that our class of functions, when restricted to classical input-output, will not be different from the set of the recursive functions.
The purpose of this thesis is to give a formal definition of quantum Kolmogorov complexity (QC), and rigorous mathematical proofs of its basic properties. The definition used here is similar to that by Berthiaume, van Dam, and Laplante. It defines the QC of some indeterminate-length qubit string ρas the minimum base length of any quantum input which makes a quantum Turing machine (QTM) halt and output ρ, up to some error tolerance. First, we prove that there is a QTM which is universal in the sense of input base length. Furthermore, we show several general properties of QTMs, including a result on mutually orthogonal ``halting spaces'', and a way to transform every almost-halting input into a deterministically-halting input by adding at most a constant number of qubits. Afterwards, we apply these results to QC. In particular, we show that QC is invariant, incompressible, agrees with classical Kolmogorov complexity for classical strings, and is closely related to von Neumann entropy for ergodic quantum information sources.
In the quantum theory of measurement, the positive operator-valued measure (POVM) is an important concept, and its implementation can be useful. A POVM consists of a set of non-negative quantum-mechanical Hermitian operators that add up to the identity. The probability that a quantum system is in a particular state is given by the expectation value of the POVM operator corresponding to that state. Following a brief review of the mathematics and mention of the history of POVMs in quantum theory, a particular implementation of a POVM for use in the measurement of nonorthogonal photon polarization states is reviewed. The implementation consists simply of a Wollaston prism, a mirror, two beam splitters, a polarization rotator and three phototubes arranged in an interferometric configuration, and it is shown analytically that the device faithfully represents the POVM. Based on Neumark's extension theorem, the two-dimensional Hilbert space of the POVM implementation can be embedded in the three-dimensional Hilbert space of an ordinary projective-valued measure. Also, analytical expressions are given for the maximum Renyi information loss from the device to a disturbing probe, and for the error and inconclusive rates induced by the probe. Various aspects of the problem of probe optimization are elaborated.