[QIP-Sem] QIP seminar, Tue 2/17, 4:15, 36-428, Roland,Jeremie

[Peter Shor]

MIT Quantum Information Processing seminar
Tuesday 2/17 at 4:15 in 36-428
-------------------------------------------------

 Roland,Jeremie (NEC Laboratories America)

The communication complexity of non-signaling distributions

Abstract:

We study a model of communication complexity that encompasses many well-studied problems, including classical and quantum communication complexity, the complexity of simulating distributions arising from bipartite measurements of shared quantum states, and XOR games. In this model, Alice gets an input x, Bob gets an input y, and their goal is to each produce an output a,b distributed according to some pre-specified joint distribution p(a,b|x,y). Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa, therefore our techniques apply to any communication problem that can be reduced to a non-signaling distribution, including quantum distributions, Boolean and non-Boolean functions, most relations, partial (promise) problems, in the two-player and multipartite settings. We give elementary proofs and very intuitive interpretations of the recent lower bounds of Linial and Shraibman, which
  we generalize to the problem of simulating any non-signaling distribution. The lower bounds we obtain are also expressed as linear programs (or SDPs for quantum communication). We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games. We show that as in the case of Boolean functions, the gap between the quantum and classical lower bounds is at most linear in size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequalities, which was previously known only for the case of Boolean outcomes with uniform marginals. Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One consequence of this 
 is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication. Joint work with:Julien Degorre, Marc Kaplan and Sophie Laplante 

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem