{'fraction_non_alphanumeric': 0.04285374176652647, 'fraction_numerical': 0.011387985080549163, 'mean_word_length': 3.9301643192488265, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Classical vs. quantum satisfiability in linear constraint systems modulo an integer

A system of linear constraints can be unsatisfiable and yet admit a solution in the form of quantum observables whose correlated outcomes satisfy the constraints. Recently, it has been claimed that such a satisfiability gap can be demonstrated using tensor products of generalized Pauli observables in odd dimensions. We provide an explicit proof that no quantum-classical satisfiability gap in any linear constraint system can be achieved using these observables. We prove a few other results for linear constraint systems modulo d>2. We show that a characterization of the existence of quantum solutions when d is prime, due to Cleve et al, holds with a small modification for arbitrary d. We identify a key property of some linear constraint systems, called phase-commutation, and give a no-go theorem for the existence of quantum solutions to constraint systems for odd d whenever phase-commutation is present. As a consequence, all natural generalizations of the Peres-Mermin magic square and pentagram to odd prime d do not exhibit a satisfiability gap.


I. INTRODUCTION
The study of linear constraint systems (LCS) originated with the simple proofs of contextuality of Peres and Mermin [1,2]. These proofs are based on inconsistent systems of linear equations over the binary field that nevertheless admit solutions if we allow for non-commutative versions of the variables, i.e. binary quantum observables. A gap between classical and quantum satisfiability in this setting is a proof of contextuality [3]. In addition, such a gap can be used to define a non-local game which can be won with certainty by quantum players but not by classical players, i.e. a pseudo-telepathic game [4]. This link has turned out to be immensely useful in the study of quantum non-locality [5][6][7][8][9][10][11]. In particular, games constructed from LCSs are suitable for studying the separation between different models of quantum correlations, such as the tensor-product and the commuting-operator models. Difficult questions on the separation of these models can be cast as questions on the quantum satisfiability of binary LCSs, an approach which has recently culminated in a number of major results [8][9][10]. Further, non-local games constructed in this way can be used for devising robust self-testing protocols [12].
Quantum satisfiability of LCSs over Z 2 has been studied in detail, see for example [5][6][7][8]. The purpose of this paper is to shed light on the non-binary case, that is, systems of linear equations over Z d , where d > 2. This case is generally less well-understood, although it was considered to varying extents in Refs. [8,12,13]. For d = 2, the canonical examples of a satisfiability gap rely on the commutation relations of qubit Pauli observables. Pauli observables can be generalized to higher dimensions in a number of different ways. The Weyl-Heisenberg group is arguably the most natural generalization, since it preserves the commutativity structure and error-correction properties of the qubit Pauli group [14]. Elements of this group are commonly referred to as generalized Pauli operators, and are natural candidates for constructing quantum solutions for LCS over Z d for d > 2. Indeed, this was the approach taken in an early version of [12], where robust self-testing routines for maximally entangled qudit states were claimed to exist using generalized Pauli observables in odd dimensions.
Unfortunately the claim in the early version of [12] is false. In this paper, we provide a concise proof that a satisfiability gap cannot be established using tensor products of generalized Pauli observables in odd dimension. This fact follows from the non-negative discrete Wigner function for Hilbert spaces of odd dimension [15][16][17], but, interestingly, does not require the full Wigner function, only its definition at a single point in phase-space. While a discrete Wigner function can be defined in even dimensions based on generalized Pauli observables [18], it is easy to show that a satisfiability gap can be demonstrated using generalized Pauli observables in every even dimension (see Table I).
For a LCS over Z d given by the equation M x = b mod d, checking whether a classical solution exists is easy, for example by Gaussian elimination if d is prime, or other efficient methods if d is not prime [19,20]. On the other hand, checking whether a quantum solution exists is a difficult task. One characterization is given in [8] in terms of the so-called solution group. The solution group associated with M x = b is a finitely presented group which encodes the algebraic relations satisfied by every quantum solution to M x = b. It is generated by symbols {g i }, which can be thought of as a non-commutative relaxation of the variables {x i }, in addition to a special generator J. The characterization in [8] is based on properties of the element J. Namely, for a LCS over Z d with d prime, a quantum solution exists if and only if J is not equivalent to the identity element in the group. Checking whether an element in a finitely presented group is equivalent to the identity is an instance of the word problem, which is undecidable in general. Nevertheless, for small enough instances or in the case of highly structured groups one can use computer software, such as GAP [21], to find a so-called confluent rewriting system, thus solving the word problem for the group.
In this paper, we note a simple extension of the characterization in [8] which covers arbitrary d. Specifically, a quantum solution exists for a LCS over Z d if and only if J has order d. When d is prime, this characterization reduces to the one in [8].
Furthermore, we note a key property of some LCS, which we call phase-commutation. Roughly speaking, phase-commutation is an abstraction of matrix anti-commutation relations of the form AB = −BA. A LCS M x = b exhibits phase-commutation if its non-commutative relaxation (as defined by the solution group) contains two variables, x 1 and x 2 , which commute up to a constant; Importantly, such relations arise in the LCSs of Peres and Mermin. In the current paper, we show that, if d is odd, any relation of the form in eq. (1), or of the more general form in eq. (16), implies that quantum solutions do not exist in any (finite-or infinite-dimensional) Hilbert space. As a consequence, this implies that all natural generalizations of the Peres-Mermin magic square and pentagram to odd prime d do not exhibit a satisfiability gap. This is in contrast to the case of even d, where the Peres-Mermin magic square and pentagram exhibit satisfiability gaps that rely on using Pauli operators to represent eq. (1). In fact, a much stronger statement was proven for d = 2 in Ref. [9], namely that any group generated by involutions can be embedded (in a strong sense) in the solution group of some binary LCS which admits a quantum solution. A significant consequence of this embedding for d = 2 is the separation, proven in the latter work, between commuting and tensor-product quantum nonlocal strategies. Our result shows that a similar statement cannot hold for odd d, as the group defined by the phase-commutation relation in eq. (1) cannot be embedded in a LCS that has a quantum solution.
The idea that phase-commutation can rule out a satisfiability gap appears in (the newer version of) Ref. [12] for particular instances of the magic square and pentagram LCSs, and a similar idea appears more recently in [13], as part of a homotopical treatment of quantum contextuality. In comparison, our exposition is more general (it applies to all LCSs, and we use it to cover all natural generalizations of the square and pentagram for odd d), and perhaps more accessible to the non-expert reader (it does not require familiarity with topological ideas like cell-complexes and group pictures). Figure 1 (a) is a diagrammatic depiction of a LCS that is classically unsatisfiable for all d ≥ 2, since the sum of the variables along the rows is 0, while the sum of the variables along the columns is 1, which is a contradiction.

II. PRELIMINARIES
A quantum solution A ≡ (A 1 , . . . , A n ) is a collection of operators, acting on some Hilbert space, satisfying:  By condition (1), each operator A i is unitary and the eigenvalues are dth roots of unity. By condition (2), whenever x j and x k appear in one of the constraints, their operator counterparts A j and A k commute. In particular, all operators corresponding to a constraint pairwise commute, and therefore can be simultaneously measured. By condition (3), the expectation values of the operators satisfy the specified constraints. Here and below, we set ω ≡ exp 2πi/d, where d is to be understood from context. Quantum solutions for the magic square and pentagram are shown in Figure 2.
For a set S = {s, t, u, . . . }, the free group F (S) generated by S consists of all words in the letters Two words correspond to the same element in F (S) if one of them can be reduced to the other using contractions of the form e = s −1 s = ss −1 , where e is the identity element. Let G be a group. The normal closure of a subset R ⊆ G is the normal subgroup N (R) generated by the set {grg −1 : g ∈ G, r ∈ R}. Let R = {r 1 , . . . , r k } be a set of words in F (S). The finitely presented group with generators S and relations {r 1 = e, . . . , r k = e} is the quotient F (S)/N (R). For further reading related to these definitions, see any standard reference on abstract algebra, for instance [22].
To every linear constraint system one can associate a solution group, which is a finitely presented group with relations that encode the defining properties of a quantum solution. Namely, Definition 1. For a LCS (M, b), the solution group G(M, b) is the finitely presented group generated by the symbols {J, g 1 , . . . , g n } and the relations Proof. Given a quantum solution {A 1 , . . . , A n } in dimension D, it is straight-forward to check that the homomorphic extension of the map φ( The single-qubit Pauli operators can be generalized to arbitrary dimensions D via the generalized Quantum solutions for the magic square (left) and pentagram (right) for d = 2 [2]. Each vertex is a unitary operator whose eigenvalues are dth roots of unity. The operators along a solid (dashed) line multiply to I (−I) modulo d.
shift and boost operators The generalized shift and boost operators satisfy the commutation relation A generalized Pauli operator for a single quDit is any operator A ∝ Z p X q for some p, q ∈ Z D . For n quDits, a generalized Pauli operator is defined as a tensor product of single quDit generalized Paulis. Proof. The first direction is easy: suppose that M x = b has a classical solution x → a ≡ (a 1 , . . . , a n ). Then A j = ω aj I defines a quantum solution in which every operator is a Pauli operator. Conversely, let us assume that the LCS admits a quantum solution {A j } consisting of generalized n-quDit Pauli operators. We will construct a classical solution by consistently assigning a root of unity ω v(σ) to each generalized n-quDit Pauli operator σ. The map v will be defined in terms of the parity operator For a single-quDit Pauli σ = ω k Z p X q , eq. (4) gives v(σ) = k + 2 −1 pq, where the inverse is modulo D.
It can be readily verified that the following identities hold for any n-quDit generalized Paulis σ, τ TABLE I. Quantum solutions to a generalized magic square LCS modulo D = 2t, for odd (even) t on the left (right). In both cases, the generalized two-quDit Pauli operators along every row and column mutually commute, their product along the third column is ω t I = −I, and their product along the rows and remaining columns is I. This shows that a satisfiability gap exists using n-quDit generalized Pauli operators for every even dimension D.
To prove that the map A j → v(A j ) gives a classical solution to the LCS in question, it is enough to show that, if σ and τ are commuting n-quDit generalized Pauli operators, Indeed if that were true then using identities 1 & 3 we get, for every row i of M , A a k for an n-element vector a = (a 1 , . . . , a n ), and, for simplicity, ignoring the phase factors in the definition of generalized Paulis, which does not affect the analysis. Note that v(Z p X q ) + v(Z r X s ) = 2 −1 (pq + rs) ∀ p, q, r, s.
The above proof fails for even D. The proof hinges on the ability to consistently assign a root of unity to every generalized Pauli operator. For σ = ω k Z p X q , eq. (4) reads When D is even, the sum evaluates to 0 whenever q is odd, making it impossible to define the map in this way. One may wonder whether the map v can be defined in a different way for even D. This is also impossible, as shown by the family of quantum solutions in Table I. Note that the parity operator Π D in the proof of Theorem 2 is one of the phase point operators for the discrete Wigner function in odd dimensions [15]. While it is possible to define a discrete Wigner function in even dimensions based on generalized Pauli operators [18], important properties, such as non-negativity of stabilizer states and Clifford-covariance, are lost in that case [23].

IV. PHASE-COMMUTATION AND EXISTENCE OF A QUANTUM SOLUTION
Theorem 2 asserts that a quantum/classical satisfiability gap cannot be illustrated using generalized Pauli operators in odd dimension. We now show that the canonical commutation relations of these operators cannot be embedded in the solution group of a LCS that has a quantum solution. Some of this discussion is inspired by (the corrected version of) Ref. [12], but it applies more generally than what is considered in that work.
A key characterization of quantum satisfiability when d is prime is the following: The proof of Theorem 3 relies on the fact that, when J = e, the group algebra of G(M, b) contains a subspace on which it is easy to construct a quantum solution. It turns out that the proof works for non-prime d as well, provided we make an adjustment to the statement of the theorem. The proof of Theorem 4 does not differ much from that of Theorem 3, which can be found in [8]. We provide a somewhat more concise version of it in Appendix A. Note that Theorem 3 is a special case of Theorem 4 since, for prime d, cyclicity of the powers of J imply that J = e if and only the order of J is d.
Generalized Pauli operators obey commutation relations of the form AB = ω c BA, and are in a sense uniquely determined by these relations. More specifcally, consider the finite group P d with generators {X , Z, η} and relations By Schur's lemma and the fact that η d = e, every irreducible representation of P d assigns a dth root of unity ω j I to η. Furthermore, it was shown by Weyl that up to unitary equivalence every irreducible representation of P d in which j = 0 maps X and Z to (phase-multiples of) the clock and shift operators in some dimension d ′ that divides d [24]. We consider a particular notion of an embedding of eq. (11) into the solution group of a LCS. Namely, suppose that the solution group contains a relation of the form for a pair of generators g and h and some nonzero a, b, c ∈ Z d . We refer to such a relation as a phasecommutation relation in the solution group. A phase-commutation relation implies that the LCS is classically unsatisfiable; no integers x and y can satisfy the equation ax + by = c + by + ax mod d for c = 0 mod d. This notion of an embedding can be motivated by considering the situation for d = 2. Given a group K, a collection of elements k 1 , . . . , k m ∈ K and a non-identity central element η, such that k 2 i = η 2 = e, it was shown in [9] that there exists a LCS M x = b and an embedding ψ : K → G(M, b), such that ψ(k i ) = g i and ψ(η) = J. As ψ is injective, this implies that J = e, and so every such K embeds in the solution group of some LCS which has a (possibly infinite-dimensional) quantum solution.
In contrast, we show next that, for odd d, a phase-commutation relation implies that quantum solutions to the LCS in question do not exist in any dimension, which rules out a satisfiability gap for any LCS in which eq. (11) embeds in the solution group.
Theorem 5. Let d be odd. Suppose that a LCS over Z d has a phase-commutation relation. Then it has no quantum solutions.
Theorem 5 can be proven diagrammatically using symmetries of the so-called group-picture associated with solution groups [9,12]. We avoid group-pictures for the sake of simplicity, and present a more direct proof instead.
Proof. Let S ≡ {J, g 1 , . . . , g n } denote the generators of the solution group G, and S ′ ≡ {J −1 , g −1 1 , . . . , g −1 n }. Let R ⊂ F (S) be the set of relations defining G, so that G = F (S)/N (R). Let g ∈ S and h ∈ S be a phase-commuting pair, so that, in G, Let w be the word J −c g a h b g −a h −b . Since w = e in G, it holds that, in F (S), w is equivalent to an element of the normal closure N (R). This implies that there exist u 1 , . . . , u ℓ ∈ F (S) and q 1 , . . . , q ℓ ∈ R, such that the word is equivalent to w in F (S), that is, W can be reduced to w using only generator contractions of the form g i g −1 i = e. LetW be the "reflected" version of W wherex is obtained from x by reversing the order of multiplication of the letters making up x. For example, if x = g 1 g 2 g 3 thenx = g 3 g 2 g 1 .
Recall, from the definition of solution groups, that each of the relations in R (and therefore each of the q i ) consists of mutually commuting letters from S ∪ S ′ . It therefore holds thatq i = q i = e in G. This implies thatW = e in G. Furthermore, we haveW =w in G, since the same sequence of generator contractions that reduces W to w can be applied to reduceW tow, soW is equivalent tõ w in F (S), and therefore also in G.
Thus we havew = e in G, and therefore h b g a = J c g a h b in G. Combining this with g a h b = J c h b g a implies that J 2c = e in G. Since d is odd, we have 2c = 0 mod d. Therefore, by Theorem 4, there are no quantum solutions.
The statement and proof of Theorem 5 can be generalized by considering relations of the form Following the same steps in the proof of Theorem 5, we can deduce that J 2c = e, which, for c = 0 mod d, implies that the order of J is less than d, and hence that there are no quantum solutions.

V. EXAMPLES
A. Magic square modulo prime d > 2 Let d > 2 be prime. Here we consider a broad class of generalizations of the magic square LCS. Namely, we consider any LCS over Z d of the form in Figure 1 (a) with arbitrary coefficients, i.e. any system of the form for some b ∈ Z 6 d , and some set of coefficients a i , a ′ i ∈ Z d − {0}. We can simplify by making some reductions. First, we assume that the coefficients in the first three constraints are all equal to one, if necessary by relabeling x i → a i x i . Second, as d is prime, every nonzero element of Z d has a multiplicative inverse, so we can divide the last three constraints respectively by the coefficients of x 1 , x 2 , and x 3 . These two steps yield a LCS of the form for some γ i ∈ Z d − {0}, and (generally different) b ∈ Z 6 d . Note that these reductions preserve classical and quantum satisfiability. Denote the above reduced LCS by It is straightforward to check that where the rank is computed modulo d (which is well-defined as d is prime). Thus the system M x = b is classically unsatisfiable only if γ 4 = γ 5 = γ 6 and γ 7 = γ 8 = γ 9 . Essentially this means that we only need to check (d − 1) 2 cases, corresponding to the values of the γ i ∈ Z d − {0} that could make the LCS classically unsatisfiable. As we will see next, in each of these cases a phase-commutation relation prohibits the existence of a satisfiability gap. Proof. If a classical solution exists then a quantum solution exists. Conversely, assume that a quantum solution exists, and denote the associated reduced LCS in eq. (18) by M x = b. Assume that γ 4 = γ 5 = γ 6 ≡ γ and γ 7 = γ 8 = γ 9 ≡ δ, otherwise there is a classical solution and we are done. In the solution group G(M, b), we have g 1 g 2 g 3 = J b1 g 4 g 5 g 6 = J b2 g 7 g 8 g 9 = J b3 We note the group identity Multiplying both sides on the left by g −1 1 and on the right by g −γ 5 reveals the phase-commutation Since d is odd, by Theorem 5 and eq. (23), a necessary condition for the existence of a quantum solution is that −b 1 − γb 2 − δb 3 + b 4 + b 5 + b 6 = 0 mod d. This implies that the LCS is classically satisfiable: This shows that the original LCS in eq. (17) has a classical solution.

B. Magic pentagram modulo prime d > 2
Similar to the magic square LCS, we consider any LCS over Z d of the pentagram form in Figure 1 (b) with arbitrary coefficients, i.e. any system of the form We can perform similar reductions to the magic square case. First, we set all coefficients equal to 1 in the first constraint by relabeling x i → a i x i if necessary. Next, we divide the remaining four constraints by the coefficients of the first variable from the left. Finally, for i = 5, . . . , 10, we relabel x i → a i x i if necessary to ensure that the coefficient of each x i equals 1 in the first constraint it appears in. This yields the LCS It is straightforward to verify that where the rank is computed modulo d. Thus the system M x = b is classically unsatisfiable only if γ i = −1 for all i. Again, we find that phase-commutation prohibits the existence of a satisfiability gap in this case. , we have g 1 g 2 g 3 g 4 = J b1 g 1 g 5 g 6 g 7 = J b2 g 2 g −1 5 g 8 g 9 = J b3 g 3 g −1 6 g −1 8 g 10 =J b4 g 4 g −1 7 g −1 9 g −1 10 = J b5 .
C. Magic square and pentagram modulo odd, composite d When d is a composite integer, Z d is not a field, and one cannot define a vector space over Z d . This makes it difficult to generalize the proofs of the previous two subsections to this setting. In particular, zero-divisors can appear as coefficients in the LCS, making the reductions used in eqs. (18) and (25) inapplicable. Linear algebraic concepts, such as matrix rank and column space, are also invalid in this case, so we cannot use eqs. (20) and (27).
Nevertheless, if the coefficients in the LCS are restricted to {±1}, the arguments used in the prime d case go through almost unchanged. Namely, we can use the same reductions to obtain the LCSs eqs. (18) and (25), and these LCSs satisfy the following. The proofs of Theorems 10 and 11 are identical to those of Theorems 6 and 7, respectively.

VI. CONCLUSION AND REMARKS
The existence of a quantum/classical satisfiability gap in a LCS modulo d is deeply related to whether d is even or odd. Part of this dependence is elucidated by considering generalized Pauli operators. These operators enter the picture in two ways. First, as shown in Theorem 2, generalized Pauli operators in odd d cannot be used to demonstrate a satisfiability gap, since every quantum solution consisting of these operators can be reduced to a classical solution. Second, the canonical commutation relation AB = ω c BA, obeyed by generalized Pauli operators, is itself sufficient to rule out a satisfiability gap when d is odd. Specifically, Theorem 5 shows that if this relation is embedded in the solution group of a LCS over odd d, then quantum solutions do not exist in any dimension. Both of these facts are in contrast to the case of even d; table I shows a family of LCSs for every even d, each of which has a phase-commutation relation, as well as a satisfiability gap which can be demonstrated using generalized Pauli operators in even d. Theorem 5 can be seen as an obstruction to generalizing the embedding theorem of [9], which holds for d = 2, to odd d. The embedding theorem has significant consequences; it plays a key role in proving the separation between the tensor-product and commuting-operator models of two-party quantum correlations. It is a curious fact that this theorem does not hold if d is odd.
In Section V we use the relationship between phase-commutation and satisfiability to prove that certain generalizations of the magic square and pentagram to odd d do not have a satisfiability gap. The LCSs we consider in these examples can be seen as arising from the incidence matrices of (weighted) graphs. Prior work for d = 2 characterizes the existence of a gap in terms of planarity of such graphs [5], but this characterization does not carry over to the case of d > 2. The techniques based on phase-commutation, outlined in the examples in Section V, may become useful in finding such a generalization. It is, however, unclear how simple such a characterization might be. Planarity of a graph can be checked efficiently, see for example [25], but phase-commutation seems to be a more difficult property to check.
Finally, the results in this paper raise the question of whether there exists a LCS over odd d with a classical/quantum satisfiability gap. While no such cases are currently known, an upcoming work by Slofstra and L. Zhang [26] answers this question in the affirmative; there exists a LCS with a classical/quantum gap modulo d for every prime d, with some evidence that the gap is achievable using finite-dimensional quantum solutions.