Codes and Expansions (CodEx) Seminar
Bill Martin (Worcester Polytechnic Institute):
Quantum isomorphic graphs from association schemes
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 \(x_A\) (\(x_B\)) in \(V(G)\dot{\cup} V(H)\). Alice and Bob respond with
vertices \(y_A,y_B\) 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 \(x_A,y_A,x_B,y_B\)) 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činska 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.