Bounds on entanglement-assisted source-channel coding via the Lovász ϑ number and its variants

• Main Authors: Cubitt, Toby, Mancinska, Laura, Roberson, David E., Severini, Simone, Stahlke, Dan, Winter, Andreas
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2015
• Subjects: DRNTU::Engineering::Computer science and engineering::Information systems
• Online Access: https://hdl.handle.net/10356/103786; http://hdl.handle.net/10220/24586
• Institution: Nanyang Technological University

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 ϑ(G̅) ≤ ϑ(H̅), where ϑ represents the Lovász number. We also obtain similar inequalities for the related Schrijver ϑ- and Szegedy ϑ+ 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: α*(G) ≤ ϑ-(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 β as an upper bound on α* and posed the question of whether β(G) = ⌊ϑ(G)⌋. We answer this in the affirmative and show that a related quantity is equal to ⌊ϑ(G)⌋. We show that a quantity χvect(G) recently introduced in the context of Tsirelson's problem is equal to ⌊ϑ+(G)⌋. In an appendix, we investigate multiplicativity properties of Schrijver's and Szegedy's numbers, as well as projective rank.