CaltechAUTHORS
  A Caltech Library Service

The quantum communication complexity of sampling

Ambainis, Andris and Schulman, Leonard J. and Ta-Shma, Amnon and Vazirani, Umesh and Wigderson, Avi (2003) The quantum communication complexity of sampling. SIAM Journal on Computing, 32 (6). pp. 1570-1585. ISSN 0097-5397. http://resolver.caltech.edu/CaltechAUTHORS:AMBsiamjc03

[img]
Preview
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 set-disjointness 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, set-disjointness, the log-rank 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