Second Quantized Kolmogorov Complexity
arXiv:0809.2642
Abstract
The Kolmogorov complexity of a string is the length of its shortest description. We define a second quantised Kolmogorov complexity where the length of a description is defined to be the average length of its superposition. We discuss this complexity's basic properties. We define the corresponding prefix complexity and show that the inequalities obeyed by this prefix complexity are also obeyed by von Neumann entropy.
14 pages, 0 figures
References in corpus (13)
- Quantum Kolmogorov Complexity
- Quantum Kolmogorov Complexity Based on Classical Descriptions
- Quantum Algorithmic Entropy
- Algorithmic complexity and entanglement of quantum states
- Indeterminate-length quantum coding
- Lossless quantum data compression and variable-length coding
- Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
- Quantum algorithmic information theory
- An extension of Chaitin's halting probability Ωto a measurement operator in an infinite dimensional quantum system
- Algorithmic Information Theoretic Issues in Quantum Mechanics
- Upper bound by Kolmogorov complexity for the probability in computable POVM measurement
- Energy Requirements for Quantum Data Compression and 1-1 Coding
- Lossless Quantum Compression