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:2601.11367

No quantum solutions to linear constraint systems from monomial measurement-based quantum computation in odd prime dimension

Markus Frembs, Cihan Okay, Ho Yiu Chung

quant-phmath-phSubmitted Jan 16, 2026• Announced Jan 19, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

Comments
12+7 pages, 2 figures; second part to arXiv:2209.14018v2; comments welcome

Related papers

Contextuality as a resource for measurement-based quantum computation beyond qubits

Markus Frembs, Sam Roberts, Stephen D. Bartlett

Contextuality—the obstruction to describing quantum mechanics in a classical statistical way—has been proposed as a resource that powers quantum computing. The measurement-based model provides a concrete manifestation of contextuality as a computational resource, as follows. If local measurements on a multi-qubit state can be used to evaluate nonlinear boolean functions with only linear control processing, then this computation constitutes a proof of strong contextuality—the possible local measurement outcomes cannot all be pre-assigned. However, this connection is restricted to the special case when the local measured systems are qubits , which have unusual properties from the perspective of contextuality. A single qubit cannot allow for a proof of contextuality, unlike higher-dimensional systems, and multiple qubits can allow for state-independent contextuality with only Pauli observables, again unlike higher-dimensional generalisations. Here we identify precisely that strong non-locality is necessary in a qudit measurement-based computation (MBC) that evaluates high-degree polynomial functions with only linear control. We introduce the concept of local universality , which places a bound on the space of output functions accessible under the constraint of single-qudit measurements. Thus, the partition of a physical system into subsystems plays a crucial role for the increase in computational power. A prominent feature of our setting is that the enabling resources for qubit and qudit MBC are of the same underlying nature, avoiding the pathologies associated with qubit contextuality.

arXiv:1804.07364•New Journal of Physics•Sep 24, 2018•53 citations

Contextuality as a Resource for Models of Quantum Computation with Qubits

Juan Bermejo-Vega, Nicolas Delfosse, Dan E. Browne +2 more

A central question in quantum computation is to identify the resources that are responsible for quantum speed-up. Quantum contextuality has been recently shown to be a resource for quantum computation with magic states for odd-prime dimensional qudits and two-dimensional systems with real wave functions. The phenomenon of state-independent contextuality poses a priori an obstruction to characterizing the case of regular qubits, the fundamental building block of quantum computation. Here, we establish contextuality of magic states as a necessary resource for a large class of quantum computation schemes on qubits. We illustrate our result with a concrete scheme related to measurement-based quantum computation.

arXiv:1610.08529•Physical Review Letters•Sep 21, 2017•160 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

Algebraic paradoxes in adaptive quantum computation

Samson Abramsky, Rui Soares Barbosa, Carmen Constantin +1 more

Measurement-based quantum computation (MBQC) is a universal model of quantum computation whose full power requires adaptivity. Contextuality is known to power quantum advantage in MBQC, yet it has resisted algebraic analysis in the adaptive setting. We show that if an adaptive $\mathbb{Z}_2$-linear measurement-based quantum computing protocol deterministically computes a non-affine Boolean function, then the underlying quantum resource satisfies an inconsistent set of linear equations. This witnesses an algebraic form of strong contextuality generalising Mermin's All-versus-Nothing arguments. Such algebraic contextuality can be detected cohomologically, resolving an open question posed by Raussendorf, who had established cohomological witnesses of contextuality for non-adaptive protocols, but left the adaptive case open. We prove this result constructively: we model adaptive measurement protocols as ordinary measurements on a larger scenario of tree-like measurements, and explicitly build the inconsistent equations inductively.

quant-pharXiv:2607.26157•Jul 30, 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•6 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•4 citations
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.
Contextuality—the obstruction to describing quantum mechanics in a classical statistical way—has been proposed as a resource that powers quantum computing. The measurement-based model provides a concrete manifestation of contextuality as a computational resource, as follows. If local measurements on a multi-qubit state can be used to evaluate nonlinear boolean functions with only linear control processing, then this computation constitutes a proof of strong contextuality—the possible local measurement outcomes cannot all be pre-assigned. However, this connection is restricted to the special case when the local measured systems are qubits , which have unusual properties from the perspective of contextuality. A single qubit cannot allow for a proof of contextuality, unlike higher-dimensional systems, and multiple qubits can allow for state-independent contextuality with only Pauli observables, again unlike higher-dimensional generalisations. Here we identify precisely that strong non-locality is necessary in a qudit measurement-based computation (MBC) that evaluates high-degree polynomial functions with only linear control. We introduce the concept of local universality , which places a bound on the space of output functions accessible under the constraint of single-qudit measurements. Thus, the partition of a physical system into subsystems plays a crucial role for the increase in computational power. A prominent feature of our setting is that the enabling resources for qubit and qudit MBC are of the same underlying nature, avoiding the pathologies associated with qubit contextuality.
A central question in quantum computation is to identify the resources that are responsible for quantum speed-up. Quantum contextuality has been recently shown to be a resource for quantum computation with magic states for odd-prime dimensional qudits and two-dimensional systems with real wave functions. The phenomenon of state-independent contextuality poses a priori an obstruction to characterizing the case of regular qubits, the fundamental building block of quantum computation. Here, we establish contextuality of magic states as a necessary resource for a large class of quantum computation schemes on qubits. We illustrate our result with a concrete scheme related to measurement-based quantum computation.
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.
Measurement-based quantum computation (MBQC) is a universal model of quantum computation whose full power requires adaptivity. Contextuality is known to power quantum advantage in MBQC, yet it has resisted algebraic analysis in the adaptive setting. We show that if an adaptive Z2\mathbb{Z}_2Z2​-linear measurement-based quantum computing protocol deterministically computes a non-affine Boolean function, then the underlying quantum resource satisfies an inconsistent set of linear equations. This witnesses an algebraic form of strong contextuality generalising Mermin's All-versus-Nothing arguments. Such algebraic contextuality can be detected cohomologically, resolving an open question posed by Raussendorf, who had established cohomological witnesses of contextuality for non-adaptive protocols, but left the adaptive case open. We prove this result constructively: we model adaptive measurement protocols as ordinary measurements on a larger scenario of tree-like measurements, and explicitly build the inconsistent equations inductively.
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.
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.