RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

Arkhipov's theorem, games, groups, and graphs

June 17, 2020 - 11:00am
William Slofstra
University of Waterloo

Given 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.

Join Zoom Meeting

Meeting ID: 917 8094 9183
Password: 822350
One tap mobile
+13017158592,,91780949183# US (Germantown)
+19294362866,,91780949183# US (New York)

Dial by your location
        +1 301 715 8592 US (Germantown)
        +1 929 436 2866 US (New York)
        +1 312 626 6799 US (Chicago)
        +1 346 248 7799 US (Houston)
        +1 669 900 6833 US (San Jose)
        +1 253 215 8782 US (Tacoma)
Meeting ID: 917 8094 9183
Find your local number: