Quantum Kolmogorov Complexity
arXiv:quant-ph/0005018 · doi:10.1006/jcss.2001.1765
Abstract
In this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can produce this string as its output. It is a measure of the amount of innate randomness (or information) contained in the string. We define the quantum Kolmogorov complexity of a qubit string as the length of the shortest quantum input to a universal quantum Turing machine that produces the initial qubit string with high fidelity. The definition of Vitanyi (Proceedings of the 15th IEEE Annual Conference on Computational Complexity, 2000) measures the amount of classical information, whereas we consider the amount of quantum information in a qubit string. We argue that our definition is natural and is an accurate representation of the amount of quantum information contained in a quantum state.
14 pages, LaTeX2e, no figures, \usepackage{amssymb,a4wide}. To appear in the Proceedings of the 15th IEEE Annual Conference on Computational Complexity
References in corpus (6)
Cited by in corpus (37)
- Quantum Computational Complexity -- From Quantum Information to Black Holes and Back
- 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
- Krylov Complexity and Dynamical Phase Transition in the quenched LMG model
- Quantum Kolmogorov Complexity and the Quantum Turing Machine
- State complexity and quantum computation
- Spread complexity and quantum chaos for periodically driven spin chains
- Complexity-constrained quantum thermodynamics
- Algorithmic Information Theoretic Issues in Quantum Mechanics
- Upper bound by Kolmogorov complexity for the probability in computable POVM measurement
- Quantum Kolmogorov Complexity and Quantum Key Distribution
- Lossless Quantum Prefix Compression for Communication Channels that are Always Open
- Algorithmic complexity of quantum capacity
- Prefix-free quantum Kolmogorov complexity
- Quantum algorithmic randomness
- Generalized Zurek's bound on the cost of an individual classical or quantum computation
- 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 Bounded Quantum Memory
- Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
- The information-theoretical viewpoint on the physical complexity of classical and quantum objects and their dynamical evolution
- Entanglement, Complexity, and Causal Asymmetry in Quantum Theories
- Von Neumann Entropy and Quantum Algorithmic Randomness
- Quantum entropy and complexity
- Gacs Algorithmic Complexity on Hilbert Spaces and Some of its Applications
- Algorithmic Randomness and Kolmogorov Complexity for Qubits
- Quantum substitutions of Pisot type, their quantum topological entropy and their use for optimal spacing
- On Gács' quantum algorithmic entropy
- 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
- Probing the localization effects in Krylov basis
- On the Quantum Kolmogorov Complexity of Classical Strings
- Use of Mathematical Logical Concepts in Quantum Mechanics: An Example
- Second Quantized Kolmogorov Complexity