COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

## Relaxations of Graph IsomorphismAdd 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
- MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
Note that ex-directory lists are not shown. |
## Other listsThe Eddington Lectures Physics of Medicine Journal Club Humanitarian Centre## Other talks'Cryptocurrency and BLOCKCHAIN – PAST, PRESENT AND FUTURE' Diversity of the human response to malaria Using the git revision control system Protecting Analog Sensor Security Lifestyle Dynamics Index: Worldwide Results and household economic implications LARMOR LECTURE - Exoplanets, on the hunt of Universal life |