Bounds on entanglement assisted source-channel coding via the Lovasz theta number and its variants

Abstract

We study zero-error entanglement assisted source-channel coding (communication in the presence of side information). Adapting a technique of Beigi, we show that such coding requires existence of a set of vectors satisfying orthogonality conditions related to suitably defined graphs $G$ and $H$. Such vectors exist if and only if $\vartheta (\overline{G})\le \vartheta (\overline{H})$ where $\vartheta$ represents the Lovász number. We also obtain similar inequalities for the related Schrijver ${\vartheta }^{-}$ and Szegedy ${\vartheta }^{+}$ numbers. These inequalities reproduce several known bounds and also lead to new results. We provide a lower bound on the entanglement assisted cost rate. We show that the entanglement assisted independence number is bounded by the Schrijver number: ${\alpha }^{\ast }(G)\le {\vartheta }^{-}(G)$. Therefore, we are able to disprove the conjecture that the one-shot entanglement-assisted zero-error capacity is equal to the integer part of the Lovász number. Beigi introduced a quantity $\beta$ as an upper bound on ${\alpha }^{\ast }$ and posed the question of whether $\beta (G)=\lfloor \vartheta (G)\rfloor$. We answer this in the affirmative and show that a related quantity is equal to $\lceil \vartheta (G)\rceil$. We show that a quantity ${\chi }_{\text{vect}}(G)$ recently introduced in the context of Tsirelson's conjecture is equal to $\lceil {\vartheta }^{+}(\overline{G})\rceil$. In an appendix we investigate multiplicativity properties of Schrijver's and Szegedy's numbers, as well as projective rank.

Fixed proof of multiplicativity; more connections to prior work in conclusion; many changes in exposition

References in corpus (1)

• Connes' embedding problem and Tsirelson's problem

Cited by in corpus (9)

• Resource convertibility and ordered commutative monoids
• Quantum source-channel coding and non-commutative graph theory
• The asymptotic spectrum of graphs and the Shannon capacity
• Bounding the joint numerical range of Pauli strings by graph parameters
• A new property of the Lovász number and duality relations between graph parameters
• Entanglement-assisted zero-error source-channel coding
• Separation between quantum Lovász number and entanglement-assisted zero-error classical capacity
• A unified construction of semiring-homomorphic graph invariants
• Quantum advantage in zero-error function computation with side information