Abstract
We introduce a nonlocal game that captures and extends the notion of graph isomorphism. This game can be won in the classical case if and only if the two input graphs are isomorphic. Thus, by considering quantum strategies we are able to define the notion of quantum isomorphism. We also consider the case of more general nonsignalling strategies, and show that such a strategy exists if and only if the graphs are fractionally isomorphic. We prove several necessary conditions for quantum isomorphism, including cospectrality, and provide a construction for producing pairs of nonisomorphic graphs that are quantum isomorphic.
We then show that both classical and quantum isomorphism can be reformulated as feasibility programs over the completely positive and completely positive semidefinite cones respectively. This leads us to considering relaxations of (quantum) isomorphism arrived at by relaxing the cone to either the doubly nonnegative (DNN) or positive semidefinite (PSD) cones. We show that DNNisomorphism is equivalent to the previous defined notion of graph equivalence, a polynomialtime decidable relation that is related to coherent algebras. We also show that PSDisomorphism implies several types of cospectrality, and that it is equivalent to cospectrality for connected 1walkregular graphs. Finally, we show that all of the above mentioned relations form a strict hierarchy of weaker and weaker relations, with nonsingalling/fractional isomorphism being the weakest. The techniques used are an interesting mix of algebra, combinatorics, and quantum information.
BibTeX  Entry
@InProceedings{mancinska_et_al:LIPIcs:2017:7469,
author = {Laura Mancinska and David E. Roberson and Robert Samal and Simone Severini and Antonios Varvitsiotis},
title = {{Relaxations of Graph Isomorphism}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {76:176:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7469},
URN = {urn:nbn:de:0030drops74697},
doi = {10.4230/LIPIcs.ICALP.2017.76},
annote = {Keywords: graph isomorphism, quantum information, semidefinite programming}
}
Keywords: 

graph isomorphism, quantum information, semidefinite programming 
Collection: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) 
Issue Date: 

2017 
Date of publication: 

07.07.2017 