arXiv:2609.20678
Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism
Lorenzo Ciardo, Iris Hebbeker, Gideo Joubert, Jana Kreiß, Antoine Mottet
Abstract
We prove RE-completeness of the quantum homomorphism problem parameterised by families of graphs derived from the classic metric association schemes. These include Kneser graphs, $q$-Kneser graphs, and the complements of Johnson, Grassmann, and Hamming graphs. Our proof develops a spectral method for establishing non-contextuality of quantum polymorphisms. It combines an equality analysis of Roberson's bound on the projective packing number in terms of Schrijver's theta with a structural argument inspired by Erdős-Ko-Rado theory.
AI Summary
The paper studies which fixed target graphs $G$ make deciding the existence of a finite-dimensional quantum homomorphism $F\to G$ undecidable. It primarily uses the **oracular model**, requiring measurements at adjacent input vertices to commute, and advances the proposed quantum analogue of the Hell–Nešetřil classification. It proves $\mathsf{RE}$-completeness for Kneser graphs $KG(n,k)$ and $q$-Kneser graphs $KG_q(n,k)$ with $n>2k\geq2$; complements of Johnson and Grassmann graphs with $n>2k\geq4$; and complements of Hamming graphs $\overline{H(d,q)}$ with $d\geq2$, $q\geq3$. For Grassmann families, $q$ is a prime power. Odd graphs $O_n=KG(2n-1,n-1)$ also receive $\mathsf{RE}$-completeness and commutativity gadgets in the non-oracular model, resolving a previously posed question. The method analyses equality in Roberson’s bound $\alpha_p(G)\leq\vartheta^-(G)$. Optimal projective packings are forced into the kernel of an optimal Schrijver certificate. A disjointness representation with suitable kernel rigidity across categorical powers and additional structural conditions then forces every quantum polymorphism to be globally commuting. Existing polymorphism machinery converts this into commutativity gadgets and hardness. Within association schemes, Schrijver rigidity is shown equivalent to a linear-programming version based on Delsarte’s bound, with explicit spectral certificates for the stated families. The criterion is sufficient, not a classification. Odd cycles of length at least five have commutativity gadgets but fail its tightness requirement. Conversely, some $\mathsf{RE}$-complete targets have contextual quantum polymorphisms and no commutativity gadget, including a core example discussed in the paper.
the authors used ChatGPT to assist with literature search, exploration and checking of mathematical arguments, and drafting and revision of the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.