2002/12/11 by Kohtaro Tadaki, Tadaki, Kohtaro
Computer Science · Mathematics · Physics and Astronomy · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0212071
13 pages, LaTeX2e, no figures
arxiv created 2002/12/11 · openalex publication_date 2002/12/11 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 -log2 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.