A complete classification of the existence of finite-dimensional quantum solutions to inconsistent linear constraint systems

Technical Summary: Classification of Finite-Dimensional Quantum Solutions to Inconsistent Linear Constraint Systems

Problem Statement
Linear constraint systems (LCS) provide an algebraic framework for nonlocal games and state-independent contextuality. An LCS is defined over a ring $\mathbb{Z}_n$ (or a finite field $\mathbb{F}_q$) as a system of linear equations $Ax = b$. A system is classically unsatisfiable if no vector $x \in \mathbb{Z}_n^N$ satisfies the equations. The central problem addressed is the existence of finite-dimensional quantum solutions to such inconsistent systems. A quantum solution consists of unitary operators $\{X_i\}$ on a Hilbert space $\mathcal{H}$ of dimension $d$ satisfying the same algebraic relations as the classical variables, but with the right-hand side scaled by a root of unity $\zeta_n^b$.

Prior to this work, it was well-established that such "quantum-classical gaps" exist in the binary case ($n=2$) via the Mermin–Peres square and Mermin's pentagram, utilizing Pauli operators. However, for odd prime moduli ($n=p$), a series of no-go results suggested that no such finite-dimensional gaps exist for natural generalizations of Pauli-based constructions (including Clifford and monomial unitaries). This led to a conjecture that no classically unsatisfiable LCS over $\mathbb{Z}_n$ (for odd $n$) admits a finite-dimensional quantum solution. This paper aims to resolve the existence problem for arbitrary $n$ and $d$, specifically refuting the conjecture for odd moduli and providing a complete classification.

Methodology
The author employs a multi-faceted approach combining algebraic obstruction theory, geometric combinatorics, and group representation theory:

1. Tensor Product Analysis: The paper first analyzes solutions constructed as tensor products of local unitaries. Using determinant arguments and commutation relations, it proves that for odd moduli $n$, a global obstruction (classical unsatisfiability) cannot arise solely from tensoring locally unobstructed factors. This isolates the "parity mechanism" unique to $n=2$ (where reordering phases can yield non-trivial fourth roots) as the reason for the success of binary Pauli constructions, explaining why they fail to generalize directly to odd moduli.

2. Ray-Context Arrangements: To bypass the limitations of tensor-product constructions, the paper shifts focus to LCS associated with ray-context arrangements. These are finite sets of rank-one projectors $\{P_v\}$ in $\mathbb{C}^d$ and a set of contexts (maximal orthogonal bases) $\mathcal{C}$.

   • Automatic Quantum Solvability: For any such arrangement, the operators $X_v = \zeta_n^{P_v}$ automatically satisfy the LCS constraints over $\mathbb{Z}_n$.
   • Classical Obstruction: The problem reduces to finding arrangements where the associated incidence relations are classically inconsistent. This is characterized by the existence of an incidence cycle (a linear combination of contexts) that sums to zero on the variables but non-zero on the constraints.

3. Frame Functions and Group Cohomology: The existence of quantum solutions is linked to the non-existence of $\mathbb{Z}_n$-valued frame functions of weight 1. The paper utilizes group-valued frame functions and group cohomology ($H^1(G, \ker A)$) to analyze symmetric arrangements and determine conditions under which classical solutions can be symmetrized or obstructed.

4. Explicit Constructions:

   • Harding–Jager–Smith (HJS) Extension: The paper revisits and extends a 2005 construction by Harding, Jager, and Smith, providing explicit ray-context arrangements for dimensions $d = kn$($k \ge 2$).
   • Prime Dimension $d=p$: For the minimal case $d=p$ (where $p$ is an odd prime), the author constructs specific arrangements using the projective hyperoctahedral group $G_p$. This involves "transporting" rays with zero coordinates to the coordinate orbit via context chains and exploiting the differing $p$-divisibility of stabilizer subgroups for diagonal versus coordinate rays.
   • Dimension $d=3$: A specific 43-ray, 31-context arrangement in $\mathbb{C}^3$ is constructed using the signed permutation group and vectors in the ring $\mathbb{Z}[\sqrt{-2}]$, closely related to Kochen–Specker sets.

Key Contributions and Results

1. Refutation of the Odd-Modulus Conjecture: The paper definitively refutes the conjecture that no finite-dimensional quantum-classical gaps exist for LCS over $\mathbb{Z}_n$ with $n$ odd. It demonstrates that such systems exist for all $n$ and $d$ satisfying specific conditions.

2. Complete Classification Theorem (Theorem 6):
   The paper establishes that a linear constraint system over $\mathbb{Z}_n$ with no classical solution but admitting a $d$-dimensional quantum solution exists if and only if:
   $$\gcd(n, d) > 1 \quad \text{and} \quad d \ge 3$$

   • Necessity: If $\gcd(n, d) = 1$, the determinant condition forces a classical solution. If $d=2$, commuting unitaries share a common eigenbasis, allowing a classical solution.
   • Sufficiency: Explicit constructions are provided for all valid pairs $(n, d)$.
     • For $d = kn$($k \ge 2$), the HJS construction is used.
     • For $d = p$ (prime), explicit constructions are given for $p \ge 5$ (using $G_p$ orbits) and $p=3$ (using the 43-ray arrangement).
     • For composite $d$, the results are extended via tensoring or lifting from prime factors.

3. Finite Field Generalization (Theorem 8): The results are extended to arbitrary finite fields $\mathbb{F}_q$ (where $q = p^f$). A quantum-classical gap exists over $\mathbb{F}_q$ if and only if $p \mid d$ and $d \ge 3$. This distinguishes the additive group structure of $\mathbb{F}_q$ from the cyclic group $\mathbb{Z}_q$.

4. Characterization of Frame Functions (Theorem 7): The paper refines the characterization of $\mathbb{Z}_n$-valued frame functions. It proves that for $d$ sufficiently large relative to the prime factors of $n$, all such frame functions are constant. Specifically, the set of possible weights for a frame function on $\mathbb{C}^d$ is exactly $\gcd(n, d)\mathbb{Z}_n$.

Significance
The paper provides a "complete classification" of the existence problem for finite-dimensional quantum solutions to inconsistent linear constraint systems. By moving beyond the restrictive class of Pauli and Clifford operators to general ray-context arrangements, the author resolves a long-standing open question regarding the existence of quantum-classical gaps in odd dimensions.

The work clarifies the structural distinction between binary ($n=2$) and odd-modulus ($n$ odd) cases: the binary case relies on a specific phase-reordering mechanism (the "parity mechanism") that does not generalize to tensor products in odd dimensions. However, by utilizing global geometric obstructions in ray-context arrangements, the paper demonstrates that quantum advantage in the form of perfect strategies for inconsistent linear systems is a generic phenomenon whenever the dimension $d$ and modulus $n$ share a common factor and $d \ge 3$. This unifies the understanding of contextuality across different algebraic settings and provides explicit, constructive examples for all valid parameter regimes.