Mohammad Bavarian: Beyond XOR Games: Information causality, Szemerédi-Trotter and Algebraic Variants of CHSH

CHSH_q is the following simple two-player game: two parties are given x,y in F_q uniformly at random, and each must produce an output a,b in F_q$ without communicating to the other. The players objective is to maximize the probability that their outputs satisfy a+b=xy in F_q. This game was introduced by Buhrman and Massar (Phys. Rev. A 72.5 (2005)) as a larger alphabet generalization of the CHSH game, which is one of the most well-studied games in quantum information theory, and which has large number of applications to quantum cryptography and quantum complexity. In this work, we obtain the first asymptotic results on the quantum and classical values of $\sf CHSH_q$. An important fact here is that for analyzing CHSH_q (and in general for any game with q>2) we cannot rely on the powerful result of Tsirelson(Journal of Soviet Mathematics, 36 (1987)) on SDP characterization of the quantum value of games, which only holds for XOR games (a subclass of q=2 games). As a result of this barrier, there are few examples and techniques available for analyzing quantum games with q>2. One primary contribution of this work is to expand on the set of tools and examples in a setting beyond the relatively well-understood case of XOR games.

The main result regarding the quantum value of CHSH_q is an upper bound of O(q^{-1/2}). Regarding the classical value of the game, we prove an upper bound O(q^{1/2-eps}) in the case of q=p^{2k-1}, and a tight lower bound of Omega(q^{-1/2}) for q=p^{2k}. A key observation that allows us to obtain the above bounds is a geometric view of CHSH_q} which reveals an intimate connection between this game and the celebrated finite field Szemeredi-Trotter theorem of Bourgain-Katz-Tao (GAFA 14.1 (2004)). This connection creates one of the first links between the study of multiplayer refereed games and arithmetic combinatorics, and may have applications to other areas. Beside the above, our work contains various other technical results of independent interest. For example, as an intermediate step in our quantum upper bound we prove a new variant of the principle of information causality, resolving an open problem of Pawlowski and Winter (Phys. Rev. A 85.2 (2012)).