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 (2003) The quantum communication complexity of sampling. SIAM Journal on Computing, 32 (6). pp. 1570-1585. ISSN 0097-5397.

See Usage Policy.


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 that Alice and Bob must communicate for Alice to pick x ∈ X and Bob to pick y ∈ Y as well as a value z such that 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 models. We give several variants of a definition. We completely characterize some of these variants 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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2003 Society for Industrial and Applied Mathematics. Received by the editors April 12, 1999; accepted for publication (in revised form) June 2, 2003; published electronically October 2, 2003. An earlier version of this paper appeared in the Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), Palo Alto, CA, IEEE Computer Society, Washington, DC, 1998, pp. 342–351.
Subject Keywords:communication complexity, quantum communication complexity, quantum information theory, set-disjointness, the log-rank conjecture in communication complexity
Issue or Number:6
Record Number:CaltechAUTHORS:AMBsiamjc03
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:552
Deposited By: Tony Diaz
Deposited On:18 Aug 2005
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page