TY - JOUR AU - Buhrman, Harry AU - Cleve, Richard AU - Dam, Wim van PY - 1997/06/10 Y2 - 2024/03/29 TI - Quantum Entanglement and Communication Complexity JF - BRICS Report Series JA - BRICS VL - 4 IS - 40 SE - Articles DO - 10.7146/brics.v4i40.18966 UR - https://tidsskrift.dk/brics/article/view/18966 SP - AB - We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles<br />in an entangled quantum state. We show that, although a prior<br />quantum entanglement cannot be used to simulate a communication channel, it can reduce the communication complexity of functions in<br />some cases. Specifically, we show that, for a particular function among three parties (each of which possesses part of the function's input), a prior quantum entanglement enables them to learn the value of the<br />function with only three bits of communication occurring among the parties, whereas, without quantum entanglement, four bits of communication are necessary. We also show that, for a particular two-party probabilistic communication complexity problem, quantum entanglement<br />results in less communication than is required with only classical<br />random correlations (instead of quantum entanglement). These results are a noteworthy contrast to the well-known fact that quantum entanglement cannot be used to actually simulate communication among<br />remote parties. ER -