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 will be of importance for eventual real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. These are the first results concerning the quantum version of this problem, originally 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 with arbitrarily small error. Our simulation strategy has a far higher communication rate than a naive one that encodes separately each particular round of communication to achieve comparable success. 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, for arbitrarily small ε > 0, error rates as high as 1/2 -- ε when parties preshare perfect entanglement, but the classical channel is noisy. We show that this is optimal. Note that in this model, the naive strategy would not work for any constant fraction of errors. We provide extension of these results in several other models of communication, including when also the entanglement is noisy, and when there is no pre-shared entanglement but communication is quantum and noisy. We also study the case of random noise, for which we provide simulation protocols with positive communication rates and no pre-shared entanglement over some quantum channels with quantum capacity Q = 0, proving that Q is in general not the right characterization of a channel's capacity for interactive quantum communication. Our results are stated for a general quantum communication protocol in which Alice and Bob collaborate, and hold in particular in the quantum communication complexity settings of the Yao and Cleve-Buhrman models.

Authors

• Gilles Brassard
• Ashwin Nayak 0001
• Alain Tapp
• Dave Touchette
• Falk Unger

Keywords

• Protocols
• Noise measurement
• Error analysis
• Registers
• Adaptation models
• Quantum mechanics
• Quantum Information
• Noisy Communication
• Error Rate
• Channel Capacity
• Complex Communication
• Simulation Scheme
• Simulation Protocol
• Communication Rate
• Communication Capacity
• Classical Setting
• Noisy Channels
• Communication Rounds
• Quantum Channel
• Quantum Information Theory
• Results Of Other Models
• Corruption
• Error Model
• State Formation
• Constant Factor
• Coding Tree
• Classical Protocol
• Decoding Error
• Pauli Matrices
• Quantum Model
• Secret Key
• Quantum Error Correction
• Dilation Factor
• Classical Information
• Interaction Scenarios
• Coding Theory
• Communication Complexity
• Quantum Computation and Information