Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2, 2003 | public
Journal Article Open

The quantum communication complexity of sampling


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.

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.


Files (216.1 kB)
Name Size Download all
216.1 kB Preview Download

Additional details

September 13, 2023
October 23, 2023