Adina Goldberg, University of Waterloo
Synchronous and quantum games: Graphical and algebraic methods
This is a mathematics thesis that contributes to an understanding of nonlocal games as formal objects. With that said, it does have connections to quantum information theory and physical operational interpretations.
Nonlocal games are interactive protocols modelling two players attempting to win a game, by answering a pair of questions posed by the referee, who then checks whether their answers are correct. The players may have access to a shared quantum resource state and may use a pre-arranged strategy. Upon receiving their questions, they can measure this state, subject to some separation constraints, in order to select their answers. A famous example is the CHSH game of [Cla+69], where making use of shared quantum entanglement gives the players an advantage over using classical strategies.
This thesis contributes to two separate questions arising in the study of synchronous nonlocal games: their algebraic properties, and their generalization to the quantum question-and-answer setting. Synchronous games are those in which players must respond with the same answer, given the same question.
First, we study a synchronous version of the linear constraint game, where the players must attempt to convince the referee that they share a solution to a system of linear equations over a finite field. We give a correspondence between two different algebraic objects modelling perfect strategies for this game, showing one is isomorphic to a quotient of the other. These objects are the game algebra of [OP16] and the solution group of [CLS17]. We also demonstrate an equivalence of these linear system games to graph isomorphism games on graphs parameterized by the linear system.
Second, we extend nonlocal games to quantum games, in the sense that we allow the questions and answers to be quantum states of a bipartite system. We do this by quantizing the rule function, games, strategies, and correlations using a graphical calculus for symmetric monoidal categories applied to the category of finite dimensional Hilbert spaces. This approach follows the overall program of categorical quantum mechanics. To this generalized setting of quantum games, we extend definitions and results around synchronicity. We also introduce quantum versions of the classical graph homomorphism [MR16] and isomorphism [Ats+16] games, where the question and answer spaces are the vertex algebras of quantum graphs, and we show that quantum strategies realizing perfect correlations for these games correspond to morphisms between the underlying quantum graphs.
MC 2009 or Zoom: https://uwaterloo.zoom.us/j/92051331429?pwd=fl6rjZHC4X7itlJpaJaxwpfzJINQvG.1