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.
I propose to 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.
My thesis will focus on the communication complexity of the correlation
and entanglement distillation protocols. In designing error correcting
codes, efficiency is one of the main concerns. One wants to construct
an error correcting code with the least possible redundancy while
being able to withhold the highest rate of noise. In correlation and
entanglement distillation protocols, the efficiency is measured by the
amount the communication between Alice and Bob, and thus it is
important to design protocols with minimal amount of communication. My
study concerns the minimal amount the communication needed for
distillation.
I will present a number of known results concerning communication
complexity for protocols over various noise models, which are
mathematically models for different types of correlation
corruption. These results span both classical and quantum information
theory, and have connections to other areas of computer science,
including cryptography and computational complexity.
I propose to continue the project of understanding communication
complexity of correlation/entanglement distillation as my thesis
work.