期刊
SIAM JOURNAL ON COMPUTING
卷 30, 期 6, 页码 1829-1841出版社
SIAM PUBLICATIONS
DOI: 10.1137/S0097539797324886
关键词
complexity theory; communication complexity; quantum computing
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据