Relaxations of graph isomorphism Leibniz International Proceedings in Informatics

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10369136" target="_blank" >RIV/00216208:11320/17:10369136 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.76" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.76</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.76" target="_blank" >10.4230/LIPIcs.ICALP.2017.76</a>

Result language

angličtina

Original language name

Relaxations of graph isomorphism Leibniz International Proceedings in Informatics

Original language description

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 non-signalling 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 non-isomorphic 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 DNN-isomorphism is equivalent to the previous defined notion of graph equivalence, a polynomialtime decidable relation that is related to coherent algebras. We also show that PSD-isomorphism implies several types of cospectrality, and that it is equivalent to cospectrality for connected 1-walk-regular graphs. Finally, we show that all of the above mentioned relations form a strict hierarchy of weaker and weaker relations, with non-singalling/fractional isomorphism being the weakest. The techniques used are an interesting mix of algebra, combinatorics, and quantum information.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2017

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

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

ISBN

978-3-95977-041-5

ISSN

1868-8969

e-ISSN

neuvedeno

Number of pages

14

Pages from-to

1-14

Publisher name

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Place of publication

Dagstuhl, Germany

Event location

Warsaw

Event date

Jul 10, 2017

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—