ALGORITHMIC COMPLEXITY OF QUANTUM STATES

DOI10.1142/S0219749906002043MaRDI QIDQ5493927zbMATH OpenOpenAlexFDO

Authors C. Mora, H. J. Briegel

Publication date 16 October 2006

Published in International Journal of Quantum Information (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic complexityentanglementShannon entropy

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Quantum computation (81P68) Measures of information, entropy (94A17)

Abstract: In this paper we give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of ``how difficult it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of states.

Recommendations

• Quantum algorithmic entropy
• Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem
• Quantum Kolmogorov complexity
• Entropy and algorithmic complexity in quantum information theory
• Quantum Kolmogorov complexity based on classical descriptions

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3137325 (Why is no real title available?)
• Quantum computations: algorithms and error correction

Cited in

(24)

• The decrease in the overall algorithmic complexity of the spin-echo effect
• Algorithmic complexity of quantum capacity
• Quantum complexity and the virial theorem
• Entanglement, complexity, and causal asymmetry in quantum theories
• Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem
• Equilibration in low-dimensional quantum matrix models
• Quantum algorithmic entropy
• Quantum state description complexity (invited talk)
• Lossless quantum data compression and quantum Kolmogorov complexity
• Algebraic analysis of quantum search with pure and mixed states
• Computational Complexity of Projected Entangled Pair States
• State complexity and quantum computation
• QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS
• SECOND QUANTIZED KOLMOGOROV COMPLEXITY
• ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS
• Kolmogorov's algorithmic complexity and its probability interpretation in quantum gravity
• Quantum Kolmogorov complexity based on classical descriptions
• Complexity measure: a quantum information approach
• An algorithmic construction of quantum circuits of high descriptive complexity
• Computing complexity measures for quantum states based on exponential families
• Probing the quantum-classical boundary with compression software
• Hay from the haystack: explicit examples of exponential quantum circuit complexity
• A meta-complexity characterization of quantum cryptography
• Informational branching universe

This page was built for publication: ALGORITHMIC COMPLEXITY OF QUANTUM STATES

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5493927)