期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In communication complexity, two players each have an input and they wish to compute some function of the joint inputs. This has been the object of much study and a wide variety of lower bound methods have been introduced to address the problem of showing lower bounds on communication. Recently, Jain and Klauck introduced the partition bound, which subsumes many of the known methods, in particular factorization norm, discrepancy, and the rectangle (corruption) bound.
Physicists have considered a closely related scenario where two players share a predefined entangled state. Each is given a measurement as input, which they perform on their share of the system. The outcomes of the measurements follow a distribution which is predicted by quantum mechanics. In an experimental setting, Bell inequalities are used to distinguish truly quantum from classical behavior.
We present a new lower bound technique based on the notion of detector inefficiency (where some runs are discarded by either of the players) for the extended setting of simulating distributions, and show that it coincides with the partition bound in the case of computing functions. The dual form is more feasible to use, and we show that it amounts to constructing an explicit Bell inequality. We also give a lower bound on quantum communication complexity which can be viewed as a quantum extension of the rectangle bound, effectively overcoming the necessity of a quantum minmax theorem.
For one-way communication, we show that the quantum one-way partition bound is tight for classical communication with shared entanglement up to arbitrarily small error.
Finally, an important goal in physics is to devise robust Bell experiments that are impervious to noise and detector inefficiency. We make further progress towards this by giving a general tradeoff between communication, Bell inequality violation, and detector efficiency.
