Prefix-free quantum Kolmogorov complexity

DOI10.1016/J.TCS.2021.05.017MaRDI QIDQ2034780zbMATH OpenOpenAlexFDO

Authors Tejas Bhojraj

Publication date 23 June 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.11686

zbMATH Keywords

density matrixKolmogorov complexityMartin-Löf randomnessprefix-free Turing machinequbitSchnorr randomness

Mathematics Subject Classification ID

Classical models of computation (Turing machines, etc.) (68Q04) Quantum algorithms and complexity in the theory of computing (68Q12) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

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$.

Recommendations

• Quantum Kolmogorov complexity
• Quantum algorithmic entropy
• Quantum algorithmic randomness
• SECOND QUANTIZED KOLMOGOROV COMPLEXITY
• Quantum Kolmogorov complexity based on classical descriptions

Cites work

• A new quantum random number generator certified by value indefiniteness
• A quantum random number generator certified by value indefiniteness
• Algorithmic randomness and complexity.
• Computability and randomness
• Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem
• Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces
• Generating randomness from a computable, non-random sequence of qubits
• scientific article; zbMATH DE number 1542869 (Why is no real title available?)
• scientific article; zbMATH DE number 1911266 (Why is no real title available?)
• Incompleteness theorems for random reals
• Martin-Löf random quantum states
• On the Unpredictability of Individual Quantum Measurement Outcomes
• Quantum algorithmic randomness
• Quantum Complexity Theory
• Quantum computation and quantum information. 10th anniversary edition
• Quantum Kolmogorov complexity
• Quantum Kolmogorov complexity based on classical descriptions
• Quantum mechanical Hamiltonian models of Turing machines
• Quantum theory, the Church–Turing principle and the universal quantum computer
• The Shannon-McMillan theorem for ergodic quantum lattice systems

Cited in

(5)

• THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY
• Quantum Kolmogorov complexity based on classical descriptions
• Quantum algorithmic randomness
• Quantum Kolmogorov complexity
• Von Neumann entropy and quantum algorithmic randomness

This page was built for publication: Prefix-free quantum Kolmogorov complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2034780)