Quantum Communication Complexity

A distributed information processing task is one where two or more physically separated parties each receive some input data and they are required to compute some quantities based on this data. A simple two-party example is where each party receives a binary string and their goal is to determine whether or not the strings are identical. It is clear that this particular task cannot be accomplished without some communication occurring between the parties. In communication complexity, the amount of communication required to perform distributed information processing tasks is quantified. We shall give examples of information processing tasks that can be accomplished with significant savings in communication when quantum resources are available. These include some intriguing nonlocal effects that were first discovered by John Bell in the 1960s, as well as more recent communication protocols which have connections with quantum algorithms. Taken together, these results complement the well-known fact that bits cannot be compressed by encoding them into qubits.