Quantum entanglement and communication complexity

We consider a variation of the communication complexity scenario, where the parties are supplied with an extra resource: particles in an entangled qua ntum state. We note that quantum nonlocality can be naturally expressed in the language of communication complexity. These are communication complexit y problems where the output is embodied in the correlations between the out puts of the individual parties. Without entanglement, the parties must comm unicate to produce the required correlations; whereas, with entanglement, n o communication is necessary to produce the correlations. In this sense, no nlocality proofs can also be viewed as communication complexity problems wh ere the presence of quantum entanglement reduces the amount of necessary co mmunication. We show how to transform examples of nonlocality into more tra ditional communication complexity problems, where the output is explicitly determined by each individual party. The resulting problems require communi cation with or without entanglement, but the required communication is less when entanglement is available. All these results are a noteworthy contras t to the well-known fact that entanglement cannot be used to actually simul ate or compress classical communication between remote parties.