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
mathbbZ2-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.
We investigate quantum relaxations of two key decision problems in computer science: the constraint satisfaction problem (CSP) and the structure isomorphism problem. CSP asks whether a homomorphism exists between two relational structures, while structure isomorphism seeks an isomorphism between them. In recent years, it has become increasingly apparent that many special cases of CSP can be reformulated in terms of the existence of perfect classical strategies in non-local games, a key topic of study in quantum information theory. These games have allowed us to study quantum advantage in relation to many important decision problems, such as the k-colouring problem, and the problem of solving binary constraint systems. Abramsky et al. (2017) have shown that all of these games can be seen as special instances of a non-local CSP game. Moreover, they show that perfect quantum strategies in this CSP game can be viewed as Kleisli morphisms of a graded monad on the category of relational structures, which they dub the quantum monad. In this way, the quantum monad provides a categorical characterisation of quantum advantage for the non-local CSP game. In this work we solidify and expand the results of Abramsky et al., answering several of their open questions. Firstly, we compare the definition of quantum graph homomorphisms arising from this work with an earlier definition of the concept due to Mančinska and Roberson and show that there are graphs which exhibit quantum advantage under one definition but not the other. Our second contribution is to extend the results of Abramsky et al. which only hold in the tensor product framework of quantum mechanics to the commuting operator framework. Next, we study a non-local structure isomorphism game, which generalises the well-studied graph isomorphism game. We show how the construction of the quantum monad can be refined to provide categorical semantics for quantum strategies in this game. This results in a category where morphisms coincide with quantum homomorphisms and isomorphisms coincide with quantum isomorphisms.
We consider a class of nonlocal games that are related to binary constraint systems (BCSs) in a manner similar to the games implicit in the work of Mermin [N.D. Mermin, "Simple unified form for the major no-hidden-variables theorems," Phys. Rev. Lett., 65(27):3373-3376, 1990], but generalized to n binary variables and m constraints. We show that, whenever there is a perfect entangled protocol for such a game, there exists a set of binary observables with commutations and products similar to those exhibited by Mermin. We also show how to derive upper bounds strictly below 1 for the the maximum entangled success probability of some BCS games. These results are partial progress towards a larger project to determine the computational complexity of deciding whether a given instance of a BCS game admits a perfect entangled strategy or not.
We introduce the concept of quantum polymorphisms to the complexity theory of quantum constraint satisfaction. Via this notion, we build an algebraic framework of reductions between quantum CSPs, and we establish a Galois connection between quantum polymorphism minions and quantum relational constructions. By leveraging a contextuality property of quantum polymorphisms, we fully characterise the existence of commutativity gadgets for relational structures, introduced by Ji as a method for achieving quantum soundness of classical CSP reductions. Prior to our work, only a partial classification was known for a subclass of Boolean languages and for non-Boolean languages meeting specific structural conditions [Culf--Mastel, FOCS'25]. As an application of our framework, we prove that the quantum CSPs parameterised by odd cycles and the quantum CSP expressing quantum satisfiability of Siggers clauses are undecidable.
Linear system games are a generalization of Mermin’s magic square game introduced by Cleve and Mittal. They show that perfect strategies for linear system games in the tensor-product model of entanglement correspond to finite-dimensional operator solutions of a certain set of non-commutative equations. We investigate linear system games in the commuting-operator model of entanglement, where Alice and Bob’s measurement operators act on a joint Hilbert space, and Alice’s operators must commute with Bob’s operators. We show that perfect strategies in this model correspond to possibly infinite-dimensional operator solutions of the non-commutative equations. The proof is based around a finitely presented group associated with the linear system which arises from the non-commutative equations.
Mermin and Peres showed that there are Boolean constraint systems (BCSs) that are not satisfiable but are satisfiable with quantum observables. This has led to a burgeoning theory of quantum satisfiability for constraint systems, connected to nonlocal games and quantum contextuality. In this theory, different types of quantum satisfying assignments can be understood as representations of the BCS algebra of the system. This theory is closely related to the theory of synchronous games and algebras, and every synchronous algebra is a BCS algebra and vice versa. The purpose of this paper is to further develop the role of BCS algebras in this theory and tie up some loose ends: We give a new presentation of BCS algebras in terms of joint spectral projections and show that it is equivalent to the standard definition. We construct a constraint system that is C∗-satisfiable but not tracially satisfiable. We show that certain reductions between constraint systems lead to ∗-homomorphisms between the BCS algebras of the systems, and we use this to streamline and strengthen several results of Atserias, Kolaitis, and Severini on analogues of Schaefer’s dichotomy theorem. In particular, we show that the question of whether or not there is a nonhyperlinear group is linked to dichotomy theorems for RU-satisfiability.