Quantum communication complexity

Classical communication complexity

The notion of communication complexity (CC) was introduced by Yao in 1979, who investigated the following problem involving two separated parties (Alice and Bob). Alice receives a n-bit string x and Bob another n-bit string y, and the goal is for one of them (say Bob) to compute a certain function f(x,y) with the least amount of communication between them. Note that here we are not concerned about the number of computational steps, or the size of the computer memory used. Communication complexity tries to quantify the amount of communication required for such distributed computations.

Of course they can always succeed by having Alice send her whole n-bit string to Bob, who then computes the function, but the idea here is to find clever ways of calculating f with less than n bits of communication.

This abstract problem is relevant in many contexts: in VLSI circuit design, for example, one wants to minimize energy use by decreasing the amount of electric signals required between the different components during a distributed computation. The problem is also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan.

Quantum communication complexity

Quantum communication complexity tries to quantify the communication reduction possible by using quantum effects during a distributed computation.

At least three quantum generalizations of CC have been proposed; for a survey see the suggested text by G. Brassard.

The first one is the qubit-communication model, where the parties can use quantum communication instead of classical communication, for example by exchanging photons through an optical fiber.

In a second model the communication is still performed with classical bits, but the parties are allowed to manipulate an unlimited supply of quantum entangled states as part of their protocols. By doing measurements on their entangled states, the parties can save on classical communication during a distributed computation.

The third model involves access to previously shared entanglement in addition to qubit communication, and is the least explored of the three quantum models.

References:

• Kushilevitz, E. and Nisan, N. Communication complexity. Cambridge University Press, 1997.
• Brassard, G. Quantum communication complexity: a survey. http://arxiv.org/abs/quant-ph/0101005 (http://arxiv.org/abs/quant-ph/0101005)