Name
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(N1k/) 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 |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/TIT.2007.896888 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
communication complexity,correlation methods,message passing,protocols,quantum communication,correlation,information-theoretic lemmas,message exchange,quantum communication complexity,quantum protocol,round hierarchy theorem,Average encoding theorem,Hellinger distance,entanglement-assisted communication,informational distance,pointer jumping,quantum communication complexity,quantum information theory,round complexity,round reduction,set disjointness | Discrete mathematics,Quantum,Combinatorics,Quantum entanglement,Upper and lower bounds,Computer science,Theoretical computer science,Communication complexity,Quantum information science,Quantum information,Qubit,Message passing | Journal |
Volume | Issue | ISSN |
53 | 6 | 0018-9448 |
Citations | PageRank | References |
11 | 0.62 | 27 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hartmut Klauck | 1 | 484 | 30.85 |
| Ashwin Nayak | 2 | 645 | 61.76 |
| A. Ta-Shma | 3 | 11 | 0.62 |
| David Zucherman | 4 | 2588 | 266.65 |