An extended coding theorem with application to quantum complexities

DOI10.1016/J.IC.2020.104660zbMATH Open1496.68159arXiv1511.05006OpenAlexW3098697362MaRDI QIDQ2216136FDOQ2216136

Samuel Epstein

Publication date: 15 December 2020

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• A formal theory of inductive inference. Part I
• A Theory of Program Size Formally Identical to Information Theory
• Kolmogorov's Structure Functions and Model Selection
• Discussion on Kolmogorov Complexity and Statistical Analysis
• On Algorithmic Strong Sufficient Statistics
• An introduction to Kolmogorov complexity and its applications
• Quantum algorithmic entropy
• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
• Quantum Kolmogorov complexity
• Title not available (Why is that?)
• Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity
• Algorithmic Statistics: Forty Years Later
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• Entropic Proofs of Singleton Bounds for Quantum Error-Correcting Codes
• Title not available (Why is that?)
• 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)