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:2209.14018 · Quantum

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

Markus Frembs, Cihan Okay, Ho Yiu Chung

Published Jan 8, 2025• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2025-01-08-1583

Related papers

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 from monomial measurement-based quantum computation in odd prime dimension

Markus Frembs, Cihan Okay, Ho Yiu Chung

We combine the study of resources in measurement-based quantum computation (MBQC) with that of quantum solutions to linear constraint systems (LCS). Contextuality of the input state in MBQC has been identified as a key resource for quantum advantage, and in a stronger form, underlies algebraic relations between (measurement) operators which obey classically unsatisfiable (linear) constraints. Here, we compare these two perspectives on contextuality, and study to what extent they are related. More precisely, we associate a LCS to certain MBQC which exhibit strong forms of state-dependent contextuality, and ask if the measurement operators in such MBQC give rise to state-independent contextuality in the form of quantum solutions of its associated LCS. Our main result rules out such quantum solutions for a large class of MBQC. This both sharpens the distinction between state-dependent and state-independent forms of contextuality, and further generalises results on the non-existence of quantum solutions to LCS in finite odd (prime) dimension.

quant-pharXiv:2601.11367•Jan 19, 2026•0 citations

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

Mermin-Peres magic rectangles modulo odd primes

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

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.

quant-pharXiv:2609.20746•Sep 18, 2026•0 citations

A Review of Galois Qudits

Adam Wills

Galois qudits are $q$-dimensional quantum systems whose choice of Pauli group encodes the arithmetic of some finite field $\mathbb{F}_q$. They differ from the more familiar modular qudit, which are the same quantum system but whose choice of Pauli group are the clock and shift operators, which encode the arithmetic of integer addition and multiplication modulo $q$. Galois qudits are a useful mathematical construct that allow us to leverage the mathematical tools that are native to the larger qudit while only physically building smaller qudits. In particular, a Galois qudit of dimension $q = 2^s$ is exactly the same thing as a collection of $s$ qubits, not only in its Hilbert space, but also in its Pauli group, and Clifford hierarchy. This formalism has found a lot of utility recently in constructing quantum error-correcting codes over qubits with useful properties. In this review, we build on existing literature to collect and formalise facts and proofs about Galois qudits over binary extension fields. We define them and their Clifford hierarchies, describe what it means to measure their Pauli operators, describe their stabiliser tableaux, formally define qudit-to-qubit mappings, and finally describe quantum Reed-Solomon codes.

quant-pharXiv:2605.18981•May 20, 2026•0 citations

Clifford-hierarchy stabilizer formalism with applications to twisted quantum doubles

Christopher Fechisin, Kieran Cooney, Mathi Raja +4 more

Recent work has shown that quantum double models can be used to circumvent the Bravyi-Koenig bound. In particular, this is achieved through code-switching protocols in which non-Pauli stabilizer phases appear as intermediate codes. We introduce the $X\mathcal C^{(k)}_d$ stabilizer formalism, which generalizes the Pauli stabilizer formalism by combining Pauli-$X$ operators with diagonal operators drawn from a fixed level $k$ of the Clifford hierarchy on prime-dimensional qudits. This yields a natural class of beyond-Pauli stabilizer models, including many twisted quantum double phases. We classify a large class of these $X\mathcal C^{(k)}_d$ stabilizer states, showing that they are uniform superpositions over affine-linear subspaces with diagonal phases. In particular, when the stabilizers of a state require operators from level $k$ of the Clifford hierarchy, we show that the diagonal gates required to produce the phases in the wavefunction sit one level higher. We further show that every 2D twisted quantum double ${\cal D}^ω(\mathbb{Z}_p^n)$ with $ω$ a product of type-III cocycles and $p$ an odd prime admits a realization using only Clifford ($k=2$) stabilizers, and we conjecture that phases where $ω$ contains a type-I or type-II cocycle require level-$p$ Clifford-hierarchy stabilizers for $p$-dimensional qudits. Finally, we demonstrate that a pair of qudit toric codes may be deterministically prepared in a logical magic state by measuring $X\mathcal C^{(k)}_d$ stabilizers. Together, these results provide a concrete stabilizer framework for topological codes beyond Pauli stabilizer models and their logical gates.

quant-pharXiv:2610.00464•Oct 2, 2026•0 citations
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.
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 combine the study of resources in measurement-based quantum computation (MBQC) with that of quantum solutions to linear constraint systems (LCS). Contextuality of the input state in MBQC has been identified as a key resource for quantum advantage, and in a stronger form, underlies algebraic relations between (measurement) operators which obey classically unsatisfiable (linear) constraints. Here, we compare these two perspectives on contextuality, and study to what extent they are related. More precisely, we associate a LCS to certain MBQC which exhibit strong forms of state-dependent contextuality, and ask if the measurement operators in such MBQC give rise to state-independent contextuality in the form of quantum solutions of its associated LCS. Our main result rules out such quantum solutions for a large class of MBQC. This both sharpens the distinction between state-dependent and state-independent forms of contextuality, and further generalises results on the non-existence of quantum solutions to LCS in finite odd (prime) dimension.
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.
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.
Galois qudits are qqq-dimensional quantum systems whose choice of Pauli group encodes the arithmetic of some finite field Fq\mathbb{F}_qFq​. They differ from the more familiar modular qudit, which are the same quantum system but whose choice of Pauli group are the clock and shift operators, which encode the arithmetic of integer addition and multiplication modulo qqq. Galois qudits are a useful mathematical construct that allow us to leverage the mathematical tools that are native to the larger qudit while only physically building smaller qudits. In particular, a Galois qudit of dimension q=2sq = 2^sq=2s is exactly the same thing as a collection of sss qubits, not only in its Hilbert space, but also in its Pauli group, and Clifford hierarchy. This formalism has found a lot of utility recently in constructing quantum error-correcting codes over qubits with useful properties. In this review, we build on existing literature to collect and formalise facts and proofs about Galois qudits over binary extension fields. We define them and their Clifford hierarchies, describe what it means to measure their Pauli operators, describe their stabiliser tableaux, formally define qudit-to-qubit mappings, and finally describe quantum Reed-Solomon codes.
Recent work has shown that quantum double models can be used to circumvent the Bravyi-Koenig bound. In particular, this is achieved through code-switching protocols in which non-Pauli stabilizer phases appear as intermediate codes. We introduce the XCd(k)X\mathcal C^{(k)}_dXCd(k)​ stabilizer formalism, which generalizes the Pauli stabilizer formalism by combining Pauli-XXX operators with diagonal operators drawn from a fixed level kkk of the Clifford hierarchy on prime-dimensional qudits. This yields a natural class of beyond-Pauli stabilizer models, including many twisted quantum double phases. We classify a large class of these XCd(k)X\mathcal C^{(k)}_dXCd(k)​ stabilizer states, showing that they are uniform superpositions over affine-linear subspaces with diagonal phases. In particular, when the stabilizers of a state require operators from level kkk of the Clifford hierarchy, we show that the diagonal gates required to produce the phases in the wavefunction sit one level higher. We further show that every 2D twisted quantum double Dω(Zpn){\cal D}^ω(\mathbb{Z}_p^n)Dω(Zpn​) with ωωω a product of type-III cocycles and ppp an odd prime admits a realization using only Clifford (k=2k=2k=2) stabilizers, and we conjecture that phases where ωωω contains a type-I or type-II cocycle require level-ppp Clifford-hierarchy stabilizers for ppp-dimensional qudits. Finally, we demonstrate that a pair of qudit toric codes may be deterministically prepared in a logical magic state by measuring XCd(k)X\mathcal C^{(k)}_dXCd(k)​ stabilizers. Together, these results provide a concrete stabilizer framework for topological codes beyond Pauli stabilizer models and their logical gates.