Sandwich theorems and capacity bounds for non-commutative graphs

DOI10.1016/J.JCTA.2020.105302zbMATH Open1448.05159arXiv1907.11504OpenAlexW2964532533MaRDI QIDQ2005181FDOQ2005181

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)

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.

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

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

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)

Cites Work

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

Cited In (7)

• Synchronicity for quantum non-local games
• Bounds on entanglement assisted source-channel coding via the Lovász \(\vartheta\) number and its variants
• 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
• Homomorphisms of quantum hypergraphs
• Quantum graphs: different perspectives, homomorphisms and quantum automorphisms
• Quantum no-signalling correlations and non-local games

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)