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

information theoryalgorithmic informationquantum stateKolmogorov complexityquantum cloning

Mathematics Subject Classification ID

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

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)

• Quantum algorithmic randomness
• Probing the quantum-classical boundary with compression software
• ALGORITHMIC COMPLEXITY OF QUANTUM STATES
• Randomness and intractability in Kolmogorov complexity
• ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS
• Quantum state description complexity (invited talk)
• 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
• Informational branching universe
• Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces
• Statistical complexity and classical-quantum frontier
• Quantum Kolmogorov complexity and information-disturbance theorem
• Lossless quantum data compression and quantum Kolmogorov complexity
• THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY
• SECOND QUANTIZED KOLMOGOROV COMPLEXITY
• Analytical complexity and signal coding

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)