Ambainis, Andris and Schulman, Leonard J. and TaShma, Amnon and Vazirani, Umesh and Wigderson, Avi (2003) The quantum communication complexity of sampling. SIAM Journal on Computing, 32 (6). pp. 15701585. ISSN 00975397. http://resolver.caltech.edu/CaltechAUTHORS:AMBsiamjc03

PDF
See Usage Policy. 211Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:AMBsiamjc03
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 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 setdisjointness function.
Item Type:  Article 

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, setdisjointness, the logrank conjecture in communication complexity 
Record Number:  CaltechAUTHORS:AMBsiamjc03 
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:AMBsiamjc03 
Alternative URL:  http://dx.doi.org/10.1137/S009753979935476 
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  552 
Collection:  CaltechAUTHORS 
Deposited By:  Tony Diaz 
Deposited On:  18 Aug 2005 
Last Modified:  26 Dec 2012 08:40 
Repository Staff Only: item control page