Journal
SIAM JOURNAL ON COMPUTING
Volume 32, Issue 6, Pages 1570-1585Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S009753979935476
Keywords
communication complexity; quantum communication complexity; quantum information theory; set-disjointness; the log-rank conjecture in communication complexity
Ask authors/readers for more resources
Sampling is an important primitive in 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 de. ne the sampling complexity of ( f, D) as the minimum number of bits that Alice and Bob must communicate for 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 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available