Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs

Connor Paddock

Published Jun 6, 2019• 1 citation
OpenAlex

Abstract

To every linear binary-constraint system (LinBCS) non-local game, there is an associated algebraic object called the solution group. Cleve, Liu, and Slofstra showed that a LinBCS game has a perfect quantum strategy if and only if an element, denoted by $J$, is non-trivial in this group. In this work, we restrict to the set of graph-LinBCS games, which arise from $\\mathbb{Z}_2$-linear systems $Ax=b$, where $A$ is the incidence matrix of a connected graph, and $b$ is a (non-proper) vertex $2$-colouring. In this context, Arkhipov's theorem states that the corresponding graph-LinBCS game has a perfect quantum strategy, and no perfect classical strategy, if and only if the graph is non-planar and the $2$-colouring $b$ has odd parity. In addition to efficient methods for detecting quantum and classical strategies for these games, we show that computing the classical value, a problem that is NP-hard for general LinBCS games can be done efficiently. In this work, we describe a graph-LinBCS game by a $2$-coloured graph and call the corresponding solution group a graph incidence group. As a consequence of the Robertson-Seymour theorem, we show that every quotient-closed property of a graph incidence group can be expressed by a finite set of forbidden graph minors. Using this result, we recover one direction of Arkhipov's theorem and derive the forbidden graph minors for the graph incidence group properties: finiteness, and abelianness. Lastly, using the representation theory of the graph incidence group, we discuss how our graph minor criteria can be used to deduce information about the perfect strategies for graph-LinBCS games.

Related papers

Arkhipov’s theorem, graph minors, and linear system nonlocal games

Connor Paddock, Vincent M. Russo, Turner Silverthorne +1 more

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.

arXiv:2205.04645•Algebraic Combinatorics•Aug 29, 2023•0 citations

Synchronous linear constraint system games

Adina Goldberg

Mathematical models of quantum mechanics can be studied and distinguished using nonlocal games. We discuss a class of nonlocal games called synchronous linear constraint system (syncLCS) games. We unify two algebraic approaches to studying syncLCS games and relate these games to nonlocal games played on graphs, known as graph isomorphism games. In more detail, syncLCS games are nonlocal games that verify whether or not two players share a solution to a given system of equations. Two algebraic objects associated with these games encode information about the existence of perfect strategies. They are called the game algebra and the solution group. Here, we show that these objects are essentially the same, i.e., the game algebra is a suitable quotient of the group algebra of the solution group. We also demonstrate that syncLCS games are equivalent to graph isomorphism games on a pair of graphs parameterized by the linear system.

arXiv:2007.02782•Journal of Mathematical Physics•Mar 1, 2021•9 citations

Binary Constraint System Games and Locally Commutative Reductions

Zhengfeng Ji

A binary constraint system game is a two-player one-round non-local game defined by a system of Boolean constraints. The game has a perfect quantum strategy if and only if the constraint system has a quantum satisfying assignment [R. Cleve and R. Mittal, arXiv:1209.2729]. We show that several concepts including the quantum chromatic number and the Kochen-Specker sets that arose from different contexts fit naturally in the binary constraint system framework. The structure and complexity of the quantum satisfiability problems for these constraint systems are investigated. Combined with a new construct called the commutativity gadget for each problem, several classic NP-hardness reductions are lifted to their corresponding quantum versions. We also provide a simple parity constraint game that requires $Ω(\sqrt{n})$ EPR pairs in perfect strategies where $n$ is the number of variables in the constraint system.

arXiv:1310.3794•Oct 14, 2013•28 citations

Operator solutions of linear systems and small cancellation

William Slofstra, Luming Zhang

We show that if a graph has minimum vertex degree at least d and girth at least g, where (d, g) is (3, 6) or (4, 4), then the incidence system of the graph has a (possibly infinite-dimensional) quantum solution over $\mathbb{Z}_p$ for every choice of vertex weights and integer $p \geq 2$. In particular, there are linear systems over $\mathbb{Z}_p$, for $p$ an odd prime, such that the corresponding linear system nonlocal game has a perfect commuting-operator strategy, but no perfect classical strategy.

arXiv:2412.10305•Dec 13, 2024•0 citations

A complete classification of the existence of finite-dimensional quantum solutions to inconsistent linear constraint systems

Markus Frembs

Linear constraint systems (LCS) provide a compact algebraic language for nonlocal games and state-independent contextuality. In the binary case the Mermin--Peres square shows that inconsistent LCS can be solved by promoting variables to local Pauli operators, whereas a series of no-go results excludes analogous Pauli-, Clifford- and monomial unitary-based constructions at odd prime modulus. We first isolate the reason for this difference: for tensor-product quantum solutions, the obstruction to a classical solution of a LCS over $\mathbb{Z}_n$ decomposes into obstruction classes carried by the individual factors. As a consequence, a genuinely global obstruction cannot arise solely by tensoring locally unobstructed systems. The argument is specific to odd modulus; at even modulus the reordering phase need not vanish, as in Pauli-based examples. Given this distinction, we instead associate LCS to finite arrangements of rank-one projectors and resolutions of the identity in finite-dimensional vector spaces. Quantum solvability for such LCS is automatic and the search for a quantum-classical gap rests entirely on proving classical unsatisfiability of the underlying modular incidence problem of the arrangement. By relating such LCS with group-valued frame functions, we identify a family of examples in the work of [Harding, Jager, and Smith, Int. J. Theor. Phys. 44, 539 (2005)]. To establish the (non)existence of classically unsatisfiable LCS over $\mathbb{Z}_n$ with quantum solutions in all dimensions $d$ and for all $n\in\mathbb{N}$, we further construct explicit examples for the cases $d=n$ prime. Our main result thus positively resolves the existence problem of such LCS beyond the binary case: such systems exist if and only if $d\geq 3$ and $\gcd(n,d)>1$. Moreover, we establish the existence of LCS with a quantum-classical gap over finite fields if and only if $d\geq 3$ and $p\mid d$.

quant-pharXiv:2609.16490•Sep 16, 2026•0 citations

Linear game non-contextuality and Bell inequalities - a graph-theoretic approach

P. Gnaciński, Monika Rosicka, Ravishankar Ramanathan +4 more

We study the classical and quantum values of one- and two-party linear games, an important class of unique games that generalizes the well-known XOR games to the case of non-binary outcomes. We introduce a ``constraint graph" associated to such a game, with the constraints defining the linear game represented by an edge-coloring of the graph. We use the graph-theoretic characterization to relate the task of finding equivalent games to the notion of signed graphs and switching equivalence from graph theory. We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of more general XOR-d games to the identification of specific cycles in the graph. We construct an orthogonality graph of the game from the constraint graph and study its Lovász theta number as a general upper bound on the quantum value even in the case of single-party contextual XOR-d games. Linear games possess appealing properties for use in device-independent applications such as randomness of the local correlated outcomes in the optimal quantum strategy. We study the possibility of obtaining quantum algebraic violation of these games, and show that no finite linear game possesses the property of pseudo-telepathy leaving the frequently used chained Bell inequalities as the natural candidates for such applications. We also show this lack of pseudo-telepathy for multi-party XOR-type inequalities involving two-body correlation functions.

arXiv:1511.05415•Nov 17, 2015•2 citations
To every linear binary-constraint system (LinBCS) non-local game, there is an associated algebraic object called the solution group. Cleve, Liu, and Slofstra showed that a LinBCS game has a perfect quantum strategy if and only if an element, denoted by JJJ, is non-trivial in this group. In this work, we restrict to the set of graph-LinBCS games, which arise from mathbbZ2\\mathbb{Z}_2mathbbZ2​-linear systems Ax=bAx=bAx=b, where AAA is the incidence matrix of a connected graph, and bbb is a (non-proper) vertex 222-colouring. In this context, Arkhipov's theorem states that the corresponding graph-LinBCS game has a perfect quantum strategy, and no perfect classical strategy, if and only if the graph is non-planar and the 222-colouring bbb has odd parity. In addition to efficient methods for detecting quantum and classical strategies for these games, we show that computing the classical value, a problem that is NP-hard for general LinBCS games can be done efficiently. In this work, we describe a graph-LinBCS game by a 222-coloured graph and call the corresponding solution group a graph incidence group. As a consequence of the Robertson-Seymour theorem, we show that every quotient-closed property of a graph incidence group can be expressed by a finite set of forbidden graph minors. Using this result, we recover one direction of Arkhipov's theorem and derive the forbidden graph minors for the graph incidence group properties: finiteness, and abelianness. Lastly, using the representation theory of the graph incidence group, we discuss how our graph minor criteria can be used to deduce information about the perfect strategies for graph-LinBCS games.
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.
Mathematical models of quantum mechanics can be studied and distinguished using nonlocal games. We discuss a class of nonlocal games called synchronous linear constraint system (syncLCS) games. We unify two algebraic approaches to studying syncLCS games and relate these games to nonlocal games played on graphs, known as graph isomorphism games. In more detail, syncLCS games are nonlocal games that verify whether or not two players share a solution to a given system of equations. Two algebraic objects associated with these games encode information about the existence of perfect strategies. They are called the game algebra and the solution group. Here, we show that these objects are essentially the same, i.e., the game algebra is a suitable quotient of the group algebra of the solution group. We also demonstrate that syncLCS games are equivalent to graph isomorphism games on a pair of graphs parameterized by the linear system.
A binary constraint system game is a two-player one-round non-local game defined by a system of Boolean constraints. The game has a perfect quantum strategy if and only if the constraint system has a quantum satisfying assignment [R. Cleve and R. Mittal, arXiv:1209.2729]. We show that several concepts including the quantum chromatic number and the Kochen-Specker sets that arose from different contexts fit naturally in the binary constraint system framework. The structure and complexity of the quantum satisfiability problems for these constraint systems are investigated. Combined with a new construct called the commutativity gadget for each problem, several classic NP-hardness reductions are lifted to their corresponding quantum versions. We also provide a simple parity constraint game that requires Ω(n)Ω(\sqrt{n})Ω(n​) EPR pairs in perfect strategies where nnn is the number of variables in the constraint system.
We show that if a graph has minimum vertex degree at least d and girth at least g, where (d, g) is (3, 6) or (4, 4), then the incidence system of the graph has a (possibly infinite-dimensional) quantum solution over Zp\mathbb{Z}_pZp​ for every choice of vertex weights and integer p≥2p \geq 2p≥2. In particular, there are linear systems over Zp\mathbb{Z}_pZp​, for ppp an odd prime, such that the corresponding linear system nonlocal game has a perfect commuting-operator strategy, but no perfect classical strategy.
Linear constraint systems (LCS) provide a compact algebraic language for nonlocal games and state-independent contextuality. In the binary case the Mermin--Peres square shows that inconsistent LCS can be solved by promoting variables to local Pauli operators, whereas a series of no-go results excludes analogous Pauli-, Clifford- and monomial unitary-based constructions at odd prime modulus. We first isolate the reason for this difference: for tensor-product quantum solutions, the obstruction to a classical solution of a LCS over Zn\mathbb{Z}_nZn​ decomposes into obstruction classes carried by the individual factors. As a consequence, a genuinely global obstruction cannot arise solely by tensoring locally unobstructed systems. The argument is specific to odd modulus; at even modulus the reordering phase need not vanish, as in Pauli-based examples. Given this distinction, we instead associate LCS to finite arrangements of rank-one projectors and resolutions of the identity in finite-dimensional vector spaces. Quantum solvability for such LCS is automatic and the search for a quantum-classical gap rests entirely on proving classical unsatisfiability of the underlying modular incidence problem of the arrangement. By relating such LCS with group-valued frame functions, we identify a family of examples in the work of [Harding, Jager, and Smith, Int. J. Theor. Phys. 44, 539 (2005)]. To establish the (non)existence of classically unsatisfiable LCS over Zn\mathbb{Z}_nZn​ with quantum solutions in all dimensions ddd and for all n∈Nn\in\mathbb{N}n∈N, we further construct explicit examples for the cases d=nd=nd=n prime. Our main result thus positively resolves the existence problem of such LCS beyond the binary case: such systems exist if and only if d≥3d\geq 3d≥3 and gcd⁡(n,d)>1\gcd(n,d)>1gcd(n,d)>1. Moreover, we establish the existence of LCS with a quantum-classical gap over finite fields if and only if d≥3d\geq 3d≥3 and p∣dp\mid dp∣d.
We study the classical and quantum values of one- and two-party linear games, an important class of unique games that generalizes the well-known XOR games to the case of non-binary outcomes. We introduce a ``constraint graph" associated to such a game, with the constraints defining the linear game represented by an edge-coloring of the graph. We use the graph-theoretic characterization to relate the task of finding equivalent games to the notion of signed graphs and switching equivalence from graph theory. We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of more general XOR-d games to the identification of specific cycles in the graph. We construct an orthogonality graph of the game from the constraint graph and study its Lovász theta number as a general upper bound on the quantum value even in the case of single-party contextual XOR-d games. Linear games possess appealing properties for use in device-independent applications such as randomness of the local correlated outcomes in the optimal quantum strategy. We study the possibility of obtaining quantum algebraic violation of these games, and show that no finite linear game possesses the property of pseudo-telepathy leaving the frequently used chained Bell inequalities as the natural candidates for such applications. We also show this lack of pseudo-telepathy for multi-party XOR-type inequalities involving two-body correlation functions.