Abstract: The study of equivalence relations on mathematical structures is a vast theory embracing combinatorics, optimization, algebra, and mathematical logic. In this context, graph isomorphism and its hierarchy of relaxations constitute a central topic, not only for its elusive complexity, but also for its mathematical richness. We develop a framework which succeeds in capturing salient aspects of the relaxations of graph isomorphism with tools furnished by nonlocal games. This framework allows us to introduce quantum and non-signalling isomorphism. We show that non-signalling isomorphism is equivalent to fractional isomorphism as well as exhibit pairs of non-isomorphic graphs which are nevertheless quantum isomorphic.
Our notion of quantum isomorphism can also be expressed in terms of a feasibility program over the recently introduced completely positive semidefinite cone. We can thus give relaxations of quantum isomorphism by considering the same program, but over the positive semidefinite or doubly nonnegative cones. The doubly nonnegative relaxation turns out to be equivalent to a previously defined notion based on coherent algebras associated to graphs. Interestingly, the main idea behind the proof of this purely classical result is based on Choi matrices and CPTP unital maps.
Joint work with Albert Atserias, Robert Samal, David Roberson, Simone Severini, and Antonios Varvitsiotis.