dorsal/arxiv
View SchemaMultiparty Quantum Communication Complexity
| Authors | Harry Buhrman, Wim van Dam, Peter Hoyer, Alain Tapp |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9710054 |
| URL | https://arxiv.org/abs/quant-ph/9710054 |
| DOI | 10.1103/PhysRevA.60.2737 |
| Journal | Phys.Rev. A60 (1999) 2737-2741 |
Abstract
Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of k parties hold some partial input data to some fixed k-variable function f. The communication complexity of f is the minimum number of classical bits required to be broadcasted for every party to know the value of f on their inputs. We construct a function G such that for the one-round communication model and three parties, G can be computed with n+1 bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of G is (3/2)n + 1. Next we generalize this function to a function F. We show that if the parties share prior quantum entanglement, then the communication complexity of F is exactly k. We also show that if no entangled particles are provided, then the communication complexity of F is roughly k*log(k). These two results prove for the first time communication complexity separations better than a constant number of bits.
{
"annotation_id": "1e84488a-d6bf-489b-bce2-900acfaca7df",
"date_created": "2026-03-02T18:02:41.235000Z",
"date_modified": "2026-03-02T18:02:41.235000Z",
"file_hash": "bc2770c4181d6dd5ecc528926b9d1971ea780447dbf4bee3ebbe4393f0539a97",
"private": false,
"record": {
"abstract": "Quantum entanglement cannot be used to achieve direct communication between\nremote parties, but it can reduce the communication needed for some problems.\nLet each of k parties hold some partial input data to some fixed k-variable\nfunction f. The communication complexity of f is the minimum number of\nclassical bits required to be broadcasted for every party to know the value of\nf on their inputs.\n We construct a function G such that for the one-round communication model and\nthree parties, G can be computed with n+1 bits of communication when the\nparties share prior entanglement. We then show that without entangled\nparticles, the one-round communication complexity of G is (3/2)n + 1. Next we\ngeneralize this function to a function F. We show that if the parties share\nprior quantum entanglement, then the communication complexity of F is exactly\nk. We also show that if no entangled particles are provided, then the\ncommunication complexity of F is roughly k*log(k).\n These two results prove for the first time communication complexity\nseparations better than a constant number of bits.",
"arxiv_id": "quant-ph/9710054",
"authors": [
"Harry Buhrman",
"Wim van Dam",
"Peter Hoyer",
"Alain Tapp"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.60.2737",
"journal_ref": "Phys.Rev. A60 (1999) 2737-2741",
"title": "Multiparty Quantum Communication Complexity",
"url": "https://arxiv.org/abs/quant-ph/9710054"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "97b6debc-bfab-4f82-9e74-e97c904be05c",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}