Communication cost Vs Bell inequality violation

Abstract

In 1964, John Bell proved that independent measurements on entangled quantum states lead to correlations that cannot be reproduced using local hidden variables. The core of his proof is that such distributions violate some logical constraints known as Bell inequalities. This remarkable result establishes the non-locality of quantum physics. Bell's approach is purely qualitative. This naturally leads to the question of quantifying quantum physics' non-locality. We will specifically consider two quantities introduced for this purpose. The first one is the maximum amount of Bell inequality violation, and the second one is the communication cost of simulating quantum distributions. In this talk, we prove that these two quantities are strongly related: the logarithm of the first is upper bounded by the second. We prove this theorem in the more general context of non-signalling distributions. This generalization gives us two clear benefits. First, the rich structure of the underlying affine space provides us with a very strong intuition. Secondly, non-signalling distributions capture traditional communication complexity of boolean functions. In that case, our theorem is equivalent to the factorization norm lower bound of Linial and Shraibman, for which we give an elementary proof.