Quantum Kolmogorov Complexity Based on Classical Descriptions
arXiv:quant-ph/0102108 · doi:10.1109/18.945258
Abstract
We develop a theory of the algorithmic information in bits contained in an individual pure quantum state. This extends classical Kolmogorov complexity to the quantum domain retaining classical descriptions. Quantum Kolmogorov complexity coincides with the classical Kolmogorov complexity on the classical domain. Quantum Kolmogorov complexity is upper bounded and can be effectively approximated from above under certain conditions. With high probability a quantum object is incompressible. Upper- and lower bounds of the quantum complexity of multiple copies of individual pure quantum states are derived and may shed some light on the no-cloning properties of quantum states. In the quantum situation complexity is not sub-additive. We discuss some relations with ``no-cloning'' and ``approximate cloning'' properties.
17 pages, LaTeX, final and extended version of quant-ph/9907035, with corrections to the published journal version (the two displayed equations in the right-hand column on page 2466 had the left-hand sides of the displayed formulas erroneously interchanged)
Cited by in corpus (35)
- 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
- 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
- Algorithmic complexity of quantum capacity
- Prefix-free quantum Kolmogorov complexity
- Quantum Kolmogorov Complexity and Information-Disturbance Theorem
- Kolmogorov complexity as intrinsic entropy of a pure state: Perspective from entanglement in free fermion systems
- Quantum algorithmic randomness
- Microscopic Reversibility and Macroscopic Irreversibility: From a viewpoint of Algorithmic Randomness
- Generalized Zurek's bound on the cost of an individual classical or quantum computation
- Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
- Quantum Kolmogorov Complexity and Bounded Quantum Memory
- Topological obstructions to quantum computation with unitary oracles
- Incompleteness, Complexity, Randomness and Beyond
- Entanglement, Complexity, and Causal Asymmetry in Quantum Theories
- The information-theoretical viewpoint on the physical complexity of classical and quantum objects and their dynamical evolution
- Quantum entropy and complexity
- Algorithmic Randomness and Kolmogorov Complexity for Qubits
- Gacs Algorithmic Complexity on Hilbert Spaces and Some of its Applications
- The No Cloning Theorem versus the Second Law of Thermodynamics
- Use of Mathematical Logical Concepts in Quantum Mechanics: An Example
- Second Quantized Kolmogorov Complexity
- Algorithmic Problem Complexity
- 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
- Topologically driven no-superposing theorem with a tight error bound
- On Gács' quantum algorithmic entropy
- Quantum substitutions of Pisot type, their quantum topological entropy and their use for optimal spacing
- Quantum Optimization Problems
- Computational Complexity Measures of Multipartite Quantum Entanglement