Noisy Interactive Quantum Communication

We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and is of particular importance for real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. To the best of our knowledge, these are the first results regarding the quantum version of this problem, first studied by Schulman in a classical setting (FOCS '92, STOC '93). We simulate a length N quantum communication protocol by a length O(N) protocol. Our simulation strategy has a far higher communication rate than the naive one that encodes each particular round of communication to achieve comparable success. In particular, such a strategy would have a communication rate going to 0 in the worst interaction case as the length of the protocols increases, in contrast to our strategy, which has a communication rate proportional to the capacity of the channel used. Under adversarial noise, our strategy can withstand error rates up to 1/2 when parties preshare perfect entanglement, and this even if they are only allowed noisy classical communication. We show that this is optimal. This is in contrast to the case of the naive strategy, which would not work for any constant fraction of errors in this model. When the parties do not preshare entanglement, we show how to tolerate adversarial error rates close to the maximum tolerable for one-way quantum data transmission. In a random noise setting with a quantum channel of capacity Q > 0, the communication rate is proportional to Q.