Quantum Kolmogorov complexity based on classical descriptions
From MaRDI portal
Publication:4544682
DOI10.1109/18.945258zbMATH Open1021.94006arXivquant-ph/0102108OpenAlexW2106534004MaRDI QIDQ4544682FDOQ4544682
Publication date: 4 August 2002
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/quant-ph/0102108
Recommendations
Information theory (general) (94A15) Quantum computation (81P68) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Cited In (23)
- ALGORITHMIC COMPLEXITY OF QUANTUM STATES
- ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS
- LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY
- Quantum Kolmogorov complexity
- Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness
- Entanglement, complexity, and causal asymmetry in quantum theories
- Quantum dynamical entropies and Gács algorithmic entropy
- Entropy and algorithmic complexity in quantum information theory
- Prefix-free quantum Kolmogorov complexity
- Algorithmic complexity of quantum capacity
- QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS
- Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report)
- Quantum algorithmic entropy
- Quantum information distance
- Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem
- Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces
- Informational branching universe
- Randomness and Intractability in Kolmogorov Complexity
- Statistical complexity and classical-quantum frontier
- Quantum Kolmogorov complexity and information-disturbance theorem
- THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY
- SECOND QUANTIZED KOLMOGOROV COMPLEXITY
- Quantum algorithmic randomness
This page was built for publication: Quantum Kolmogorov complexity based on classical descriptions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4544682)
