Large Bell violations from communication complexity lower bounds

ALEXANDRE NOLIN; GABRIEL SENNO; SOPHIE LAPLANTE; JÉRÉMIE ROLAND; MATHIEU LAURIÈRE

Paris

Jornada; QuPa (Meeting of the Paris Centre for Quantum Computing); 2016

The classical (resp. quantum) communication complexity of a bipartite function $f$ is the minimum number of bits (resp. qbits) that need to be communicated between players Alice, holding input $x$, and Bob, holding input $y$, in order for them to compute $f(x,y)$. One of the strongest techniques known to prove lower bounds on classical communication complexity is the so-called partition bound. We show how to derive large Bell violations from any problem whose quantum communication complexity is smaller than its partition bound value. This applies to many of the usually studied functions: Disjointness, Vector in Subspace, Tribes, etc. The violations we get are resistant to the detection loophole, can be exponential in the size of the inputs and we show that they can also be made resistant to uniform noise.