Editing Communication complexity (section)

== 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 communication complexity have been proposed; for a survey see the suggested text by G. Brassard.

The first one is the [[Quantum entanglement|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 (see an application in [[#Collapse_of_Randomized_Communication_Complexity|Collapse of Randomized Communication Complexity]]).

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