An extended coding theorem with application to quantum complexities

DOI10.1016/J.IC.2020.104660MaRDI QIDQ2216136zbMATH OpenOpenAlexFDO

Authors Samuel Epstein

Publication date 15 December 2020

Published in Information and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: This paper introduces a new inequality in algorithmic information theory that can be seen as an extended coding theorem. This inequality has applications in new bounds between quantum complexity measures.

Recommendations

• QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS
• Quantum algorithmic entropy
• Quantum Kolmogorov complexity and information-disturbance theorem
• Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem
• A new inequality for the von Neumann entropy

Cites work

• scientific article; zbMATH DE number 3860059 (Why is no real title available?)
• scientific article; zbMATH DE number 4041257 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A formal theory of inductive inference. Part I
• Algorithmic statistics: forty years later
• An introduction to Kolmogorov complexity and its applications
• Discussion on Kolmogorov Complexity and Statistical Analysis
• Kolmogorov's Structure Functions and Model Selection
• On algorithmic strong sufficient statistics
• Quantum Kolmogorov complexity
• Quantum algorithmic entropy
• Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity
• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity

Cited in

(7)

• A Combinatorial Interpretation for the Shor-Laflamme Weight Enumerators of CWS Codes
• A Coding Theorem for Bipartite Unitaries in Distributed Quantum Computation
• scientific article; zbMATH DE number 5508888 (Why is no real title available?)
• Entropic Proofs of Singleton Bounds for Quantum Error-Correcting Codes
• scientific article; zbMATH DE number 1944611 (Why is no real title available?)
• Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding
• Inequalities for space-bounded Kolmogorov complexity

This page was built for publication: An extended coding theorem with application to quantum complexities

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