dorsal/arxiv
View SchemaOn rounds in quantum communication
| Authors | Hartmut Klauck |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0004100 |
| URL | https://arxiv.org/abs/quant-ph/0004100 |
Abstract
We investigate the power of interaction in two player quantum communication protocols. Our main result is a rounds-communication hierarchy for the pointer jumping function $f_k$. We show that $f_k$ needs quantum communication $\Omega(n)$ if Bob starts the communication and the number of rounds is limited to $k$ (for any constant $k$). Trivially, if Alice starts, $O(k\log n)$ communication in $k$ rounds suffices. The lower bound employs a result relating the relative von Neumann entropy between density matrices to their trace distance and uses a new measure of information. We also describe a classical probabilistic $k$ round protocol with communication $O(n/k\cdot(\log^{(k/2)}n+\log k)+k\log n)$ in which Bob starts the communication. Furthermore as a consequence of the lower bound for pointer jumping we show that any $k$ round quantum protocol for the disjointness problem needs communication $\Omega(n^{1/k})$ for $k=O(1)$.
{
"annotation_id": "49b1ea22-820a-4733-8f06-31bf4d85f41e",
"date_created": "2026-03-02T18:01:39.279000Z",
"date_modified": "2026-03-02T18:01:39.279000Z",
"file_hash": "335464d68d5b915a94fc5ab442ca441d21c6cecfcf3863573cab0742db8ad6bc",
"private": false,
"record": {
"abstract": "We investigate the power of interaction in two player quantum communication\nprotocols. Our main result is a rounds-communication hierarchy for the pointer\njumping function $f_k$. We show that $f_k$ needs quantum communication\n$\\Omega(n)$ if Bob starts the communication and the number of rounds is limited\nto $k$ (for any constant $k$). Trivially, if Alice starts, $O(k\\log n)$\ncommunication in $k$ rounds suffices. The lower bound employs a result relating\nthe relative von Neumann entropy between density matrices to their trace\ndistance and uses a new measure of information. We also describe a classical\nprobabilistic $k$ round protocol with communication\n$O(n/k\\cdot(\\log^{(k/2)}n+\\log k)+k\\log n)$ in which Bob starts the\ncommunication. Furthermore as a consequence of the lower bound for pointer\njumping we show that any $k$ round quantum protocol for the disjointness\nproblem needs communication $\\Omega(n^{1/k})$ for $k=O(1)$.",
"arxiv_id": "quant-ph/0004100",
"authors": [
"Hartmut Klauck"
],
"categories": [
"quant-ph"
],
"title": "On rounds in quantum communication",
"url": "https://arxiv.org/abs/quant-ph/0004100"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8c5f549b-64cf-4399-83c5-4cd0b93c3bd3",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}