Welcome to Pure Mathematics

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

Aleksa Vujicic, University of Waterloo

The Spine of a Fourier Algebra

Given a locally compact group G, one can define the Fourier and Fourier-Stieltjes algebras A(G) and B(G), which in the abelian case, are isomorphic to L1(G^) and M(G^) respectively. The Fourier algebra A(G) is typically more tractable than B(G), and often easier to describe. A notable exception is when B(G) = A(G), which occurs precisely when G is compact.
The spine of a Fourier Algebra A*(G), introduced by M. Ilie and N. Spronk, is a subalgebra of B(G) which contains all A(H)∘η  where η : G → H is a continuous homomorphism.
It has been shown that for G = Qp ⋊ Op*, that B(G) = A*(G), despite not being compact.
We also explore G = Qp^2 ⋊ Op*, where we have shown that although B(G) is strictly larger than A*(G), they are close to being similar.

MC 5417

Kieran Mastel, University of Waterloo

The weighted algebra approach to constraint system games

Entanglement allows for correlations between spatially separated experiments that are not possible classically. One way to study the computational power of entanglement is via nonlocal games. I will discuss my recent works with Eric Culf and William Slofstra on constraint system games. Different types of perfect entangled strategies for these games can be understood as representations of the algebra of the underlying constraint system. The weighted algebra formalism, introduced by Slofstra and me, extends this to non-perfect strategies. Using this formalism we can show that classical reductions between constraint systems are sound against quantum provers, which allows us to prove the RE-completeness of some constraint system games and to show that MIP* admits two prover perfect zero knowledge proofs.

MC 5417