Quantum Kolmogorov complexity based on classical descriptions

DOI10.1109/18.945258MaRDI QIDQ4544682zbMATH OpenOpenAlexFDO

Authors Paul M. B. Vitányi

Publication date 4 August 2002

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0102108, http://dare.uva.nl/personal/pure/en/publications/quantum-kolmogorov-complexity-based-on-classical-descriptions(8adaa0f2-2ef0-4567-b0d2-024a9fa49216).html

zbMATH Keywords

algorithmic informationinformation theoryKolmogorov complexityquantum cloningquantum state

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Quantum computation (81P68) Information theory (general) (94A15)

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.

Recommendations

• Quantum algorithmic entropy
• Prefix-free quantum Kolmogorov complexity
• ALGORITHMIC COMPLEXITY OF QUANTUM STATES
• ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS
• Quantum Kolmogorov complexity

Cited in

(26)

• Algorithmic complexity of quantum capacity
• Prefix-free quantum Kolmogorov complexity
• Entanglement, complexity, and causal asymmetry in quantum theories
• Statistical complexity and classical-quantum frontier
• Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report)
• Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness
• Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem
• Quantum algorithmic entropy
• Quantum state description complexity (invited talk)
• Lossless quantum data compression and quantum Kolmogorov complexity
• Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces
• QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS
• THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY
• SECOND QUANTIZED KOLMOGOROV COMPLEXITY
• ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS
• Quantum dynamical entropies and Gács algorithmic entropy
• Quantum information distance
• Randomness and intractability in Kolmogorov complexity
• ALGORITHMIC COMPLEXITY OF QUANTUM STATES
• Probing the quantum-classical boundary with compression software
• Quantum algorithmic randomness
• Quantum Kolmogorov complexity
• Analytical complexity and signal coding
• Quantum Kolmogorov complexity and information-disturbance theorem
• Entropy and algorithmic complexity in quantum information theory
• Informational branching universe

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)