Sandwich theorems and capacity bounds for non-commutative graphs

DOI10.1016/J.JCTA.2020.105302MaRDI QIDQ2005181zbMATH OpenOpenAlexFDO

Authors G. Boreland, Ivan G. Todorov, Andreas Winter

Publication date 7 October 2020

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

quantum channelShannon capacitysandwich theoremnon-commutative graphLovász number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding theorems (Shannon theory) (94A24) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Channel models (including quantum) in information and communication theory (94A40)

Abstract: We define non-commutative versions of the vertex packing polytope, the theta convex body and the fractional vertex packing polytope of a graph, and establish a quantum version of the Sandwich Theorem of Gr"{o}tschel, Lov'{a}sz and Schrijver. We define new non-commutative versions of the Lov'{a}sz number of a graph which lead to an upper bound of the zero-error capacity of the corresponding quantum channel that can be genuinely better than the one established previously by Duan, Severini and Winter. We define non-commutative counterparts of widely used classical graph parameters and establish their interrelation.

Recommendations

• Information theoretic parameters of noncommutative graphs and convex corners
• Structure of the algebra generated by a noncommutative operator graph which demonstrates the superactivation phenomenon for zero-error capacity
• Violating the Shannon capacity of metric graphs with entanglement
• Quantum homomorphisms
• On the Shannon capacity of a graph

Cites work

• scientific article; zbMATH DE number 3745081 (Why is no real title available?)
• scientific article; zbMATH DE number 3627813 (Why is no real title available?)
• scientific article; zbMATH DE number 1351867 (Why is no real title available?)
• scientific article; zbMATH DE number 1849957 (Why is no real title available?)
• A ``quantum Ramsey theorem for operator systems
• A continuity theorem for Stinespring's dilation
• Completely positive linear maps on complex matrices
• Complexity and Capacity Bounds for Quantum Channels
• Entropy splitting for antiblocking corners and perfect graphs
• Geometric algorithms and combinatorial optimization.
• Lovász theta type norms and operator systems
• On the Shannon capacity of a graph
• Quantum Zero-Error Source-Channel Coding and Non-Commutative Graph Theory
• Quantum computation and quantum information. 10th anniversary edition
• Quantum systems, channels, information. A mathematical introduction.
• Relaxations of vertex packing
• The sandwich theorem
• The theory of quantum information
• Zero-Error Communication via Quantum Channels, Noncommutative Graphs, and a Quantum Lovász Number

Cited in

(7)

• Quantum no-signalling correlations and non-local games
• Synchronicity for quantum non-local games
• Bounds on entanglement assisted source-channel coding via the Lovász \(\vartheta\) number and its variants
• Structure of the algebra generated by a noncommutative operator graph which demonstrates the superactivation phenomenon for zero-error capacity
• Information theoretic parameters of noncommutative graphs and convex corners
• Homomorphisms of quantum hypergraphs
• Quantum graphs: different perspectives, homomorphisms and quantum automorphisms

This page was built for publication: Sandwich theorems and capacity bounds for non-commutative graphs

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