Prefix-free quantum Kolmogorov complexity

Abstract

We introduce quantum-K ($QK$), a measure of the descriptive complexity of density matrices using classical prefix-free Turing machines and show that the initial segments of weak Solovay random and quantum Schnorr random states are incompressible in the sense of $QK$. Many properties enjoyed by prefix-free Kolmogorov complexity ($K$) have analogous versions for $QK$; notably a counting condition. Several connections between Solovay randomness and $K$, including the Chaitin type characterization of Solovay randomness, carry over to those between weak Solovay randomness and $QK$. We work towards a Levin-Schnorr type characterization of weak Solovay randomness in terms of $QK$. Schnorr randomness has a Levin-Schnorr characterization using $K_C$; a version of $K$ using a computable measure machine, $C$. We similarly define $Q{K}_C$, a version of $QK$. Quantum Schnorr randomness is shown to have a Levin-Schnorr and a Chaitin type characterization using $Q{K}_C$. The latter implies a Chaitin type characterization of classical Schnorr randomness using $K_C$.

arXiv comment21 pages. This has been submitted to a journal

References in corpus (8)

• Quantum Kolmogorov Complexity
• Quantum Kolmogorov Complexity Based on Classical Descriptions
• Value-indefinite observables are almost everywhere
• Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno's Theorem
• Quantum algorithmic information theory
• A Quantum Random Number Generator Certified by Value Indefiniteness
• Quantum Kolmogorov Complexity and the Quantum Turing Machine
• Quantum algorithmic randomness

Cited by in corpus (4)

• Kolmogorov complexity as intrinsic entropy of a pure state: Perspective from entanglement in free fermion systems
• Quantum algorithmic randomness
• Algorithmic Randomness and Kolmogorov Complexity for Qubits
• Von Neumann Entropy and Quantum Algorithmic Randomness