Quantum and non-signalling graph isomorphisms. (English) Zbl 1414.05197
Summary: 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.
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 91A43 | Games involving graphs |
Keywords:
graph isomorphism; quantum strategies; non-local games; entanglement; non-signalling; fractional isomorphismReferences:
| [1] | Arkhipov, Alex, Extending and characterizing quantum magic games (2012) |
| [2] | Atserias, Albert; Bulatov, Andrei; Dawar, Anuj, Affine systems of equations and counting infinitary logic, Theoret. Comput. Sci., 410, 18, 1666-1683 (2009) · Zbl 1168.68040 |
| [3] | Atserias, Albert; Maneva, Elitza N., Sherali-Adams relaxations and indistinguishability in counting logics, SIAM J. Comput., 42, 1, 112-137 (2013) · Zbl 1286.68175 |
| [4] | Babai, László, Automorphism groups, isomorphism, reconstruction, (Handbook of Combinatorics, vol. 2 (1995)), 1447-1540 · Zbl 0846.05042 |
| [5] | Babai, László, Graph isomorphism in quasipolynomial time, (Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (2016)), 684-697 · Zbl 1376.68058 |
| [6] | Babai, László; Erdős, Paul; Selkow, Stanley M., Random graph isomorphism, SIAM J. Comput., 9, 3, 628-635 (1980) · Zbl 0454.05038 |
| [7] | Berkholz, Christoph; Linear, Martin Grohe, Diophantine equations, group CSPs, and graph isomorphism, (Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (2017)), 327-339 · Zbl 1410.68153 |
| [8] | Cai, Jin-Yi; Fürer, Martin; Immerman, Neil, An optimal lower bound on the number of variables for graph identification, Combinatorica, 12, 4, 389-410 (1992) · Zbl 0785.68043 |
| [9] | Cameron, Peter J.; Montanaro, Ashley; Newman, Michael W.; Severini, Simone; Winter, Andreas, On the quantum chromatic number of a graph, Electron. J. Combin., 14, 1 (2007) · Zbl 1182.05054 |
| [10] | Cleve, Richard; Liu, Li; Slofstra, William, Perfect commuting-operator strategies for linear system games, J. Math. Phys., 58, 1 (2017) · Zbl 1355.81048 |
| [11] | Cleve, Richard; Mittal, Rajat, Characterization of binary constraint system games, (Proceedings of the 41st International Colloquium on Automata, Languages, and Programming. Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, ICALP ’14 (2014)), 320-331 · Zbl 1364.91015 |
| [12] | Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario, Interactive proofs and the hardness of approximating cliques, J. ACM, 43, 2, 268-292 (March 1996) · Zbl 0882.68129 |
| [13] | Grohe, Martin, Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, vol. 47 (2017), Cambridge University Press · Zbl 1530.68007 |
| [14] | Grohe, Martin; Otto, Martin, Pebble games and linear equations, J. Symbolic Logic, 80, 03 (2012) · Zbl 1252.03084 |
| [15] | Laura Mančinska, David E. Roberson, Antonios Varvitsiotis, Semidefinite relaxations of quantum isomorphism, available online, 2016.; Laura Mančinska, David E. Roberson, Antonios Varvitsiotis, Semidefinite relaxations of quantum isomorphism, available online, 2016. |
| [16] | Mančinska, Laura; Roberson, David E., Quantum homomorphisms, J. Combin. Theory Ser. B, 118, 228-267 (2016) · Zbl 1332.05098 |
| [17] | Mancinska, Laura; Roberson, David E.; Samal, Robert; Severini, Simone; Varvitsiotis, Antonios, Relaxations of graph isomorphism, (44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), LIPIcs. Leibniz Int. Proc. Inform., vol. 80 (2017)), Article 76 pp., 14 pp · Zbl 1441.68190 |
| [18] | Mančinska, Laura; Roberson, David E.; Varvisotis, Antonios, On deciding the existence of perfect entangled strategies for nonlocal games, Chic. J. Theoret. Comput. Sci., 2016, 5 (2016) · Zbl 1341.91021 |
| [19] | McKay, Brendan D.; Piperno, Adolfo, Practical graph isomorphism, II, J. Symbolic Comput., 60, 94-112 (2014) · Zbl 1394.05079 |
| [20] | Mermin, Nathaniel D., Simple unified form for the major no-hidden-variables theorems, Phys. Rev. Lett., 65, 3373-3376 (1990) · Zbl 0971.81501 |
| [21] | Musto, Benjamin; Vicary, Jamie, Quantum latin squares and unitary error bases, Quantum Inf. Comput., 16, 15-16, 1318-1332 (November 2016) |
| [22] | Nielsen, Michael A.; Chuang, Isaac L., Quantum Computation and Quantum Information (2010), Cambridge University Press · Zbl 1288.81001 |
| [23] | O’Donnell, Ryan; Wright, John; Wu, Chenggang; Zhou, Yuan, Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs, 1659-1677 (2014) · Zbl 1422.68089 |
| [24] | Ortiz, Carlos M.; Paulsen, Vern I., Quantum graph homomorphisms via operator systems, Linear Algebra Appl., 497, 23-43 (2016) · Zbl 1353.46041 |
| [25] | Paulsen, Vern I.; Severini, Simone; Stahlke, Dan; Todorov, Ivan G.; Winter, Andreas, Estimating quantum chromatic numbers, J. Funct. Anal., 270, 6, 2188-2222 (2016) · Zbl 1353.46043 |
| [26] | Paulsen, Vern I.; Todorov, Ivan G., Quantum chromatic numbers via operator systems, Q. J. Math., 66, 2, 677-692 (2015) · Zbl 1314.05078 |
| [27] | Popescu, Sandu; Rohrlich, Daniel, Quantum nonlocality as an axiom, Found. Phys., 24, 3, 379-385 (1994) |
| [28] | Ramana, Motakuri V.; Scheinerman, Edward R.; Ullman, Daniel, Fractional isomorphism of graphs, Discrete Math., 132, 1, 247-265 (1994) · Zbl 0808.05077 |
| [29] | Roberson, David E., Variations on a Theme: Graph Homomorphisms (2013), University of Waterloo, PhD thesis |
| [30] | Scholz, Volkher B.; Werner, Reinhard F., Tsirelson’s problem (2008) |
| [31] | Slofstra, William, Tsirelson’s problem and an embedding theorem for groups arising from non-local games (2016) · Zbl 1385.17009 |
| [32] | Slofstra, William, The set of quantum correlations is not closed (2017) · Zbl 1405.81021 |
| [33] | Tinhofer, Gottfried, Graph isomorphism and theorems of Birkhoff type, Computing, 36, 4, 285-300 (1986) · Zbl 0581.05038 |
| [34] | Tsirelson, Boris, Bell inequalities and operator algebras, (Open Problems in Quantum Information Theory. Open Problems in Quantum Information Theory, Problem, vol. 33 (July 2006), Institut für Mathematische Physik, TU: Institut für Mathematische Physik, TU Braunschweig, Germany), 6 · Zbl 1112.60065 |
| [35] | van Dam, Edwin R.; Haemers, Willem H., Which graphs are determined by their spectrum?, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
