dorsal/arxiv
View SchemaQuantum Entanglement and Communication Complexity
| Authors | Harry Buhrman, Richard Cleve, Wim van Dam |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9705033 |
| URL | https://arxiv.org/abs/quant-ph/9705033 |
| DOI | 10.1137/S0097539797324886 |
| Journal | SIAM J.Comput. 30 (2001) 1829-1841 |
Abstract
We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in 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.
{
"annotation_id": "e5fcf046-48aa-48b0-863f-78fd0cf67f15",
"date_created": "2026-03-02T18:02:41.156000Z",
"date_modified": "2026-03-02T18:02:41.156000Z",
"file_hash": "50f9031047e942c2d99ddb53cec3abab0918e99998461bca839085714258b382",
"private": false,
"record": {
"abstract": "We consider a variation of the multi-party communication complexity scenario\nwhere the parties are supplied with an extra resource: particles in an\nentangled quantum state. We show that, although a prior quantum entanglement\ncannot be used to simulate a communication channel, it can reduce the\ncommunication complexity of functions in some cases. Specifically, we show\nthat, for a particular function among three parties (each of which possesses\npart of the function\u0027s input), a prior quantum entanglement enables them to\nlearn the value of the function with only three bits of communication occurring\namong the parties, whereas, without quantum entanglement, four bits of\ncommunication are necessary. We also show that, for a particular two-party\nprobabilistic communication complexity problem, quantum entanglement results in\nless communication than is required with only classical random correlations\n(instead of quantum entanglement). These results are a noteworthy contrast to\nthe well-known fact that quantum entanglement cannot be used to actually\nsimulate communication among remote parties.",
"arxiv_id": "quant-ph/9705033",
"authors": [
"Harry Buhrman",
"Richard Cleve",
"Wim van Dam"
],
"categories": [
"quant-ph"
],
"doi": "10.1137/S0097539797324886",
"journal_ref": "SIAM J.Comput. 30 (2001) 1829-1841",
"title": "Quantum Entanglement and Communication Complexity",
"url": "https://arxiv.org/abs/quant-ph/9705033"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "27e690ec-854a-4038-b73e-14ce2b4cb8ac",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}