The quantum communication complexity of sampling
Abstract
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.
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.Additional details
- Eprint ID
- 28455
- DOI
- 10.1109/SFCS.1998.743480
- Resolver ID
- CaltechAUTHORS:20111213-142315946
- NSF
- CCR-9800024
- JSEP
- Israel Science Foundation
- 69/96
- Created
-
2011-12-13Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 6128800