dorsal/arxiv
View SchemaA lower bound on entanglement-assisted quantum communication complexity
| Authors | Ashley Montanaro, Andreas Winter |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0610085 |
| URL | https://arxiv.org/abs/quant-ph/0610085 |
| Journal | In Proc. ICALP'07, 2007 |
Abstract
We prove a general lower bound on the bounded-error entanglement-assisted quantum communication complexity of Boolean functions. The bound is based on the concept that any classical or quantum protocol to evaluate a function on distributed inputs can be turned into a quantum communication protocol. As an application of this bound, we give a very simple proof of the statement that almost all Boolean functions on n+n bits have linear communication complexity, even in the presence of unlimited entanglement.
{
"annotation_id": "769534c1-ff48-4577-a7dd-5a39131dbfba",
"date_created": "2026-03-02T18:02:30.845000Z",
"date_modified": "2026-03-02T18:02:30.845000Z",
"file_hash": "787ac9fb63d91b1c8a08f762baabb32349a49e2bbb8b80a32f1499254810d791",
"private": false,
"record": {
"abstract": "We prove a general lower bound on the bounded-error entanglement-assisted\nquantum communication complexity of Boolean functions. The bound is based on\nthe concept that any classical or quantum protocol to evaluate a function on\ndistributed inputs can be turned into a quantum communication protocol. As an\napplication of this bound, we give a very simple proof of the statement that\nalmost all Boolean functions on n+n bits have linear communication complexity,\neven in the presence of unlimited entanglement.",
"arxiv_id": "quant-ph/0610085",
"authors": [
"Ashley Montanaro",
"Andreas Winter"
],
"categories": [
"quant-ph"
],
"journal_ref": "In Proc. ICALP\u002707, 2007",
"title": "A lower bound on entanglement-assisted quantum communication complexity",
"url": "https://arxiv.org/abs/quant-ph/0610085"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b5455a6a-0734-4854-9969-dfef55721dd9",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}