Quantum Communication Complexity


Although entanglement cannot be used for direct communication (as otherwise it would be superluminal), it surprisingly can produce effects as if some information had been transferred: entanglement can save on classical communication when remote parties need to accomplish a joint task. A typical problem is computation of a function whose inputs are distributed among the remote parties. The minimal amount of information that has to be exchanged to accomplish the task defines its complexity.

We showed that in certain communication complexity protocols entangled states are useful only to the extent that they exhibit nonlocal correlations. More precisely, we demonstrated that for every Bell’s inequality there exists a communication complexity problem, for which the protocol assisted by states which violate the inequality is more efficient than any classical protocol [1]. On this basis we developed protocols that exploit entanglement between qubits, qutrits and higher dimensional states [1-2].

In Ref. [3] you can read about a simple but insightful example that illustrates how entanglement can help separated individuals to find each other even in the lack of any communication whatsoever.

Recently, we showed that “the quantum superposition of the direction of communication” is a useful resource for communication complexity. We found a task for which such a superposition allows for an exponential saving in communication, compared to one-way quantum (or classical) communication [4] (See also “Quantum Theory on Indefinite Causal Structures”).


Two partners are on the two poles of the Earth (left). From each pole there are three paths (red 1, yellow 2 and blue 3) and for each path there are two directions (+ and -) (right, view from the North pole). Which path and direction should the partners take to find each other at the equatorial line in the lack of any communication? (For an entanglement-assistant solution see Ref. [3])

[1] Č. Brukner, M. Zukowski, J.-W. Pan and A. Zeilinger, Bell's inequality and Quantum Communication Complexity, Phys. Rev. Lett. 92, 127901 (2004).

[2] Č. Brukner, M. Zukowski and A. Zeilinger, Quantum Communication Complexity Protocol with Two Entangled Qutrits, Phys. Rev. Lett. 89,  197901 (2002).

[3] Č. Brukner, N. Paunkovic, T. Rudolph and V. Vedral, Entanglement-assisted Orientation in Space, Int. J. of Quant. Inf. 4, 365 (2006). Preprint at quant-ph/0509123.

[4] P. A. Guérin, A. Feix, M. Araújo and Č. Brukner, Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication, Phys. Rev. Lett. 117, 100502 (2016).