CaltechAUTHORS
  A Caltech Library Service

Interaction in quantum communication and the complexity of set disjointness

Klauck, Hartmut and Nayak, Ashwin and Ta-Shma, Amnon and Zuckerman, David (2001) Interaction in quantum communication and the complexity of set disjointness. In: STOC '01 Proceedings of the thirty-third annual ACM symposium on Theory of computing. ACM , New York, NY, pp. 124-133. ISBN 1-58113-349-9. https://resolver.caltech.edu/CaltechAUTHORS:20161116-160336653

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161116-160336653

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/380752.380786DOIArticle
http://dl.acm.org/citation.cfm?doid=380752.380786PublisherArticle
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.
Funders:
Funding AgencyGrant Number
European Union (EU)IST-1999-11234
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)612.055.001
Charles Lee Powell FoundationUNSPECIFIED
NSFCCR 98761722
Institute for Quantum Information, CaltechUNSPECIFIED
Joint Science Education Project (JSEP)UNSPECIFIED
NSFCCR 9800024
NSFSTC 91-19999
NSFCCR 99-06105
NSFEIA 00-80234
David and Lucile Packard FoundationUNSPECIFIED
NSFCCR-9457799
NSFCCR-9912428
NSFCCR-9457799
Alfred P. Sloan FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20161116-160336653
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20161116-160336653
Official Citation:Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, and David Zuckerman. 2001. Interaction in quantum communication and the complexity of set disjointness. In Proceedings of the thirty-third annual ACM symposium on Theory of computing (STOC '01). ACM, New York, NY, USA, 124-133. DOI=http://dx.doi.org/10.1145/380752.380786
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:72075
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:17 Nov 2016 00:47
Last Modified:03 Oct 2019 16:14

Repository Staff Only: item control page