Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno's Theorem

Abstract

In classical information theory, entropy rate and Kolmogorov complexity per symbol are related by a theorem of Brudno. In this paper, we prove a quantum version of this theorem, connecting the von Neumann entropy rate and two notions of quantum Kolmogorov complexity, both based on the shortest qubit descriptions of qubit strings that, run by a universal quantum Turing machine, reproduce them as outputs.

26 pages, no figures. Reference to publication added: published in the Communications in Mathematical Physics (http://www.springerlink.com/content/1432-0916/)

References in corpus (10)

• Quantum Kolmogorov Complexity
• Universal Quantum Information Compression
• Quantum Kolmogorov Complexity Based on Classical Descriptions
• Quantum Algorithmic Entropy
• Algorithmic complexity and entanglement of quantum states
• Measurement-Based Quantum Turing Machines and their Universality
• Stationary quantum source coding
• Chained Typical Subspaces - a Quantum Version of Breiman's Theorem
• Algorithmic complexity of quantum states
• The information-theoretical viewpoint on the physical complexity of classical and quantum objects and their dynamical evolution

Cited by in corpus (21)

• Chaos and Complexity of quantum motion
• Law without law: from observer states to physics via algorithmic information theory
• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
• Renormalization algorithm with graph enhancement
• Quantum Kolmogorov Complexity and the Quantum Turing Machine
• Entropy rate of message sources driven by quantum walks
• Prefix-free quantum Kolmogorov complexity
• Quantum algorithmic randomness
• Quantum Kolmogorov Complexity and Information-Disturbance Theorem
• Kolmogorov complexity as intrinsic entropy of a pure state: Perspective from entanglement in free fermion systems
• Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
• Quantum Entropies and Decoherence for the Multiparticle Quantum Arnol'd Cat
• Algorithmic Randomness and Kolmogorov Complexity for Qubits
• Quantum entropy and complexity
• Von Neumann Entropy and Quantum Algorithmic Randomness
• On the Algorithmic Content of Quantum Measurements
• Behavior of correlation functions in the dynamics of the Multiparticle Quantum Arnol'd Cat
• On the Quantum Kolmogorov Complexity of Classical Strings
• Classification of the automorphisms of the noncommutative torus among the (chaotic and non-chaotic) shallow ones and the non-chaotic complex ones
• On Gács' quantum algorithmic entropy
• Quantum substitutions of Pisot type, their quantum topological entropy and their use for optimal spacing