Quantum and non-signalling graph isomorphisms

TY - JOUR

T1 - Quantum and non-signalling graph isomorphisms

AU - Atserias, Albert

AU - Mančinska, Laura

AU - Roberson, David E.

AU - Šámal, Robert

AU - Severini, Simone

AU - Varvitsiotis, Antonios

PY - 2019

Y1 - 2019

N2 - We introduce the (G,H)-isomorphism game, a new two-player non-local game that classical players can win with certainty iff the graphs G and H are isomorphic. We then define quantum and non-signalling isomorphisms by considering perfect quantum and non-signalling strategies for this game. We prove that non-signalling isomorphism coincides with fractional isomorphism, giving the latter an operational interpretation. We show that quantum isomorphism is equivalent to the feasibility of two polynomial systems obtained by relaxing standard integer programs for graph isomorphism to Hermitian variables. Finally, we provide a reduction from linear binary constraint system games to isomorphism games. This reduction provides examples of quantum isomorphic graphs that are not isomorphic, implies that the tensor product and commuting operator frameworks result in different notions of quantum isomorphism, and proves that both relations are undecidable.

AB - We introduce the (G,H)-isomorphism game, a new two-player non-local game that classical players can win with certainty iff the graphs G and H are isomorphic. We then define quantum and non-signalling isomorphisms by considering perfect quantum and non-signalling strategies for this game. We prove that non-signalling isomorphism coincides with fractional isomorphism, giving the latter an operational interpretation. We show that quantum isomorphism is equivalent to the feasibility of two polynomial systems obtained by relaxing standard integer programs for graph isomorphism to Hermitian variables. Finally, we provide a reduction from linear binary constraint system games to isomorphism games. This reduction provides examples of quantum isomorphic graphs that are not isomorphic, implies that the tensor product and commuting operator frameworks result in different notions of quantum isomorphism, and proves that both relations are undecidable.

KW - Entanglement

KW - Fractional isomorphism

KW - Graph isomorphism

KW - Non-local games

KW - Non-signalling

KW - Quantum strategies

UR - http://www.scopus.com/inward/record.url?scp=85057881619&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2018.11.002

DO - 10.1016/j.jctb.2018.11.002

M3 - Journal article

AN - SCOPUS:85057881619

SN - 0095-8956

VL - 136

SP - 289

EP - 328

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -