Mathematical Sciences Department
Discrete Math Seminar
Bill Martin - WPI
Monday, February 19th, 2024
11:00-11:50 AM
Fuller Labs 320
Quantum games have emerged as useful tools to understand the power of shared entanglement. A simple classical game can be used to define graph isomorphism: two players, Alice and Bob, convince a referee that graphs G and H are isomorphic as follows. Alice and Bob may strategize beforehand but cannot communicate during the game. The referee gives Alice (Bob) a vertex xA (xB ) in V (G) ̇∪V (H). Alice and Bob respond with vertices yA, yB of the opposite graph and win if the relationship (equal, adjacent, non-adjacent) between the two vertices of G matches the relationship between the two vertices (among xA, yA, xB , yB ) belonging to H. The question is how much the game changes if, as part of their strategizing, Alice and Bob prepare some quantum state on which they can later perform measurements. We say the graphs G and H are quantum isomorphic if there is a way for Alice and Bob to fool the referee with this additional resource. Ada Chan and I showed that any two Hadamard graphs on the same number of vertices are quantum isomorphic. This follows from a more general recipe for showing quantum isomorphism of graphs arising from certain association schemes. The main result is built from three tools. A remarkable recent result of Manˇcinska and Roberson shows that graphs G and H are quantum isomorphic if and only if, for any planar graph F , the number of graph homomorphisms from F to G is equal to the number of graph homomorphisms from F to H. A generalization of partition functions called ”scaffolds” affords some basic reduction rules such as series-parallel reduction and can be applied to counting homomorphisms. The final tool is the classical theorem of Epifanov showing that any plane graph can be reduced to a single vertex and no edges by extended series-parallel reductions and Delta-Wye transformations. This last sort of transformation is available to us in the case of exactly triply regular association schemes. The goal of the talk is to walk through these ideas without making things unnecessarily technical. No knowledge of physics is assumed and, for this narrative, we will avoid the the quantum commuting framework and work in a finite-dimensional quantum tensor framework