On rounds in quantum communication
| dc.creator | Klauck, Hartmut | |
| dc.date | 2000-04-26 | |
| dc.date | 2001-06-28 | |
| dc.date.accessioned | 2026-07-07T05:59:54Z | |
| dc.date.available | 2026-07-07T05:59:54Z | |
| dc.description | 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 $Ω(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 $Ω(n^{1/k})$ for $k=O(1)$. | |
| dc.description | 21 pages, LaTeX. Partially rewritten and bugs removed. Appears joined with quant-ph/0005106 at 33rd STOC | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0004100 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0004100 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/88852 | |
| dc.subject | Quantum Physics | |
| dc.title | On rounds in quantum communication | |
| dc.type | text |