Prefix-free quantum Kolmogorov complexity

DOI10.1016/j.tcs.2021.05.017zbMath1504.68084arXiv2101.11686OpenAlexW3122335491MaRDI QIDQ2034780

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 randomnessqubitSchnorr randomnessprefix-free Turing machine

Mathematics Subject Classification ID

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

Related Items (1)

Quantum algorithmic randomness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantum mechanical Hamiltonian models of Turing machines
• Incompleteness theorems for random reals
• The Shannon-McMillan theorem for ergodic quantum lattice systems
• A new quantum random number generator certified by value indefiniteness
• Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem
• On the Unpredictability of Individual Quantum Measurement Outcomes
• Quantum Computation and Quantum Information
• Algorithmic Randomness and Complexity
• Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Quantum Complexity Theory
• Quantum Kolmogorov complexity based on classical descriptions
• Martin-Löf random quantum states
• A quantum random number generator certified by value indefiniteness
• Quantum algorithmic randomness
• Quantum Kolmogorov complexity

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