Quantum and non-signalling graph isomorphisms
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Quantum and non-signalling graph isomorphisms. / Atserias, Albert; Mančinska, Laura; Roberson, David E.; Šámal, Robert; Severini, Simone; Varvitsiotis, Antonios.
I: Journal of Combinatorial Theory. Series B, Bind 136, 2019, s. 289-328.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
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
VL - 136
SP - 289
EP - 328
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
SN - 0095-8956
ER -
ID: 215082838