Quantum Strategies for Graph Based Nonlocal Games

A nonlocal game involves a verifier and two cooperative players, Alice and Bob. The verifier sends each of the players a question/input and they each respond with their own answer/output. Whether or not the players “win” the game depends on both of their questions and answers. These games are nontrivial because Alice and Bob do not know each other’s questions.

Quantum strategies making use of a shared entangled state between Alice and Bob can outperform classical strategies because entanglement allows them to “correlate” their answers. Several of the well-known examples of nonlocal games with a quantum advantage have graph theoretic formulations. This interplay between graph theory and quantum information is rather unexpected, and it has led to several important and surprising results like the equivalence of “quantum isomorphism” and equality of homomorphisms counts from all planar graphs.

Nonlocal games have found applications in self-testing of quantum systems and device-independent quantum cryptography. Over the past few years, several connections between nonlocal games and other fields of mathematics such as Graph Theory, Operator Algebras, Operator Space Theory, Compact Quantum Groups, and Categorical Quantum Mechanics have been unearthed.

We will look to exploit and explore the interplay between these branches of mathematics and nonlocal games and hope to further enrich our understanding of nonlocal games and quantum correlations. We will also be looking into strategies for nonlocal games with quantum inputs and outputs and potential applications to self-testing of quantum systems.