Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-036 | 27th March 2004 00:00

Exponential Separation of Quantum and Classical One-Way Communication Complexity

RSS-Feed




TR04-036
Authors: Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis
Publication: 14th April 2004 20:39
Downloads: 1495
Keywords: 


Abstract:

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x in {0,1}^n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) such that the edge (i,j) belongs to the matching M and b is the xor of x_i and x_j. We prove that the quantum one-way communication complexity of HM_n is O(log n), yet any randomized one-way protocol with bounded error must use
\Omega(\sqrt{n}) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM) and hence we provide the first exponential separation between quantum SM and randomized SM with public
coins. <P>

For a Boolean decision version of HM_n, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is \Omega(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires \Omega(\sqrt[3]{n log n}) bits of communication.



ISSN 1433-8092 | Imprint