Journal
SIAM JOURNAL ON COMPUTING
Volume 30, Issue 6, Pages 1829-1841Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S0097539797324886
Keywords
complexity theory; communication complexity; quantum computing
Ask authors/readers for more resources
We consider a variation of the communication complexity scenario, where the parties are supplied with an extra resource: particles in an entangled quantum state. We note that quantum nonlocality can be naturally expressed in the language of communication complexity. These are communication complexity problems where the output is embodied in the correlations between the outputs of the individual parties. Without entanglement, the parties must communicate to produce the required correlations; whereas, with entanglement, no communication is necessary to produce the correlations. In this sense, nonlocality proofs can also be viewed as communication complexity problems where the presence of quantum entanglement reduces the amount of necessary communication. We show how to transform examples of nonlocality into more traditional communication complexity problems, where the output is explicitly determined by each individual party. The resulting problems require communication with or without entanglement, but the required communication is less when entanglement is available. All these results are a noteworthy contrast to the well-known fact that entanglement cannot be used to actually simulate or compress classical communication between remote parties.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available