dorsal/arxiv
View SchemaInteraction in Quantum Communication
| Authors | Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0603135 |
| URL | https://arxiv.org/abs/quant-ph/0603135 |
| DOI | 10.1109/TIT.2007.896888 |
Abstract
In some scenarios there are ways of conveying information with many fewer, even exponentially fewer, qubits than possible classically. Moreover, some of these methods have a very simple structure--they involve only few message exchanges between the communicating parties. It is therefore natural to ask whether every classical protocol may be transformed to a ``simpler'' quantum protocol--one that has similar efficiency, but 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. This, in particular, proves a round hierarchy theorem for quantum communication complexity, and implies, via a simple reduction, an Omega(N^{1/k}) lower bound for k message quantum protocols for Set Disjointness for constant k. Enroute, we prove information-theoretic lemmas, and define a related measure of correlation, the informational distance, that we believe may be of significance in other contexts as well.
{
"annotation_id": "35500d3d-ae58-4b18-84eb-cf5cb24218d6",
"date_created": "2026-03-02T18:02:24.140000Z",
"date_modified": "2026-03-02T18:02:24.140000Z",
"file_hash": "aea51386b715c62ef86d4814220b756d13c0aaf7f9d41041f2acbc9a0dd8698c",
"private": false,
"record": {
"abstract": "In some scenarios there are ways of conveying information with many fewer,\neven exponentially fewer, qubits than possible classically. Moreover, some of\nthese methods have a very simple structure--they involve only few message\nexchanges between the communicating parties. It is therefore natural to ask\nwhether every classical protocol may be transformed to a ``simpler\u0027\u0027 quantum\nprotocol--one that has similar efficiency, but uses fewer message exchanges.\n We show that for any constant k, there is a problem such that its k+1 message\nclassical communication complexity is exponentially smaller than its k message\nquantum communication complexity. This, in particular, proves a round hierarchy\ntheorem for quantum communication complexity, and implies, via a simple\nreduction, an Omega(N^{1/k}) lower bound for k message quantum protocols for\nSet Disjointness for constant k.\n Enroute, we prove information-theoretic lemmas, and define a related measure\nof correlation, the informational distance, that we believe may be of\nsignificance in other contexts as well.",
"arxiv_id": "quant-ph/0603135",
"authors": [
"Hartmut Klauck",
"Ashwin Nayak",
"Amnon Ta-Shma",
"David Zuckerman"
],
"categories": [
"quant-ph",
"cs.CC",
"cs.IT",
"math.IT"
],
"doi": "10.1109/TIT.2007.896888",
"title": "Interaction in Quantum Communication",
"url": "https://arxiv.org/abs/quant-ph/0603135"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9dbdce0b-fd7a-44be-8570-58d6f68ad754",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}