A Caltech Library Service

The quantum communication complexity of sampling

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.

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

Use this Persistent URL to link to this item:


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:
Schulman, Leonard J.0000-0001-9901-2797
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.
Funding AgencyGrant Number
Israel Science Foundation69/96
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number6128800
Record Number:CaltechAUTHORS:20111213-142315946
Persistent URL:
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:28455
Deposited By: Tony Diaz
Deposited On:13 Dec 2011 22:43
Last Modified:09 Nov 2021 16:57

Repository Staff Only: item control page