Bounds on entanglement assisted source-channel coding via the Lovasz theta number and its variants
| Autor: | Cubitt, Toby, Mancinska, Laura, Roberson, David, Severini, Simone, Stahlke, Dan, Winter, Andreas |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | IEEE Trans. Inf. Theory 60(11):7330-7344 (2014) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1109/TIT.2014.2349502 |
| Popis: | 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\'asz 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 Lov\'asz 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 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. Comment: Fixed proof of multiplicativity; more connections to prior work in conclusion; many changes in exposition |
| Databáze: | arXiv |
| Externí odkaz: |
|