Relaxations of graph isomorphism

• Main Authors: Mančinska, Laura, Šámal, Robert, Severini, Simone, Varvitsiotis, Antonios, Roberson, David E.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2018
• Subjects: DRNTU::Science::Mathematics; Graph Isomorphism; Quantum Information
• Online Access: https://hdl.handle.net/10356/88428; http://hdl.handle.net/10220/45783
• Institution: Nanyang Technological University

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...