Quantum Entanglement and Communication Complexity
DOI:
https://doi.org/10.7146/brics.v4i40.18966Resumé
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 prior
quantum entanglement cannot be used to simulate a communication channel, it can reduce the communication complexity of functions in
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
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
results in less communication than is required with only classical
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
remote parties.
Downloads
Publiceret
1997-06-10
Citation/Eksport
Buhrman, H., Cleve, R., & Dam, W. van. (1997). Quantum Entanglement and Communication Complexity. BRICS Report Series, 4(40). https://doi.org/10.7146/brics.v4i40.18966
Nummer
Sektion
Artikler
Licens
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).