SECOND QUANTIZED KOLMOGOROV COMPLEXITY

DOI10.1142/S021974990800375XzbMATH Open1153.81471arXiv0809.2642MaRDI QIDQ3536074FDOQ3536074

Authors: Caroline Rogers, Vlatko Vedral, Rajagopal Nagarajan 

Publication date: 17 November 2008

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

Abstract: The Kolmogorov complexity of a string is the length of its shortest description. We define a second quantised Kolmogorov complexity where the length of a description is defined to be the average length of its superposition. We discuss this complexity's basic properties. We define the corresponding prefix complexity and show that the inequalities obeyed by this prefix complexity are also obeyed by von Neumann entropy.

Full work available at URL: https://arxiv.org/abs/0809.2642

Recommendations

• THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY
• Quantum Kolmogorov complexity
• Quantum algorithmic entropy
• QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS
• Quantum Kolmogorov complexity based on classical descriptions

zbMATH Keywords

quantum Kolmogorov complexityindeterminate length quantum stringsinequalities of von Neumann entropyvariable length compression

Mathematics Subject Classification ID

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

Cites Work

• Algorithmic Information Theory
• Quantum Complexity Theory
• Reversible arithmetic coding for quantum data compression
• A new inequality for the von Neumann entropy
• Quantum algorithmic entropy
• Quantum Kolmogorov complexity based on classical descriptions
• Quantum Kolmogorov complexity
• Inequalities for Shannon entropy and Kolmogorov complexity
• ALGORITHMIC COMPLEXITY OF QUANTUM STATES
• A strange application of Kolmogorov complexity
• On Lossless Quantum Data Compression With a Classical Helper

Cited In (8)

• Quantum Kolmogorov complexity
• Prefix-free quantum Kolmogorov complexity
• Quantum complexity and the virial theorem
• Quantum information distance
• State complexity and quantum computation
• Complexity measure: a quantum information approach
• Lossless quantum data compression and quantum Kolmogorov complexity
• THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY

This page was built for publication: SECOND QUANTIZED KOLMOGOROV COMPLEXITY

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