Quantum Kolmogorov complexity

DOI10.1006/JCSS.2001.1765zbMath0992.68086arXivquant-ph/0005018OpenAlexW2762038352MaRDI QIDQ5956011

André Berthiaume, Wim van Dam, Sophie Laplante

Publication date: 19 February 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0005018

zbMATH Keywords

quantum Kolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (19)

Quantum information distance ⋮ Entanglement, complexity, and causal asymmetry in quantum theories ⋮ State complexity and quantum computation ⋮ Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report) ⋮ Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces ⋮ Algorithmic complexity of quantum capacity ⋮ Entropy and algorithmic complexity in quantum information theory ⋮ Quantum dynamical entropies and Gács algorithmic entropy ⋮ THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY ⋮ An extended coding theorem with application to quantum complexities ⋮ SECOND QUANTIZED KOLMOGOROV COMPLEXITY ⋮ Quantum Kolmogorov complexity and information-disturbance theorem ⋮ Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem ⋮ LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY ⋮ Quantum Algorithmic Complexities and Entropy ⋮ Prefix-free quantum Kolmogorov complexity ⋮ ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Quantum algorithmic randomness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completely positive maps and entropy inequalities
• Relative entropy and the Wigner-Yanase-Dyson-Lieb concavity in an interpolation theory
• Quantum algorithmic entropy
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Quantum computing: pro and con
• Quantum Complexity Theory
• Stabilization of Quantum Computations by Symmetrization
• A New Proof of the Quantum Noiseless Coding Theorem
• Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
• Quantum Kolmogorov complexity based on classical descriptions
• Cryptographic distinguishability measures for quantum-mechanical states
• A single quantum cannot be cloned
• On the Length of Programs for Computing Finite Binary Sequences

This page was built for publication: Quantum Kolmogorov complexity