  We study the use of quantum entanglement in the zero-error source-channel
coding problem. Here, Alice and Bob are connected by a noisy classical one-way
channel, and are given correlated inputs from a random source. Their goal is
for Bob to learn Alice's input while using the channel as little as possible.
In the zero-error regime, the optimal rates of source codes and channel codes
are given by graph parameters known as the Witsenhausen rate and Shannon
capacity, respectively. The Lov\'asz theta number, a graph parameter defined by
a semidefinite program, gives the best efficiently-computable upper bound on
the Shannon capacity and it also upper bounds its entanglement-assisted
counterpart. At the same time it was recently shown that the Shannon capacity
can be increased if Alice and Bob may use entanglement.
  Here we partially extend these results to the source-coding problem and to
the more general source-channel coding problem. We prove a lower bound on the
rate of entanglement-assisted source-codes in terms Szegedy's number (a
strengthening of the theta number). This result implies that the theta number
lower bounds the entangled variant of the Witsenhausen rate. We also show that
entanglement can allow for an unbounded improvement of the asymptotic rate of
both classical source codes and classical source-channel codes. Our separation
results use low-degree polynomials due to Barrington, Beigel and Rudich,
Hadamard matrices due to Xia and Liu and a new application of remote state
preparation.
