Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism

Technical Summary: Schrijver–Delsarte Rigidity in Association Schemes and Undecidability of Quantum Graph Homomorphism

Problem Statement
The paper addresses the computational complexity of the quantum graph homomorphism problem, denoted $\text{CSP}_q(G')$. Given a fixed target graph $G'$, the problem asks whether an input graph $G$ admits a quantum homomorphism to $G'$. While the classical version of this problem is well-understood (NP-complete for non-bipartite targets, polynomial for bipartite), the quantum landscape is less resolved. It is known that for unrestricted quantum strategies, the problem is RE-complete (recursively enumerable complete) due to the $MIP^* = RE$ theorem. However, establishing RE-completeness for specific, non-uniform target graphs requires proving the existence of "commutativity gadgets"—structures that force quantum strategies to behave classically (non-contextually) or allow for reductions from known hard problems.

The authors focus on a systematic approach to classify the complexity of $\text{CSP}_q(G)$ for specific families of graphs derived from association schemes, including Kneser graphs, $q$-Kneser graphs, and complements of Johnson, Grassmann, and Hamming graphs. The central challenge is to determine when these graphs admit commutativity gadgets, which, according to the theory of quantum polymorphisms, is equivalent to proving that all quantum polymorphisms of the graph are non-contextual.

Methodology
The paper develops a spectral method to establish the non-contextuality of quantum polymorphisms. The approach combines three main theoretical pillars:

1. Schrijver's Theta and Projective Packings: The authors utilize Schrijver's parameter $\vartheta^-(G)$, a strengthening of the Lovász theta function, which upper bounds the independence number $\alpha(G)$. They leverage Roberson's result that $\vartheta^-(G)$ also bounds the projective packing number $\alpha_p(G)$, which in turn bounds the quantum independence number $\alpha_q(G)$. The core of their method relies on the case where these bounds are tight ($\alpha(G) = \alpha_p(G) = \vartheta^-(G)$).
2. Rigidity and Equality Analysis: When the bound is tight, the authors analyze the structure of the "certificate" matrices witnessing this equality. They prove that if a graph admits a specific type of "Schrijver-rigid" representation, the projectors defining any perfect quantum strategy must lie in a restricted subspace (the kernel of the certificate). This restriction forces linear identities among the projectors.
3. Tame Disjointness Representations and Association Schemes: To translate the spectral condition into a checkable criterion, the authors introduce "tame disjointness representations." These are injective maps from graph vertices to sets of features such that adjacent vertices map to disjoint sets. They define a representation as Schrijver-rigid if the kernel of the optimal Schrijver certificate coincides with the incidence space of the representation.
   • Crucially, for graphs derived from association schemes (Johnson, Grassmann, Hamming), the authors prove that Schrijver-rigidity is equivalent to Delsarte-rigidity. Delsarte-rigidity is a condition formulated entirely within the linear programming (LP) framework of the Bose–Mesner algebra, making it computationally verifiable given the scheme's eigenvalue matrix.
   • They further show that if a graph has a "tame" Schrijver-rigid representation, the linear identities derived from the spectral constraints force all projectors in a quantum polymorphism to commute (non-contextuality).

Key Contributions and Results
The primary contribution is the proof of RE-completeness for the quantum homomorphism problem parameterized by several families of graphs derived from classic metric association schemes.

• Main Theorem (Theorem 1.1): The authors prove that determining whether an input graph admits a quantum homomorphism to any of the following graphs is RE-complete:

  • Kneser graphs $KG(n, k)$ with $n > 2k \ge 2$.
  • Complements of Johnson graphs $\overline{J(n, k)}$ with $n > 2k \ge 4$.
  • $q$-Kneser graphs $KG_q(n, k)$ with $n > 2k \ge 2$ and $q$ a prime power.
  • Complements of Grassmann graphs $\overline{J_q(n, k)}$ with $n > 2k \ge 4$ and $q$ a prime power.
  • Complements of Hamming graphs $\overline{H(d, q)}$ with $d \ge 2$ and $q \ge 3$.

• Resolution of Open Questions: This result settles the complexity question for "odd graphs" ($O_n = KG(2n-1, n-1)$), a class of graphs for which the existence of commutativity gadgets was previously unresolved. The authors establish RE-completeness for these graphs in both the oracular and non-oracular settings.

• Technical Framework: The paper establishes a bridge between spectral graph theory (Schrijver's bound) and the algebraic theory of association schemes (Delsarte's LP bound). It demonstrates that for these symmetric structures, the complex SDP conditions required for non-contextuality can be reduced to checking LP conditions on the eigenvalues of the scheme.

Significance and Claims
The paper claims to make significant progress toward a "quantum Hell–Nešetřil classification," which aims to dichotomize graph homomorphism problems into those solvable in polynomial time and those that are RE-complete. By providing a spectral criterion (Schrijver-rigidity) that guarantees RE-completeness, the authors offer a systematic tool for analyzing new graph families.

However, the authors are modest about the scope of their method. They explicitly state that their spectral approach does not capture the entire landscape of RE-complete problems. They provide counterexamples:

• Some graphs (like the diamond graph or the Moser spindle) are RE-complete but do not admit commutativity gadgets (and thus fail the non-contextuality condition).
• Other graphs (like odd cycles of length $\ge 5$) admit commutativity gadgets but fail the spectral criterion because Schrijver's bound is not tight on them.

Consequently, the authors conclude that a full classification will likely require combining their spectral arguments with combinatorial methods (such as contextuality bifurcations) rather than relying on spectral rigidity alone. The work does not propose new experimental protocols but rather provides a rigorous theoretical framework for understanding the computational power of entanglement in specific graph homomorphism games.