Computer Science Department
School of Computer Science, Carnegie Mellon University
On the Communication Complexity of Correlation
Traditionally correlation repair is done via a preventive strategy, namely error correction. Using this strategy, Alice encodes her information using an error correcting code or a quantum error correcting code before sending it through a noisy channel to Bob, who then decodes and recovers the original information. Error correcting codes and quantum error correcting codes are extremely useful objects in information theory with numerous applications in many other areas of science and technology. They are well studied and well understood. However they have limitations. We shall show that some assumptions used by error correction are not sound in many scenarios and make the preventive strategy unsuitable.
We study the alternative strategy of correlation repair. Using this strategy, Alice and Bob start by sharing imperfectly correlated information, and then engage in a protocol to "distill" the correlation/entanglement via communication. We call these protocols (classical) correlation distillation protocols and (quantum) entanglement distillation protocols. We show that such a reparative strategy can be as efficient as the preventive strategy. Furthermore, the reparative strategy is more flexible, and in particular, quantum entanglement distillation protocols play a very important role in quantum information theory.
We focus on the communication complexity of the correlation and entanglement distillation protocols. Our study is concerned with the minimal amount the communication needed for distillation.
We present a number of results concerning communication complexity for protocols over various noise models. These results span both classical and quantum information theory, and have connections to other areas of computer science, including cryptography and computational complexity.