Quantum algorithmic entropy
From MaRDI portal
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.
Recommendations
Cited in
(35)- Algorithmic complexity of quantum capacity
- Quantum complexity and the virial theorem
- Prefix-free quantum Kolmogorov complexity
- Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report)
- An extended coding theorem with application to quantum complexities
- Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness
- Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem
- Lossless quantum data compression and quantum Kolmogorov complexity
- Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces
- THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY
- SECOND QUANTIZED KOLMOGOROV COMPLEXITY
- Quantum algorithmic complexities and entropy
- Quantum algorithms: entanglement–enhanced information processing
- ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS
- Quantum dynamical entropies and Gács algorithmic entropy
- Kolmogorov's algorithmic complexity and its probability interpretation in quantum gravity
- scientific article; zbMATH DE number 1542869 (Why is no real title available?)
- Quantum Kolmogorov complexity based on classical descriptions
- Complexity measure: a quantum information approach
- scientific article; zbMATH DE number 1418480 (Why is no real title available?)
- On G\'acs' quantum algorithmic entropy
- Quantum information distance
- Computing the entropy of a large matrix
- Quantum entropy and complexity
- Automata, Languages and Programming
- ALGORITHMIC COMPLEXITY OF QUANTUM STATES
- Quantum algorithmic randomness
- Quantum Kolmogorov complexity
- Quantum Kolmogorov complexity and information-disturbance theorem
- Quantum Kolmogorov complexity and the quantum Turing machine
- Von Neumann entropy and quantum algorithmic randomness
- Entropy as a fixed point
- Entropy and algorithmic complexity in quantum information theory
- Quantum algorithm for SAT problem andquantum mutual entropy
- Informational branching universe
This page was built for publication: Quantum algorithmic entropy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2766202)
