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
- Eprint ID
- 72075
- DOI
- 10.1145/380752.380786
- Resolver ID
- CaltechAUTHORS:20161116-160336653
- IST-1999-11234
- European Union (EU)
- 612.055.001
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)
- Charles Lee Powell Foundation
- CCR 98761722
- NSF
- Institute for Quantum Information, Caltech
- Joint Science Education Project (JSEP)
- CCR 9800024
- NSF
- STC 91-19999
- NSF
- CCR 99-06105
- NSF
- EIA 00-80234
- NSF
- David and Lucile Packard Foundation
- CCR-9457799
- NSF
- CCR-9912428
- NSF
- CCR-9457799
- NSF
- Alfred P. Sloan Foundation
- Created
-
2016-11-17Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field