Entanglement-assisted zero-error capacity is upper-bounded by the Lovász $\vartheta$ function

The zero-error capacity of a classical channel is expressed in terms of the independence number of some graph and its tensor powers. This quantity is hard to compute even for small graphs such as the cycle of length seven, so upper bounds such as the Lovász theta function play an important role in zero-error communication. In this paper, we show that the Lovász theta function is an upper bound on the zero-error capacity even in the presence of entanglement between the sender and receiver.

Figure 1

The left graph shows a channel with input set $\{x_1,\dots ,x_5\}$ and output set $\{y_1,y_2,y_3\}$. If, for example, the input of the channel is $x_3$ the output is $y_1$ or $y_2$ with probabilities $0.4$ and $0.6$ respectively. If the receiver sees $y_2$ as the output, the input is either $x_3$ or $x_4$, so $(x_3,x_4)$ is a confusable pair. The right graph depicts the confusability graph of the channel. The independence number of this graph is $2$, so $\log {}_{2}2=1$ bit of information, by using code words $\{x_3,x_5\}$, can be sent through this channel with no error. Moreover, it is not hard to convince oneself that the independence of the $k$th tensor power of this graph (the graph corresponding to $k$ use of the channel) is equal to $2^k$, and then the zero-error capacity of this channel is $1$.