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

arXiv:2609.20746

Mermin-Peres magic rectangles modulo odd primes

Josse van Dobben de Bruyn, Remy van Dobben de Bruyn, Peter Zeman

quant-phSubmitted Sep 17, 2026• Announced Sep 18, 2026• 0 citations• Revised Oct 5, 2026 (v2)
v1 · Sep 17, 2026v2 · Oct 5, 2026
arXivHTMLPDF

Abstract

The Mermin-Peres magic square provides a simple example of a system of linear equations over $\mathbb{Z}/2\mathbb{Z}$ which has no classical solutions but does have a finite-dimensional operator solution. For a long time, it was not known how to construct similar examples over $\mathbb{Z}/d\mathbb{Z}$ with $d$ odd. In this paper, we construct, for every integer $d \geq 2$, a linear system over $\mathbb{Z}/d\mathbb{Z}$ that has a finite-dimensional operator solution but no classical solution. For an odd prime $p$, our operators act on two $p$-dimensional qudits and generate a finite $p$-group obtained by adjoining diagonal polynomial phase operators to the generalized Pauli group, thereby forming a natural analogue of the Mermin--Peres magic square. Classical inconsistency follows from an elementary linearity argument comparing assignments on abelian subgroups. Furthermore, we prove a sharp threshold for the required degree of the added polynomial phase operators: our construction uses polynomials up to degree $p - 1$, and we show that the group formed by polynomials up to degree $p - 2$ is noncontextual.

Comments
15 pages. v2: added Section 6, added citation of Frembs paper, minor improvements to the exposition

Related papers

Classical vs quantum satisfiability in linear constraint systems modulo an integer

Hammam Qassim, Joel J. Wallman

Abstract 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.

arXiv:1911.11171•Journal of Physics A Mathematical and Theoretical•Jul 6, 2020•3 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

No quantum solutions to linear constraint systems in odd dimension from Pauli group and diagonal Cliffords

Markus Frembs, Cihan Okay, Ho Yiu Chung

Linear constraint systems (LCS) have proven to be a surprisingly prolific tool in the study of non-classical correlations and various related issues in quantum foundations. Many results are known for the Boolean case, yet the generalisation to systems of odd dimension is largely open. In particular, it is not known whether there exist LCS in odd dimension, which admit finite-dimensional quantum, but no classical solutions. In recent work, \cite{QassimWallman2020} have shown that unlike in the Boolean case, where the n -qubit Pauli group gives rise to quantum solutions of LCS such as the Mermin-Peres square, the n-qudit Pauli group never gives rise to quantum solutions of a LCS in odd dimension. Here, we generalise this result towards the Clifford hierarchy. More precisely, we consider tensor products of groups generated by (single-qudit) Pauli and diagonal Clifford operators.

arXiv:2209.14018•Quantum•Jan 8, 2025•2 citations

Satisfiability of Commutative vs. Non-Commutative CSPs

Bulatov, Andrei A., Živný, Stanislav

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.

•Jan 1, 2025•0 citations

Completeness for Prime-Dimensional Phase-Affine Circuits

Colin Blake

Equational reasoning about circuits underpins quantum-circuit optimisation and verification. The qubit CNOT-dihedral fragment achieves this through phase polynomials, layered normal forms, and a complete equational theory; we develop the corresponding theory for prime-dimensional qudits, where basis labels, value controls, and phase exponents share prime-field arithmetic. We first describe reversible affine circuits over Fd as transformations x->Ax+b, with an affine normal form extending Lafont's linear normal form by translations. Adjoining finite-angle diagonal phases by polynomial degree yields linear, quadratic (odd prime), and cubic (prime greater than 3) calculi whose binomial-basis identities expose the mixed diagonal gates forced by affine transport. These calculi have unique phase-affine normal forms and are complete: semantic equality coincides with derivable equality, giving a prime-dimensional phase-polynomial analogue of the CNOT-dihedral equational theory.

quant-pharXiv:2603.06466•Mar 9, 2026•0 citations

Satisfiability of Commutative vs. Non-Commutative CSPs

Andreǐ A. Bulatov, Stanislav Živný

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.

arXiv:2404.11709•Leibniz international proceedings in informatics•Apr 17, 2024•0 citations
The Mermin-Peres magic square provides a simple example of a system of linear equations over Z/2Z\mathbb{Z}/2\mathbb{Z}Z/2Z which has no classical solutions but does have a finite-dimensional operator solution. For a long time, it was not known how to construct similar examples over Z/dZ\mathbb{Z}/d\mathbb{Z}Z/dZ with ddd odd. In this paper, we construct, for every integer d≥2d \geq 2d≥2, a linear system over Z/dZ\mathbb{Z}/d\mathbb{Z}Z/dZ that has a finite-dimensional operator solution but no classical solution. For an odd prime ppp, our operators act on two ppp-dimensional qudits and generate a finite ppp-group obtained by adjoining diagonal polynomial phase operators to the generalized Pauli group, thereby forming a natural analogue of the Mermin--Peres magic square. Classical inconsistency follows from an elementary linearity argument comparing assignments on abelian subgroups. Furthermore, we prove a sharp threshold for the required degree of the added polynomial phase operators: our construction uses polynomials up to degree p−1p - 1p−1, and we show that the group formed by polynomials up to degree p−2p - 2p−2 is noncontextual.
Abstract 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.
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.
Linear constraint systems (LCS) have proven to be a surprisingly prolific tool in the study of non-classical correlations and various related issues in quantum foundations. Many results are known for the Boolean case, yet the generalisation to systems of odd dimension is largely open. In particular, it is not known whether there exist LCS in odd dimension, which admit finite-dimensional quantum, but no classical solutions. In recent work, \cite{QassimWallman2020} have shown that unlike in the Boolean case, where the n -qubit Pauli group gives rise to quantum solutions of LCS such as the Mermin-Peres square, the n-qudit Pauli group never gives rise to quantum solutions of a LCS in odd dimension. Here, we generalise this result towards the Clifford hierarchy. More precisely, we consider tensor products of groups generated by (single-qudit) Pauli and diagonal Clifford operators.
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.
Equational reasoning about circuits underpins quantum-circuit optimisation and verification. The qubit CNOT-dihedral fragment achieves this through phase polynomials, layered normal forms, and a complete equational theory; we develop the corresponding theory for prime-dimensional qudits, where basis labels, value controls, and phase exponents share prime-field arithmetic. We first describe reversible affine circuits over Fd as transformations x->Ax+b, with an affine normal form extending Lafont's linear normal form by translations. Adjoining finite-angle diagonal phases by polynomial degree yields linear, quadratic (odd prime), and cubic (prime greater than 3) calculi whose binomial-basis identities expose the mixed diagonal gates forced by affine transport. These calculi have unique phase-affine normal forms and are complete: semantic equality coincides with derivable equality, giving a prime-dimensional phase-polynomial analogue of the CNOT-dihedral equational theory.
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 ppp; for such CSPs, we obtain a separation of classical satisfiability and satisfiability via operators on infinite-dimensional Hilbert spaces. Furthermore, if p=2p=2p=2, such CSPs also have gaps separating classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces.