We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ (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 = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(log n), yet any randomized one-way protocol with bounded error must use Ω(√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.For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(√[3] n log n) bits of communication.
展开▼
机译：我们给出了量子与有界误差随机单向通信复杂度之间的第一个指数分离。具体来说，我们定义了隐藏匹配问题HM n ：Alice输入x∈（0，1） n 作为输入，而Bob获得n坐标上的完美匹配M 。 Bob的目标是输出一个元组[i，j，b]，使得边（i，j）属于匹配的M，并且b = x i ⊕x j 。我们证明HM n 的量子单向通信复杂度为O（log n），但是任何具有有限误差的随机单向协议都必须使用Ω（√n）位通信。以前没有单向通信的渐近间隙。我们的界限也同时存在于同步消息（SM）模型中，因此我们提供了带有公共硬币的量子SM和随机SM之间的首次指数分离。对于HM n 的布尔决策版本，我们证明了量子单向通信复杂度保持为O（log n），零误差随机单向通信复杂度为Ω（n）。我们证明，针对该问题的任何具有有限误差的随机 linear 单向协议都需要Ω（√[3] n log n）位通信。
展开▼
