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

Atserias, A, Mančinska, L, Roberson, DE, Šámal, R, Severini, S & Varvitsiotis, A 2019, 'Quantum and non-signalling graph isomorphisms', Journal of Combinatorial Theory. Series B, bind 136, s. 289-328. https://doi.org/10.1016/j.jctb.2018.11.002

APA

Atserias, A., Mančinska, L., Roberson, D. E., Šámal, R., Severini, S., & Varvitsiotis, A. (2019). Quantum and non-signalling graph isomorphisms. Journal of Combinatorial Theory. Series B, 136, 289-328. https://doi.org/10.1016/j.jctb.2018.11.002

Vancouver

Atserias A, Mančinska L, Roberson DE, Šámal R, Severini S, Varvitsiotis A. Quantum and non-signalling graph isomorphisms. Journal of Combinatorial Theory. Series B. 2019;136:289-328. https://doi.org/10.1016/j.jctb.2018.11.002

Author

Atserias, Albert ; Mančinska, Laura ; Roberson, David E. ; Šámal, Robert ; Severini, Simone ; Varvitsiotis, Antonios. / Quantum and non-signalling graph isomorphisms. I: Journal of Combinatorial Theory. Series B. 2019 ; Bind 136. s. 289-328.

Bibtex

@article{422f1d834e174f56966f3f258ac83f9b,
title = "Quantum and non-signalling graph isomorphisms",
abstract = "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.",
keywords = "Entanglement, Fractional isomorphism, Graph isomorphism, Non-local games, Non-signalling, Quantum strategies",
author = "Albert Atserias and Laura Man{\v c}inska and Roberson, {David E.} and Robert {\v S}{\'a}mal and Simone Severini and Antonios Varvitsiotis",
year = "2019",
doi = "10.1016/j.jctb.2018.11.002",
language = "English",
volume = "136",
pages = "289--328",
journal = "Journal of Combinatorial Theory. Series B",
issn = "0095-8956",
publisher = "Academic Press",

}

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