Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 2001 | public
Book Section - Chapter

Interaction in quantum communication and the complexity of set disjointness

Abstract

One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios there are ways of conveying information with exponentially fewer qubits than possible classically [3, 26]. Moreover, these methods have a very simple structure---they involve only few message exchanges between the communicating parties. We consider the question as to 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, thus answering the above question in the negative. This in particular proves a round hierarchy theorem for quantum communication complexity, and implies via a simple reduction, an Ω(N^(1/k)) lower bound for k message protocols for Set Disjointness for constant k. Our result builds on two primitives, local transitions in bi-partite states (based on previous work) and average encoding which may be of significance in other contexts as well.

Additional Information

© 2001 ACM. Supported by the EU 5th framework program QAIP IST-1999-11234 and by NWO grant 612.055.001. Supported by Charles Lee Powell Foundation, NSF grant CCR 98761722, and Institute for Quantum Information. This work was done while the author was at University of California, Berkeley, supported by a JSEP grant and NSF grant CCR 9800024, and later at DIMACS Center and AT&T Labs, supported by NSF grants STC 91-19999, CCR 99-06105 and EIA 00-80234. Most of this work was done while the author was at the University of California at Berkeley, and supported in part by a David and Lucile Packard Fellowship for Science and Engineering and NSF NYI Grant CCR-9457799. This work was done while the author was on leave at the University of California at Berkeley. Supported in part by a David and Lucile Packard Fellowship for Science and Engineering, NSF Grant CCR-9912428, NSF NYI Grant CCR-9457799, and an Alfred P. Sloan Research Fellowship.

Additional details

Created:
August 19, 2023
Modified:
October 23, 2023