dorsal/arxiv
View SchemaInteraction in Quantum Communication Complexity
| Authors | Ashwin Nayak, Amnon Ta-Shma, David Zuckerman |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0005106 |
| URL | https://arxiv.org/abs/quant-ph/0005106 |
Abstract
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet there are ways of conveying information with exponentially fewer qubits than possible classically. Moreover, these methods have a very simple structure---they involve little interaction between the communicating parties. We look more closely at the ways in which information encoded in quantum states may be manipulated, and consider the question as to whether every classical protocol may be transformed to a ``simpler'' quantum protocol of similar efficiency. By a simpler protocol, we mean a protocol that uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity, thus answering the above question in the negative. Our result builds on two primitives, local transitions in bi-partite states (based on previous work) and average encoding which may be of significance in other applications as well.
{
"annotation_id": "cc90756a-84b3-4c4b-aedd-9c9d5dde3bdd",
"date_created": "2026-03-02T18:01:39.322000Z",
"date_modified": "2026-03-02T18:01:39.322000Z",
"file_hash": "dac5751bdee6f5c707c0f74cbb020d8229cfd72354acdd54710db6858498734a",
"private": false,
"record": {
"abstract": "One of the most intriguing facts about communication using quantum states is\nthat these states cannot be used to transmit more classical bits than the\nnumber of qubits used, yet there are ways of conveying information with\nexponentially fewer qubits than possible classically. Moreover, these methods\nhave a very simple structure---they involve little interaction between the\ncommunicating parties. We look more closely at the ways in which information\nencoded in quantum states may be manipulated, and consider the question as to\nwhether every classical protocol may be transformed to a ``simpler\u0027\u0027 quantum\nprotocol of similar efficiency. By a simpler protocol, we mean a protocol that\nuses fewer message exchanges. We show that for any constant k, there is a\nproblem such that its k+1 message classical communication complexity is\nexponentially smaller than its k message quantum communication complexity, thus\nanswering the above question in the negative. Our result builds on two\nprimitives, local transitions in bi-partite states (based on previous work) and\naverage encoding which may be of significance in other applications as well.",
"arxiv_id": "quant-ph/0005106",
"authors": [
"Ashwin Nayak",
"Amnon Ta-Shma",
"David Zuckerman"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Interaction in Quantum Communication Complexity",
"url": "https://arxiv.org/abs/quant-ph/0005106"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b3be0bef-baad-445d-8485-f3ccd86cac2c",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}