Quantum Kolmogorov complexity
From MaRDI portal
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.
Recommendations
- QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS
- Quantum Kolmogorov complexity based on classical descriptions
- Quantum Complexity Theory
- Quantum Kolmogorov complexity and information-disturbance theorem
- Prefix-free quantum Kolmogorov complexity
- Quantum information complexity
- On quantum complexity
- Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem
- SECOND QUANTIZED KOLMOGOROV COMPLEXITY
- Quantum entropy and complexity
Cites work
- A New Proof of the Quantum Noiseless Coding Theorem
- A single quantum cannot be cloned
- Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
- Completely positive maps and entropy inequalities
- Cryptographic distinguishability measures for quantum-mechanical states
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 3761463 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 3497764 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1010621 (Why is no real title available?)
- scientific article; zbMATH DE number 1542869 (Why is no real title available?)
- scientific article; zbMATH DE number 3062467 (Why is no real title available?)
- On the Length of Programs for Computing Finite Binary Sequences
- Quantum algorithmic entropy
- Quantum Complexity Theory
- Quantum computing: pro and con
- Quantum Kolmogorov complexity based on classical descriptions
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Relative entropy and the Wigner-Yanase-Dyson-Lieb concavity in an interpolation theory
- Stabilization of Quantum Computations by Symmetrization
Cited in
(31)- Algorithmic complexity of quantum capacity
- Prefix-free quantum Kolmogorov complexity
- Entanglement, complexity, and causal asymmetry in quantum theories
- 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
- Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem
- Quantum algorithmic entropy
- Lossless quantum data compression and quantum Kolmogorov complexity
- Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces
- Quantum Hamiltonian Complexity
- State complexity and quantum computation
- QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS
- THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY
- SECOND QUANTIZED KOLMOGOROV COMPLEXITY
- Quantum algorithmic complexities and entropy
- Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
- ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS
- Quantum dynamical entropies and Gács algorithmic entropy
- Quantum averaging II: Kolmogorov's algorithm
- Quantum Kolmogorov complexity based on classical descriptions
- Complexity measure: a quantum information approach
- Quantum information distance
- Randomness and intractability in Kolmogorov complexity
- ALGORITHMIC COMPLEXITY OF QUANTUM STATES
- Quantum algorithmic randomness
- scientific article; zbMATH DE number 7701522 (Why is no real title available?)
- Quantum Kolmogorov complexity and information-disturbance theorem
- Quantum Kolmogorov complexity and the quantum Turing machine
- A meta-complexity characterization of quantum cryptography
- Von Neumann entropy and quantum algorithmic randomness
- Entropy and algorithmic complexity in quantum information theory
This page was built for publication: Quantum Kolmogorov complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956011)
