Entanglement-assisted zero-error source-channel coding
arXiv:1308.4283 · doi:10.1109/TIT.2014.2385080
Abstract
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ász 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.
arXiv commentTitle has been changed. Previous title was 'Zero-error source-channel coding with entanglement'. Corrected an error in Lemma 1.2
References in corpus (9)
- Remote State Preparation
- Improving zero-error classical communication with entanglement
- Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovasz theta function
- The Shannon capacity of a graph and the independence numbers of its powers
- Entanglement can increase asymptotic rates of zero-error classical communication over classical channels
- A Generalization of Kochen-Specker Sets Relates Quantum Coloring to Entanglement-Assisted Channel Capacity
- Entanglement-assisted zero-error capacity is upper bounded by the Lovasz theta function
- Bounds on entanglement assisted source-channel coding via the Lovasz theta number and its variants
- Violating the Shannon capacity of metric graphs with entanglement
Cited by in corpus (4)
- Quantum source-channel coding and non-commutative graph theory
- The Capacity of Classical Summation over a Quantum MAC with Arbitrarily Distributed Inputs and Entanglements
- Separation between quantum Lovász number and entanglement-assisted zero-error classical capacity
- Quantum advantage in zero-error function computation with side information