Isaac Newton Institute for Mathematical Sciences

Information Causality, Non-local Computation and CHSH over Finite Fields

Presenter: Mohammad Bavarian (MIT)

Abstract

In this work, we provide two different techniques for proving upper bounds on higher alphabet generalizations of CHSH game over finite fields. In this game, denoted by $CHSH_q$, the two parties receive $x,y\in \F_q$ uniformly at random and each must produce an output without communicating to the other . They succeed if their outputs sum to $xy$ in $\F_q$. For this game we prove an upper bound of $1/q+ (q-1)/q\sqrt{q}$ which generalizes the classical result of Tsirelson, who proved the same bound of $1/2+1/2\sqrt{2}$ for the original $\F_2$ CHSH game. We give two different proof of this result: in the first approach, we prove our upper bound by a reduction to a variant of result of Linden et al (Physical Review Letters 99, 180502 (2007)). In the second approach, we use an information theoretic argument inspired by the principle of information causality by Pawlowski et al (Nature 461, 1101 (2009)). A novel point in our second approach is that along the way we develop an extension to the principle of information causality in pairwise independent setting which holds in great generality.