  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. In the quantum case,
we consider both the tensor product and commuting frameworks for nonlocal
games. 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, in the tensor product framework, 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 reducing linear binary
constraint system games to isomorphism games. This allows us to produce quantum
isomorphic graphs that are nevertheless not isomorphic. Furthermore, it allows
us to show that our two notions of quantum isomorphism, from the tensor product
and commuting frameworks, are in fact distinct relations, and that the latter
is undecidable. Our construction is related to the FGLSS reduction from
inapproximability literature, as well as the CFI construction.
