Interaction in Quantum Communication

DOI10.1109/TIT.2007.896888zbMATH Open1323.94066DBLPjournals/tit/KlauckNTZ07arXivquant-ph/0603135WikidataQ58040224 ScholiaQ58040224MaRDI QIDQ3548810FDOQ3548810

Authors: Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman 

Publication date: 21 December 2008

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/quant-ph/0603135

Recommendations

• Quantum communications
• Quantum communication in a quantum network
• scientific article; zbMATH DE number 1796842
• Noisy interactive quantum communication
• scientific article; zbMATH DE number 1816892
• Communicating quantum processes
• Entanglement-based communications
• Classical Communication Over a Quantum Interference Channel
• Communication via an entangled coherent quantum network
• Quantum communication networks

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Cited In (17)

• Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test
• Von Neumann entropy penalization and low-rank matrix estimation
• Quantum communication and complexity.
• Quantum information complexity
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Communication of partial ignorance with qubits
• Estimation of low rank density matrices: bounds in Schatten norms and other distances
• Noisy interactive quantum communication
• Transformations on density operators that leave the Holevo bound invariant
• Title not available (Why is that?)
• Title not available (Why is that?)
• Communication and information complexity
• New limits to classical and quantum instance compression
• On communication relations for quons
• Pointer chasing via triangular discrimination
• Interaction in quantum communication and the complexity of \textsc{Set Disjointness}
• Classical and Quantum Computations with Restricted Memory

This page was built for publication: Interaction in Quantum Communication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548810)