Since 2014
Quantum Entanglement and Communication Complexity
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Quantum Entanglement and Communication Complexity
|
|
| Creator |
Buhrman, Harry
Cleve, Richard Dam, Wim van |
|
| Description |
We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particlesin an entangled quantum state. We show that, although a priorquantum entanglement cannot be used to simulate a communication channel, it can reduce the communication complexity of functions insome 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 thefunction 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 entanglementresults in less communication than is required with only classicalrandom 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 amongremote parties.
|
|
| Publisher |
Aarhus University
|
|
| Date |
1997-06-10
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/18966
10.7146/brics.v4i40.18966 |
|
| Source |
BRICS Report Series; No 40 (1997): RS-40 Quantum Entanglement and Communication Complexity
BRICS Report Series; Nr. 40 (1997): RS-40 Quantum Entanglement and Communication Complexity 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/18966/16605
|
|