Loading...
Loading...

Go to the content (press return)

Quantum and non-signalling graph isomorphisms

Author
Atserias, A.; Mancinska, L.; Roberson, D.; Samal, R.; Severini, S.; Varvitsiotis, A.
Type of activity
Journal article
Journal
Journal of combinatorial theory. Series B
Date of publication
2019-05
Volume
136
First page
289
Last page
328
DOI
https://doi.org/10.1016/j.jctb.2018.11.002 Open in new window
Project funding
A unified theory of algorithmic relaxations
Theory and applications in satisfiability and constraint optimization
Repository
http://hdl.handle.net/2117/127696 Open in new window
https://arxiv.org/abs/1611.09837 Open in new window
URL
https://www.sciencedirect.com/science/article/pii/S0095895618301059 Open in new window
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 polynomia...
Citation
Atserias, A. [et al.]. Quantum and non-signalling graph isomorphisms. "Journal of combinatorial theory. Series B", 4 Desembre 2018, p. 1-40.
Keywords
Entanglement, Fractional isomorphism, Graph isomorphism, Non-local games, Non-signalling, Quantum strategies
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

  • Atserias, Albert  (author)
  • Mancinska, Laura  (author)
  • Roberson, David E.  (author)
  • Samal, Robert  (author)
  • Severini, Simone  (author)
  • Varvitsiotis, Antonios  (author)