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

Kolmogorov complexity upper bound of probability in computable POVM measurement (New Aspects of Theoretical Computer Science)

Kohtaro Tadaki

Published May 1, 2003• 0 citations
OpenAlex

Abstract

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 $\infty \mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{x}\mathrm{i}\mathrm{t}\mathrm{y}$ $K(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 $-\log_{2}m(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.

Related papers

Upper bound by Kolmogorov complexity for the probability in computable POVM measurement

Kohtaro Tadaki

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.

arXiv:quant-ph/0212071•Dec 11, 2002•6 citations

Chaitin's halting probability $\Omega$ and quantum measurements in an infinite dimensional quantum system (Theoretical Computer Science and its Applications)

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

•Apr 1, 2005•0 citations

Quantum Kolmogorov Complexity and the Quantum Turing Machine

Markus P. Müller

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.

arXiv:0712.4377•Dec 28, 2007•14 citations

Quantum Kolmogorov complexity

A. Berthiaume, Wim van Dam, Sophie Laplante

In this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can produce this string as its output. It is a measure of the amount of innate randomness (or information) contained in the string. We define the quantum Kolmogorov complexity of a qubit string as the length of the shortest quantum input to a universal quantum Turing machine that produces the initial qubit string with high fidelity. The definition of P. Vitanyi (2000) measures the amount of classical information, whereas we consider the amount of quantum information in a qubit string. We argue that our definition is natural and is an accurate representation of the amount of quantum information contained in a quantum state.

IEEE Conference on Computational Complexity (CCC)•Nov 7, 2002•17 citations

ALGORITHMIC COMPLEXITY OF QUANTUM STATES

Caterina E. Mora, Hans J. Briegel

We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of "how difficult" it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of known states. Furthermore, we establish a connection between the entanglement of a quantum state and its algorithmic complexity.

arXiv:quant-ph/0412172•International Journal of Quantum Information•Aug 1, 2006•24 citations

Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity

Morteza Saberikamarposhti

We initiate the time-bounded meta-complexity program for quantum cryptography. Recent work characterizes one-way puzzles, the minimal search primitive of quantum cryptography without one-way functions, by the average-case hardness of approximating the plain, uncomputable Kolmogorov complexity over quantumly samplable distributions; the classical program of Liu and Pass, by contrast, lives at polynomial time bounds. We define a probabilistic time-bounded quantum program complexity pKq^t for classical strings and prove two unconditional theorems. First, a quantum coding theorem: any string output by a quantum polynomial-time sampler with probability delta admits a description of the information-theoretically optimal length log(1/delta) plus logarithmic terms, decodable by a quantum machine in time O(sqrt(1/delta)) times a polynomial, via amplitude amplification over the coherently executed sampler. Second, an exact characterization at subexponential time: one-way puzzles exist if and only if the gap problem for pKq at time bound 2^(n/2) poly(n) is weakly quantum-average-hard, refining the plain-complexity characterizations. We then isolate the polynomial-time coding theorem as the single load-bearing open conjecture of the program, prove that it implies the full polynomial-time characterization, analyze why the classical derandomization proof resists quantization, and formulate a relativized barrier conjecture delimiting string-valued meta-complexity at one-way puzzles. Conjectures are labeled as such throughout.

quant-pharXiv:2609.02687•Sep 3, 2026•0 citations
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 ∞mplexity\infty \mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{x}\mathrm{i}\mathrm{t}\mathrm{y}∞mplexity K(s)K(s)K(s) of agiven classical finite binary string sss .In the standard way, K(s)K(s)K(s) is defined as the length of the shortest input string for the universal self-delimiting Turing machine to output sss .In the other way, we first introduce the so-called universal probability mmm , and then define K(s)K(s)K(s) as −log⁡2m(s)-\log_{2}m(s)−log2​m(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)2^{-K(s)}2−K(s) is the upper bound for the probability of each measurement outcome sss in such aquantum measurement.In what follows, the upper bound 2−K(s)2^{-K(s)}2−K(s) is shown to be optimal in acertain sense.
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.
Chaitin's halting probability Ω\OmegaΩ and quantum measurements in an infinite dimensional quantum system (Theoretical Computer Science and its Applications)
This paper proposes an extension of Chaitin's halting probability 0to measurement operator in aan\mathrm{a}\mathrm{a}\mathrm{n}aan infinite dimensional quantum system.Chaitin's Ω\OmegaΩ is defined as the probability that the universal self-delimiting Turing machine UUU 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)H(s)H(s) of agiven finite binary string s\mathrm{s}s .In the standard way, H(s)H(s)H(s) is defined as the length of the shortest input string for UUU to output 8.In the other way, the s0-called universal probability ΠL\Pi \mathrm{L}ΠL is introduced first, and then H(s)H(s)H(s) is defined as −log⁡2m(IF)-\log_{2}m(\mathrm{I}\mathrm{F})−log2​m(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 Ω\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 compl6ffi˙∉ycompl_{6\mathrm{f}\mathrm{f}\dot{i}}\not\in ycompl6ffi˙​∈y (or Kolmogorov complez- i˙ty)H{s\dot{i}ty)\mathrm{H}\{\mathrm{s}i˙ty)H{s ) of afinite binary string sss , which is defined as the length of the shortest binary input
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 this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can produce this string as its output. It is a measure of the amount of innate randomness (or information) contained in the string. We define the quantum Kolmogorov complexity of a qubit string as the length of the shortest quantum input to a universal quantum Turing machine that produces the initial qubit string with high fidelity. The definition of P. Vitanyi (2000) measures the amount of classical information, whereas we consider the amount of quantum information in a qubit string. We argue that our definition is natural and is an accurate representation of the amount of quantum information contained in a quantum state.
We give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory, the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of "how difficult" it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of known states. Furthermore, we establish a connection between the entanglement of a quantum state and its algorithmic complexity.
We initiate the time-bounded meta-complexity program for quantum cryptography. Recent work characterizes one-way puzzles, the minimal search primitive of quantum cryptography without one-way functions, by the average-case hardness of approximating the plain, uncomputable Kolmogorov complexity over quantumly samplable distributions; the classical program of Liu and Pass, by contrast, lives at polynomial time bounds. We define a probabilistic time-bounded quantum program complexity pKq^t for classical strings and prove two unconditional theorems. First, a quantum coding theorem: any string output by a quantum polynomial-time sampler with probability delta admits a description of the information-theoretically optimal length log(1/delta) plus logarithmic terms, decodable by a quantum machine in time O(sqrt(1/delta)) times a polynomial, via amplitude amplification over the coherently executed sampler. Second, an exact characterization at subexponential time: one-way puzzles exist if and only if the gap problem for pKq at time bound 2^(n/2) poly(n) is weakly quantum-average-hard, refining the plain-complexity characterizations. We then isolate the polynomial-time coding theorem as the single load-bearing open conjecture of the program, prove that it implies the full polynomial-time characterization, analyze why the classical derandomization proof resists quantization, and formulate a relativized barrier conjecture delimiting string-valued meta-complexity at one-way puzzles. Conjectures are labeled as such throughout.