dorsal/arxiv
View SchemaQuantum Communication Complexity (A Survey)
| Authors | Gilles Brassard |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0101005 |
| URL | https://arxiv.org/abs/quant-ph/0101005 |
Abstract
Can quantum communication be more efficient than its classical counterpart? Holevo's theorem rules out the possibility of communicating more than n bits of classical information by the transmission of n quantum bits --- unless the two parties are entangled, in which case twice as many classical bits can be communicated but no more. In apparent contradiction, there are distributed computational tasks for which quantum communication cannot be simulated efficiently by classical means. In extreme cases, the effect of transmitting quantum bits cannot be achieved classically short of transmitting an exponentially larger number of bits. In a similar vein, can entanglement be used to save on classical communication? It is well known that entanglement on its own is useless for the transmission of information. Yet, there are distributed tasks that cannot be accomplished at all in a classical world when communication is not allowed, but that become possible if the non-communicating parties share prior entanglement. This leads to the question of how expensive it is, in terms of classical communication, to provide an exact simulation of the spooky power of entanglement.
{
"annotation_id": "bbd40b09-4a52-4851-b650-66faffdedc1c",
"date_created": "2026-03-02T18:01:42.260000Z",
"date_modified": "2026-03-02T18:01:42.260000Z",
"file_hash": "fc65842f5f5a0ef95fb7642648399f5739464d13d0f8784b1ae66c50797d6f47",
"private": false,
"record": {
"abstract": "Can quantum communication be more efficient than its classical counterpart?\nHolevo\u0027s theorem rules out the possibility of communicating more than n bits of\nclassical information by the transmission of n quantum bits --- unless the two\nparties are entangled, in which case twice as many classical bits can be\ncommunicated but no more. In apparent contradiction, there are distributed\ncomputational tasks for which quantum communication cannot be simulated\nefficiently by classical means. In extreme cases, the effect of transmitting\nquantum bits cannot be achieved classically short of transmitting an\nexponentially larger number of bits.\n In a similar vein, can entanglement be used to save on classical\ncommunication? It is well known that entanglement on its own is useless for the\ntransmission of information. Yet, there are distributed tasks that cannot be\naccomplished at all in a classical world when communication is not allowed, but\nthat become possible if the non-communicating parties share prior entanglement.\nThis leads to the question of how expensive it is, in terms of classical\ncommunication, to provide an exact simulation of the spooky power of\nentanglement.",
"arxiv_id": "quant-ph/0101005",
"authors": [
"Gilles Brassard"
],
"categories": [
"quant-ph"
],
"title": "Quantum Communication Complexity (A Survey)",
"url": "https://arxiv.org/abs/quant-ph/0101005"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cd9a5939-98b6-4f4f-93d6-7a800310eb32",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}