On the communication complexity of correlation and entanglement distillation

One of the recurring themes in information theory and quantum information theory is correlation corruption and correlation recover. Correlation corruption refers to the situation where Alice and Bob share information that is not perfectly correlated (or perfectly entangled, if they share quantum information). Correlation corruption arises in many natural situations, including transmitting information through a noisy channel, measuring a noisy signal source, quantum decoherence, and adversarial distortion. Correlation recovery refers to the action Alice and Bob takes to "restore" the correlation/entanglement by agreeing on some perfectly correlated/entangled information.; 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, known as the reparative strategy. Using this strategy, Alice and Bob start by sharing imperfectly correlated (raw) 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, in that it doesn't have the limitations suffered by error correction. We also point out that in particular, quantum entanglement distillation protocols play a very important role in quantum information theory. Despite the significance of these protocols, they have received much less attention than error correcting codes and are much less well understood. (Abstract shortened by UMI.)...