Mathematical Sciences Department QIT Thinking Seminar
Speaker: Bill Martin, WPI
Tuesday February 25th, 2025
1:00pm -1:50pm
Stratton Hall 313
Title: Quantum games and graphs
Abstract: This is part two of my series on quantum games. I will try to understand two connections between quantum games and graph theory. We will pick up where we left off last week and study Arkhipov’s result that a binary constraint system where each variable appears in two equations is ``magic’’ (i.e., admits a winning quantum strategy but no winning classical strategy) if and only if the corresponding graph is planar. (Here, the graph corresponding to Ax=b is the one with incidence matrix A.) Next we will study the graph homomorphism game, with quantum chromatic number and quantum clique number as special cases, and outline the connection between binary constraint system games and quantum isomorphism of graphs. This will prepare us for our discussion of quantum isomorphism on March 4.