A numerical analysis of the NPA semidenite programming hierarchy for the Mod P game

Abstract

The Mod P game is a generalization of the famous CHSH game [6] to a field of order p. The CHSH game corresponds to the Mod P game for the value of p = 2. The CHSH game was one of the earliest and most important results in quantum mechanics because it predicted a clear and experimentally verifiable separation between classical and quantum physics in the form of a Bell's inequality violation. In this thesis, we study the maximum winning probability for the Mod P game over the set of quantum strategies. For p = 2, an early result by Tsirelson [15] showed that the maximum winning probability by a quantum strategy is 0:854. This result is also tight in that it is achievable. Here we are interested in studying the game for values of p > 2 which has seen little progress over the years. This research thesis serves two purposes. The first is to create a self contained reference for some of the most important results in the area. Among these results, a prominent work is the NPA hierarchy [13] of semidenite programs for testing whether a given bipartite correlation corresponds to a valid quantum mechanical experiment. The second part of this thesis is an implementation of this hierarchy for the Mod P game. In the first level of the hierarchy, we obtain numerical results that match analytic upper bounds by Bavarian and Shor [2]. We also nd that the Bavarian and Shor bound is tighter than the first level NPA hierarchy value for a prime power p. In a collaborative work with Matthew Coudron we also present an approach for a semidenite relaxation of the Mod P game using unitary operators. This approach brings us closer to achieving an exact analytic solution for the winning probability of the Mod P game.