The quantum communication complexity of sampling

Sampling is an important primitive ill probabilistic and quantum algorithms. In the spirit of communication complexity, given a function f : X x Y --> {0, 1} and a probability distribution D, over X x Y, we define the sampling complexity of (f, D) as the minimum number of bits Alice and Bob must communicate far Alice to pick x is an element of X and Bob to pick y is an element of Y as well as a value 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.