Relaxations of Graph Isomorphism

We introduce a two player non-local game based on graph isomorphisms. The input for the game is two graphs X and Y, and players attempt to convince a referee that there exists an isomorphism between X and Y. Classically, players can win this game with probability one if and only if a corresponding isomorphism does in fact exist. It is then natural to ask what happens when the players are allowed to make quantum measurements on a shared entangled state, i.e. are permitted to use “quantum strategies”. This allows us to define a quantum analog of isomorphism in the same manner as quantum coloring/homomorphism was defined. We will discuss recent results on this notion of “quantum isomorphism”, as well as two relaxations based on feasibility problems over the positive semidefinite and doubly nonnegative cones. This work is ongoing and the results fairly new, so there has yet to be found a separation between isomorphism and quantum isomorphism. However, the doubly nonnegative relaxation has been shown to be closely related to a previously defined notion based on coherent algebras associated to graphs.

 

Joint work with Laura Mancinska and Antonios Varvitsiotis