Quantum Communication Complexity

Although entanglement on its own cannot be used for communication, it surprisingly can produce effects as if information had been transferred: entanglement can save on classical communication when the goal is to compute a function whose input data is distributed among remote parties. The minimal amount of information that has to be exchanged to accomplish the task defines its complexity. A reduction of communication complexity is important for speeding up distributed computations, for example within VLSI circuits.

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 - including even those which are not known yet - there always exists a communication complexity problem, for which the protocol assisted by states which violate the inequality is more efficient than any classical protocol. On this basis we developed protocols that exploit entanglement between qubits, qutrits and higher dimensional states. In a separate work we demonstrated that entanglement can help separated individuals in making decisions if their goal is to find each other even in the lack of any communication between them.

Fig.: 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 the solution see Int. J. of Quant. Inf. 4, 365 (2006)) 

C. Brukner, M. Zukowski, J.-W. Pan and A. Zeilinger

Bell's inequality and Quantum Communication Complexity

Phys. Rev. Lett. 92, 127901 (2004) / e-print

C. Brukner, M. Zukowski, and A. Zeilinger

Quantum communication complexity protocol with two entangled qutrits

Phys. Rev. Lett. 89,  197901 (2002) / e-print

C.Brukner, N. Paunkovic, T. Rudolph & V. Vedral

Entanglement-assisted Orientation in Space

Int. J. of Quant. Inf. 4, 365 (2006) / e-print