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


الملخص بالإنكليزية

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 Lovasz 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^*(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 Lovasz number. Beigi introduced a quantity $beta$ as an upper bound on $alpha^*$ 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_{textrm{vect}}(G)$ recently introduced in the context of Tsirelsons conjecture is equal to $lceil vartheta^+(overline{G}) rceil$. In an appendix we investigate multiplicativity properties of Schrijvers and Szegedys numbers, as well as projective rank.

تحميل البحث