Ambainis, Andris and Schulman, Leonard J. and Ta-Shma, Amnon and Vazirani, Umesh and Wigderson, Avi (1998) The quantum communication complexity of sampling. In: 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, pp. 342-351. ISBN 0-8186-9172-7. https://resolver.caltech.edu/CaltechAUTHORS:20111213-142315946
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:20111213-142315946
Abstract
Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function f: X × Y → {0,1} and a probability distribution D over X × Y, we define the sampling complexity of (f,D) as the minimum number of bits Alice and Bob must communicate for Alice to pick x ∈ X and Bob to pick y ∈ Y as well as a valve z s.t. the resulting distribution of (x,y,z) is close to the distribution (D,f(D)). In this paper we initiate the study of sampling complexity, in both the classical and quantum model. We give several variants of the definition. We completely characterize some of these tasks, and give upper and lower bounds on others. In particular this allows us to establish an exponential gap between quantum and classical sampling complexity, for the set disjointness function. This is the first exponential gap for any task where the classical probabilistic algorithm is allowed to err.
| Item Type: | Book Section | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| ORCID: |
| |||||||||
| Additional Information: | © 1998 IEEE. Date of Current Version: 06 August 2002. This research was supported by NSF Grant CCR-9800024, and a JSEP grant. This research was supported by grant number 69/96 of the Israel Science Foundation, founded by the Israel Academy for Sciences and Humanities. The authors would like to thanks Dorit Aharonov, Ike Chuang, Michael Nielsen, Ran Raz and Steven Rudich for very helpful discussions. We thanks Michael Nielsen for showing us how to extend the upper bound of Theorem 1 to the case where Mψ is not normal. | |||||||||
| Funders: |
| |||||||||
| Other Numbering System: |
| |||||||||
| DOI: | 10.1109/SFCS.1998.743480 | |||||||||
| Record Number: | CaltechAUTHORS:20111213-142315946 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20111213-142315946 | |||||||||
| Official Citation: | Ambainis, A.; Schulman, L.J.; Ta-Shma, A.; Vazirani, U.; Wigderson, A.; , "The quantum communication complexity of sampling," Foundations of Computer Science, 1998. Proceedings.39th Annual Symposium on , vol., no., pp.342-351, 8-11 Nov 1998 doi: 10.1109/SFCS.1998.743480 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=743480&isnumber=15971 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 28455 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Tony Diaz | |||||||||
| Deposited On: | 13 Dec 2011 22:43 | |||||||||
| Last Modified: | 09 Nov 2021 16:57 |
Repository Staff Only: item control page
