Classical and quantum partition bound and detector inefficiency

Details Classical and quantum partition bound and detector inefficiency Classical and quantum partition bound and detector inefficiency

2012-03-19

arxiv.org/abs/1203.4155v1

Physics

Quantum Physics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Classical and quantum partition bound and detector inefficiency does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Classical and quantum partition bound and detector inefficiency, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classical and quantum partition bound and detector inefficiency will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-212914