Quantum and non-signalling graph isomorphisms

We introduce a two-player nonlocal game, called the $(G,H)$-isomorphism game, where classical players can win with certainty if and only if the graphs $G$ and $H$ are isomorphic. We then define the notions of quantum and non-signalling isomorphism, by considering perfect quantum and non-signalling strategies for the $(G,H)$-isomorphism game, respectively. First, we prove that non-signalling isomorphism coincides with the well-studied notion of fractional isomorphism, thus giving the latter an operational interpretation. Second, we show that quantum isomorphism is equivalent to the feasibility of two polynomial systems in non-commuting variables, obtained by relaxing the standard integer programming formulations for graph isomorphism to Hermitian variables. On the basis of this correspondence, we show that quantum isomorphic graphs are necessarily cospectral. Finally, we provide a construction for producing quantum isomorphic graphs that are nevertheless not isomorphic. Our construction makes use of linear binary constraint system games and is related to the FGLSS reduction of inapproximability literature.