Identifying Perfect Nonlocal Games

This thesis is about nonlocal games. These “games” are really interactive tests in which a verifier checks the correlations that can be produced by non-communicating players. We study the class of commuting operator correlations: correlations which can by produced by players who make commuting measurements on some shared entangled state. This thesis contains following results: • A general algebraic characterization of games with a “perfect” commuting operator strategy, i.e. games with a winning correlation that can be produced exactly by commuting operator measurements. This characterization is built on a key result in non-commutative algebraic geometry known as a (non-commutative) Nullstellensatz. • A sufficient condition for a class of nonlocal games called XOR games to have a perfect commuting operator strategy. This condition can be checked in polynomial time, and can be understood either as non-existence of a combinatorial object called a PREF (the noPREF condition) or as non existence of a solution to an instance of the subgroup membership problem in a specially constructed group. • A family of simple one-qubit-per-player strategies we call MERP strategies, which we show are optimal for any XOR game which has a perfect commuting operator strategy by the noPREF condition. • Proofs that the noPREF condition is both necessary and sufficient for symmetric XOR games and 3 player XOR games. • Explicit constructions of several families of XOR games with interesting properties. • An analysis of randomly generated XOR games using the noPREF condition and the first moment method.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Physics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Bene Watts, Adam

Advisor dc:contributor.advisor

• Harrow, Aram W.

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/142811

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/142811