University of Cambridge > Talks.cam > CQIF Seminar > Relaxations of Graph Isomorphism

Relaxations of Graph Isomorphism

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Steve Brierley.

We introduce a two player non-local game based on graph isomorphisms. In the (X,Y)-isomorphism game the players aim to convince a referee that there exists an isomorphism between graphs X and Y. Classically, players can win this game with probability one if and only if the graphs are isomorphic. This allows us to define a quantum analog of isomorphism in the same manner as quantum coloring/homomorphism was defined. This notion of “quantum isomorphism” can 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 equivalence is based on Choi matrices and CPTP unital maps. Another relaxation can be obtained by considering general non-signalling strategies for the isomorphism game. This relaxation turns out to be equivalent to a linear relaxation of graph isomorphism known as fractional isomorphism. Lastly, we give a construction of pairs graphs based on linear binary constraint systems and the FGLSS -reduction that are quantum isomorphic but not isomorphic.

Joint work with Albert Atserias, Laura Mancinska, Robert Samal, Simone Severini, and Antonios Varvitsiotis.

This talk is part of the CQIF Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2017 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity