Quantum Kolmogorov complexity based on classical descriptions

DOI10.1109/18.945258zbMath1021.94006arXivquant-ph/0102108OpenAlexW2106534004MaRDI QIDQ4544682

Paul M. B. Vitányi

Publication date: 4 August 2002

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0102108

zbMATH Keywords

Kolmogorov complexityinformation theoryquantum statealgorithmic informationquantum cloning

Mathematics Subject Classification ID

Quantum computation (81P68) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Information theory (general) (94A15)

Related Items

Quantum information distance ⋮ Entanglement, complexity, and causal asymmetry in quantum theories ⋮ Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report) ⋮ Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces ⋮ Algorithmic complexity of quantum capacity ⋮ Entropy and algorithmic complexity in quantum information theory ⋮ Quantum dynamical entropies and Gács algorithmic entropy ⋮ THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY ⋮ SECOND QUANTIZED KOLMOGOROV COMPLEXITY ⋮ Quantum Kolmogorov complexity and information-disturbance theorem ⋮ Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem ⋮ LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY ⋮ Informational branching universe ⋮ Quantum Kolmogorov complexity ⋮ Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness ⋮ Prefix-free quantum Kolmogorov complexity ⋮ ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Quantum algorithmic randomness

This page was built for publication: Quantum Kolmogorov complexity based on classical descriptions