Zero-error source-channel coding with entanglement
Jop Briët, Harry Buhrman, Monique Laurent, Teresa Piovesan, Giannicola Scarpa · Scuola Normale Superiore eBooks · 2013
We study a problem from zero-error information theory—a topic well-known for its rich connections to combinatorics [1,8,10–12,14]—in a setting where a sender and receiver may use quantum entanglement, one of the most striking features of quantum mechanics. The problem that we consider is the classical source-channel coding problem , where Alice and Bob are each given an input from a random source and get access to a noisy channel through which Alice can send messages to Bob. Their goal is to minimize the average number of channel uses per source input while allowing Bob to learn Alice’s inputs. Here we show that entanglement can allow for an unbounded decrease in the asymptotic rate of classical source-channel codes. We also consider the source problem , the case where Alice can send messages to Bob without noise. We prove a lower bound on the rate of source codes with entanglement in terms of a variant of the Lovász theta number [10,13], a graph parameter given by a semidefinite program.