William Slofstra: Arkhipov's theorem, games, groups, and graphs
0Given a nonlocal game, we'd like to be able to find the optimal quantum winning probability, and the set of optimal strategies. However, the recent MIP*=RE result implies that we cannot determine the quantum winning probability to within constant error. We also know that, even if we know the quantum winning probability, it's possible to come up with simple properties of the set of optimal strategies (for instance, whether the set contains a finite-dimensional strategy) which are also impossible to determine. Because of these results, it seems interesting to find classes of games for which we can answer questions about optimal winning probabilities and optimal strategies. One candidate for such a class is graph incidence games, also known as the linear system games for linear systems where every variable appears in exactly two constraints. This class seems more tractable than general nonlocal games, since a theorem of Alex Arkhipov states that a graph incidence game has a perfect quantum strategy and no perfect classical strategy if and only if the underlying graph is nonplanar. In this talk, I'll cover joint work with Connor Paddock, Vincent Russo, and Turner Silverthorne, in which we extend Arkhipov's theorem to show that many properties of optimal strategies for graph incidence games can also be characterized in terms of forbidden minors. In particular, we give forbidden minor characterizations for finiteness and abelianness of the solution group of an incidence system. The former is particularly interesting, since finiteness implies a form of robust self-testing by work of Coladangelo and Stark.