ALGEBRAIC COMBINATORICS

no. 4
Arkhipov’s theorem, graph minors, and linear system nonlocal games
Paddock, Connor1; Russo, Vincent2; Silverthorne, Turner3; Slofstra, William4
1 Institute for Quantum Computing University of Waterloo, and Department of Combinatorics & Optimization University of Waterloo
2 Modellicity Inc., and Unitary Fund
3 Department of Mathematics University of Toronto
4 Institute for Quantum Computing University of Waterloo, and Department of Pure Mathematics University of Waterloo
Algebraic Combinatorics, Volume 6 (2023) no. 4, pp. 1119-1162.

The perfect quantum strategies of a linear system game correspond to certain representations of its solution group. We study the solution groups of graph incidence games, which are linear system games in which the underlying linear system is the incidence system of a (non-properly) two-coloured graph. While it is undecidable to determine whether a general linear system game has a perfect quantum strategy, for graph incidence games this problem is solved by Arkhipov’s theorem, which states that the graph incidence game of a connected graph has a perfect quantum strategy if and only if it either has a perfect classical strategy, or the graph is nonplanar. Arkhipov’s criterion can be rephrased as a forbidden minor condition on connected two-coloured graphs. We extend Arkhipov’s theorem by showing that, for graph incidence games of connected two-coloured graphs, every quotient closed property of the solution group has a forbidden minor characterization. We rederive Arkhipov’s theorem from the group theoretic point of view, and then find the forbidden minors for two new properties: finiteness and abelianness. Our methods are entirely combinatorial, and finding the forbidden minors for other quotient closed properties seems to be an interesting combinatorial problem.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.292
Classification: 05E15, 05C83, 81P13, 81P40
Keywords: nonlocal games, graph minors, quantum information
Paddock, Connor 1; Russo, Vincent 2; Silverthorne, Turner 3; Slofstra, William 4

1 Institute for Quantum Computing University of Waterloo, and Department of Combinatorics & Optimization University of Waterloo
2 Modellicity Inc., and Unitary Fund
3 Department of Mathematics University of Toronto
4 Institute for Quantum Computing University of Waterloo, and Department of Pure Mathematics University of Waterloo
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2023__6_4_1119_0,
     author = {Paddock, Connor and Russo, Vincent and Silverthorne, Turner and Slofstra, William},
     title = {Arkhipov{\textquoteright}s theorem, graph minors, and linear system nonlocal games},
     journal = {Algebraic Combinatorics},
     pages = {1119--1162},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {4},
     year = {2023},
     doi = {10.5802/alco.292},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.292/}
}
TY  - JOUR
AU  - Paddock, Connor
AU  - Russo, Vincent
AU  - Silverthorne, Turner
AU  - Slofstra, William
TI  - Arkhipov’s theorem, graph minors, and linear system nonlocal games
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 1119
EP  - 1162
VL  - 6
IS  - 4
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.292/
DO  - 10.5802/alco.292
LA  - en
ID  - ALCO_2023__6_4_1119_0
ER  - 
%0 Journal Article
%A Paddock, Connor
%A Russo, Vincent
%A Silverthorne, Turner
%A Slofstra, William
%T Arkhipov’s theorem, graph minors, and linear system nonlocal games
%J Algebraic Combinatorics
%D 2023
%P 1119-1162
%V 6
%N 4
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.292/
%R 10.5802/alco.292
%G en
%F ALCO_2023__6_4_1119_0
Paddock, Connor; Russo, Vincent; Silverthorne, Turner; Slofstra, William. Arkhipov’s theorem, graph minors, and linear system nonlocal games. Algebraic Combinatorics, Volume 6 (2023) no. 4, pp. 1119-1162. doi : 10.5802/alco.292. https://alco.centre-mersenne.org/articles/10.5802/alco.292/

[1] Adamson, Sean A.; Wallden, Petros Quantum magic rectangles: Characterization and application to certified randomness expansion, Phys. Rev. Research, Volume 2 (2020), Paper no. 043317

[2] Adamson, Sean A.; Wallden, Petros Practical parallel self-testing of Bell states via magic rectangles, Physical Review A, Volume 105 (2022), Paper no. 032456 | MR

[3] Archdeacon, Dan; Richter, Bruce On the parity of planar covers, J. Graph Theory, Volume 14 (1990) no. 2, pp. 199-204 | DOI | MR | Zbl

[4] Arkhipov, Alex Extending and Characterizing Quantum Magic Games (2012) | arXiv

[5] Baader, Franz; Nipkow, Tobias Term Rewriting and All That, Cambridge University Press, 1998 | DOI

[6] Bernardi, Olivier; Noy, Marc; Welsh, Dominic Growth constants of minor-closed classes of graphs, J. Combin. Theory Ser. B, Volume 100 (2010) no. 5, pp. 468-484 | DOI | MR | Zbl

[7] Bodlaender, Hans L. On disjoint cycles, Internat. J. Found. Comput. Sci., Volume 5 (1994) no. 01, pp. 59-68 | DOI | Zbl

[8] Bollobás, Béla Extremal graph theory, Courier Corporation, 2004

[9] Brady, Noel; Riley, Tim; Short, Hamish The Geometry of the Word Problem for Finitely Generated Groups, Springer Science & Business Media, 2007

[10] Cleve, Richard; Liu, Li; Slofstra, William Perfect Commuting-Operator Strategies for Linear System Games, J. Math. Phys., Volume 58 (2017) no. 01, Paper no. 012202 | MR | Zbl

[11] Cleve, Richard; Mittal, Rajat Characterization of binary constraint system games, International Colloquium on Automata, Languages, and Programming, Springer (2014), pp. 320-331 | Zbl

[12] Coladangelo, Andrea; Goh, Koon Tong; Scarani, Valerio All pure bipartite entangled states can be self-tested, Nature Communications, Volume 8 (2017), Paper no. 15485

[13] Coladangelo, Andrea; Stark, Jalex Robust self-testing for linear constraint system games (2017) | arXiv

[14] Cui, David; Mehta, Arthur; Mousavi, Hamoon; Nezhadi, Seyed Sajjad A generalization of CHSH and the algebraic structure of optimal strategies, Quantum, Volume 4 (2020), Paper no. 346

[15] Diestel, Reinhard; Kühn, Daniela Graph minor hierarchies, Discrete Appl. Math., Volume 145 (2005) no. 2, pp. 167-182 | DOI | MR | Zbl

[16] Gowers, W. T.; Hatami, O. Inverse and stability theorems for approximate representations of finite groups, Mat. Sb., Volume 208 (2017) no. 12, pp. 70-106 | DOI | MR

[17] Holt, Derek KBMAG—Knuth-Bendix in Monoids and Automatic Groups, software package (Available at http://homepages.warwick.ac.uk/~mareg/kbmag/)

[18] Hopcroft, John; Tarjan, Robert Efficient planarity testing, J. Assoc. Comput. Mach., Volume 21 (1974) no. 4, pp. 549-568 | DOI | MR | Zbl

[19] Kalev, Amir; Miller, Carl A. Rigidity of the magic pentagram game, Quantum Sci. Technol., Volume 3 (2018) no. 1, Paper no. 015002

[20] Kaniewski, Jędrzej Weak form of self-testing, Phys. Rev. Research, Volume 2 (2020), Paper no. 033420

[21] Lovász, László On graphs not containing independent circuits, Mat. Lapok., Volume 16 (1965), pp. 289-299 | MR | Zbl

[22] McKague, Matthew; Yang, Tzyh Haur; Scarani, Valerio Robust self-testing of the singlet, J. Phys. A, Volume 45 (2012) no. 45, Paper no. 455304 | MR

[23] Mermin, N. David Simple unified form for the major no-hidden-variables theorems, Phys. Rev. Lett., Volume 65 (1990) no. 27, pp. 3373-3376 | DOI | MR | Zbl

[24] Natarajan, Anand; Vidick, Thomas A quantum linearity test for robustly verifying entanglement, STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York (2017), pp. 1003-1015 | DOI | MR | Zbl

[25] Ol’shanskii, A. Yu. Geometry of Defining Relations in Groups, 70, Springer Science & Business Media, 2012

[26] Paddock, Connor; Russo, Vincent; Silverthorne, Turner; Slofstra, William Supplementary Software, https://github.com/vprusso/graph_incidence_nonlocal_games, 2022

[27] Peres, Asher Two simple proofs of the Kochen-Specker theorem, J. Phys. A, Volume 24 (1991) no. 4, p. L175-L178 | DOI | MR | Zbl

[28] Robertson, Neil; Seymour, Paul D. Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, Volume 63 (1995) no. 1, pp. 65-110 | DOI | MR | Zbl

[29] Robertson, Neil; Seymour, Paul D. Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B, Volume 92 (2004) no. 2, pp. 325-357 | DOI | MR | Zbl

[30] Sage Developers SageMath, the Sage Mathematics Software System (Version 8.1) (2017) (https://www.sagemath.org)

[31] Scholz, Volkher B.; Werner, Reinhard F. Tsirelson’s problem (2008) | arXiv

[32] Slofstra, William The Set of Quantum Correlations is Not Closed, Forum Math. Pi, Volume 7 (2019), Paper no. e1, 41 pages | MR | Zbl

[33] Slofstra, William Tsirelson’s problem and an embedding theorem for groups arising from non-local games, J. Amer. Math. Soc., Volume 33 (2020) no. 1, pp. 1-56 | DOI | MR | Zbl

[34] Van Kampen, Egbert R. On Some Lemmas in the Theory of Groups, Amer. J. Math., Volume 55 (1933) no. 1, pp. 268-273 | MR | Zbl

[35] Wagner, Klaus Über eine Eigenschaft der ebenen Komplexe, Math. Ann., Volume 114 (1937) no. 1, pp. 570-590 | DOI | Zbl

[36] Wu, Xingyao; Bancal, Jean-Daniel; McKague, Matthew; Scarani, Valerio Device-independent parallel self-testing of two singlets, Phys. Rev. A, Volume 93 (2016) no. 6, Paper no. 062121

Cited by Sources: