Zero-error source-channel coding with entanglement

Zero-error source-channel coding with entanglement

Seminar author:Giannicola Scarpa

Event date and time:04/09/2013 11:30:am

Event location:IFAE seminar room (UAB)

Event contact:

We study the use of 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. It was recently shown that entanglement allows for a separation between the Shannon capacity of a graph and its entanglement-assisted variant.
Here we show that entanglement can allow for an unbounded decrease in the asymptotic rate of classical source-channel codes. Our proof uses low-degree polynomials due to Barrington, Beigel and Rudich, Hadamard matrices due to Xia and Liu and a novel application of the quantum teleportation scheme of Bennett et al. We also prove a lower bound on the rate of entanglement-assisted source-codes in terms of a variant of the Lov asz theta number introduced by Szegedy, a graph parameter given by a semidefinite program.