Relaxations of Graph Isomorphism

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

• David Roberson, UCL
• Thursday 13 October 2016, 14:15-15:15
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

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.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.