A complete classification of the existence of finite-dimensional quantum solutions to inconsistent linear constraint systems
Abstract
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 ℤ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 ℤn with quantum solutions in all dimensions d and for all 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≥ 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≥ 3 and p| d.
Related
- Existence and classification of solutions for singular 1-Laplacian equations with gradient terms
- Global Existence and Large-Time Behavior of Strong Solutions to the Two-Dimensional Compressible Nematic Liquid Crystal Flows with Large Initial Data and Vacuum
- Global Existence and Large-Time Asymptotic Behavior of Strong Solutions to the Two-Dimensional Nematic Liquid Crystal Flows with Large Initial Data and Vacuum
- A Necessary and Sufficient Condition for the Existence of Global Smooth Solutions to the One-Dimensional Inviscid Burgers-Vlasov System
- Local and Global Existence of Strong Solutions to the One-Dimensional Compressible Navier--Stokes Equations with General Pressure Law
BibTeX
@misc{frembs2026complete,
title = {{A complete classification of the existence of finite-dimensional quantum solutions to inconsistent linear constraint systems}},
author = {Markus Frembs},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16490},
eprint = {2609.16490},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16490},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A complete classification of the existence of finite-dimensional quantum solutions to inconsistent linear constraint systems
AU - Markus Frembs
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.16490
UR - https://arxiv.org/abs/2609.16490
AB - 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 ℤ_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 ℤ_n with quantum solutions in all dimensions d and for all 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≥ 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≥ 3 and p| d.
ER -