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.

Revised:

Accepted:

Published online:

Keywords: nonlocal games, graph minors, quantum information

Paddock, Connor ^{1};
Russo, Vincent ^{2};
Silverthorne, Turner ^{3};
Slofstra, William ^{4}

@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] Quantum magic rectangles: Characterization and application to certified randomness expansion, Phys. Rev. Research, Volume 2 (2020), Paper no. 043317

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

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

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

[5] Term Rewriting and All That, Cambridge University Press, 1998 | DOI

[6] 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] On disjoint cycles, Internat. J. Found. Comput. Sci., Volume 5 (1994) no. 01, pp. 59-68 | DOI | Zbl

[8] Extremal graph theory, Courier Corporation, 2004

[9] The Geometry of the Word Problem for Finitely Generated Groups, Springer Science & Business Media, 2007

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

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

[12] All pure bipartite entangled states can be self-tested, Nature Communications, Volume 8 (2017), Paper no. 15485

[13] Robust self-testing for linear constraint system games (2017) | arXiv

[14] A generalization of CHSH and the algebraic structure of optimal strategies, Quantum, Volume 4 (2020), Paper no. 346

[15] Graph minor hierarchies, Discrete Appl. Math., Volume 145 (2005) no. 2, pp. 167-182 | DOI | MR | Zbl

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

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

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

[19] Rigidity of the magic pentagram game, Quantum Sci. Technol., Volume 3 (2018) no. 1, Paper no. 015002

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

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

[22] Robust self-testing of the singlet, J. Phys. A, Volume 45 (2012) no. 45, Paper no. 455304 | MR

[23] 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] 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] Geometry of Defining Relations in Groups, 70, Springer Science & Business Media, 2012

[26] Supplementary Software, https://github.com/vprusso/graph_incidence_nonlocal_games, 2022

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

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

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

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

[31] Tsirelson’s problem (2008) | arXiv

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

[33] 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] On Some Lemmas in the Theory of Groups, Amer. J. Math., Volume 55 (1933) no. 1, pp. 268-273 | MR | Zbl

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

[36] Device-independent parallel self-testing of two singlets, Phys. Rev. A, Volume 93 (2016) no. 6, Paper no. 062121

*Cited by Sources: *