Quantum Algorithmic Entropy

Abstract

We extend algorithmic information theory to quantum mechanics, taking a universal semicomputable density matrix (``universal probability'') as a starting point, and define complexity (an operator) as its negative logarithm. A number of properties of Kolmogorov complexity extend naturally to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity. The von Neumann entropy of a computable density matrix is within an additive constant from the average complexity. Some of the theory of randomness translates to the new domain. We explore the relations of the new quantity to the quantum Kolmogorov complexity defined by Vitanyi (we show that the latter is sometimes as large as 2n - 2log n and the qubit complexity defined by Berthiaume, Dam and Laplante. The ``cloning'' properties of our complexity measure are similar to those of qubit complexity.

20 pages. Minor Tex problem corrected

References in corpus (1)

• Indeterminate-length quantum coding

Cited by in corpus (28)

• Quantum Kolmogorov Complexity Based on Classical Descriptions
• Chaos and Complexity of quantum motion
• Algorithmic complexity and entanglement of quantum states
• Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno's Theorem
• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
• Quantum Kolmogorov Complexity and the Quantum Turing Machine
• Complexity of Graph State Preparation
• An extension of Chaitin's halting probability Ωto a measurement operator in an infinite dimensional quantum system
• Quantum Kolmogorov Complexity and Quantum Key Distribution
• Upper bound by Kolmogorov complexity for the probability in computable POVM measurement
• Algorithmic complexity of quantum capacity
• Entropy and Diversity: The Axiomatic Approach
• Microscopic Reversibility and Macroscopic Irreversibility: From a viewpoint of Algorithmic Randomness
• Kolmogorov complexity as intrinsic entropy of a pure state: Perspective from entanglement in free fermion systems
• Quantum Kolmogorov Complexity and Information-Disturbance Theorem
• Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
• Quantum Kolmogorov Complexity and Bounded Quantum Memory
• Law of Excluded Quantum Gambling Strategies
• The information-theoretical viewpoint on the physical complexity of classical and quantum objects and their dynamical evolution
• Gacs Algorithmic Complexity on Hilbert Spaces and Some of its Applications
• Von Neumann Entropy and Quantum Algorithmic Randomness
• Quantum substitutions of Pisot type, their quantum topological entropy and their use for optimal spacing
• Second Quantized Kolmogorov Complexity
• Classification of the automorphisms of the noncommutative torus among the (chaotic and non-chaotic) shallow ones and the non-chaotic complex ones
• An Extended Coding Theorem with Application to Quantum Complexities
• Use of Mathematical Logical Concepts in Quantum Mechanics: An Example
• On the Quantum Kolmogorov Complexity of Classical Strings
• On the Algorithmic Content of Quantum Measurements