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

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.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2017

Author dc:creator

• Abate, Shalom (Shalom A.)

Advisor dc:contributor.advisor

• Peter Shor.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/112827

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/112827