Abstract
Non-local games include a verifier and two players, Alice and Bob, that devise a cooperative strategy. The verifier asks questions to both. The players give answers. They allowed to agree on a strategy beforehand, but can not communicate after they receive their questions. We consider a non-local game, called the (G,H)-isomorphism game, where the players win with certainty if and only two given graphs G and H are isomorphic. Depending on the correlations available to Alice and Bob, we define the notions of quantum and non-signalling isomorphism. First, we prove that non-signalling isomorphism coincides with fractional isomorphism. Second, we prove that quantum isomorphism is equivalent to the feasibility of two polynomial systems in non-commuting variables. Finally, by considering certain constraint satisfaction problems, we observe that there exist graphs that are quantum isomorphic but not isomorphic. The perspective discussed in the talk is a continuation of the study of quantum homomorphisms, as introducted by Laura Mancinska and David Roberson. This is work done together with Albert Atserias, Laura, David, Robert Samal, and Antonios Varvitsiotis.