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.
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.
Constraint satisfaction problems (CSPs) are a natural class of decision problems where one must decide whether there is an assignment to variables that satisfies a given formula. Schaefer’s dichotomy theorem, and its extension to all alphabets due to Bulatov and Zhuk, shows that CSP languages are either efficiently decidable, or NP-complete. It is possible to extend CSP languages to quantum assignments using the formalism of nonlocal games. Due to the equality of complexity classes MIP* = RE, general succinctly-presented entangled CSPs are RE-complete. In this work, we show that a wide range of NP-complete CSPs become RE-complete in this setting, including all boolean CSPs, such as 3SAT, as well as 3-colouring. This also implies that these CSP languages remain undecidable even when not succinctly presented.To show this, we work in the weighted algebra framework introduced by Mastel and Slofstra, where synchronous strategies for a nonlocal game are represented by tracial states on an algebra. Along the way, we improve the subdivision technique in order to be able to separate constraints in the CSP while preserving constant soundness, construct commutativity gadgets for all boolean CSPs, and show a variety of relations between the different ways of presenting CSPs as games.
The Mermin-Peres magic square is a celebrated example of a system of Boolean linear equations that is not (classically) satisfiable but is satisfiable via linear operators on a Hilbert space of dimension four. A natural question is then, for what kind of problems such a phenomenon occurs? Atserias, Kolaitis, and Severini answered this question for all Boolean Constraint Satisfaction Problems (CSPs): For 0-Valid-SAT, 1-Valid-SAT, 2-SAT, Horn-SAT, and Dual Horn-SAT, classical satisfiability and operator satisfiability is the same and thus there is no gap; for all other Boolean CSPs, these notions differ as there are gaps, i.e., there are unsatisfiable instances that are satisfiable via operators on Hilbert spaces. We generalize their result to CSPs on arbitrary finite domains and give an almost complete classification: First, we show that NP-hard CSPs admit a separation between classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces. Second, we show that tractable CSPs of bounded width have no satisfiability gaps of any kind. Finally, we show that tractable CSPs of unbounded width can simulate, in a satisfiability-gap-preserving fashion, linear equations over an Abelian group of prime order p; for such CSPs, we obtain a separation of classical satisfiability and satisfiability via operators on infinite-dimensional Hilbert spaces. Furthermore, if p=2, such CSPs also have gaps separating classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces.
The Mermin-Peres magic square is a celebrated example of a system of Boolean linear equations that is not (classically) satisfiable but is satisfiable via linear operators on a Hilbert space of dimension four. A natural question is then, for what kind of problems such a phenomenon occurs? Atserias, Kolaitis, and Severini answered this question for all Boolean Constraint Satisfaction Problems (CSPs): For 0-Valid-SAT, 1-Valid-SAT, 2-SAT, Horn-SAT, and Dual Horn-SAT, classical satisfiability and operator satisfiability is the same and thus there is no gap; for all other Boolean CSPs, these notions differ as there are gaps, i.e., there are unsatisfiable instances that are satisfiable via operators on Hilbert spaces. We generalize their result to CSPs on arbitrary finite domains and give an almost complete classification: First, we show that NP-hard CSPs admit a separation between classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces. Second, we show that tractable CSPs of bounded width have no satisfiability gaps of any kind. Finally, we show that tractable CSPs of unbounded width can simulate, in a satisfiability-gap-preserving fashion, linear equations over an Abelian group of prime order p; for such CSPs, we obtain a separation of classical satisfiability and satisfiability via operators on infinite-dimensional Hilbert spaces. Furthermore, if p = 2, such CSPs also have gaps separating classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces.
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.
Schaefer introduced a framework for generalized satisfiability problems on the Boolean domain and characterized the computational complexity of such problems. We investigate an algebraization of Schaefer's framework in which the Fourier transform is used to represent constraints by multilinear polynomials in a unique way. This representation of constraints gives rise to a relaxation of the notion of satisfiability in which the values to variables are linear operators on some Hilbert space. For constraints given by a system of linear equations over the two-element field, earlier work in the foundations of quantum mechanics has shown that there are systems that have no solutions in the Boolean domain, but have solutions via operator assignments on some finite-dimensional Hilbert space. Our main result is a complete characterization of the classes of Boolean relations for which there is a gap between satisfiability in the Boolean domain and the relaxation of satisfiability via operator assignments.
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.