Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism
math.CO, cs.CC, cs.DM, math.OA, quant-ph
Submitted: 2026-09-17
Updated: 2026-09-17
License: http://creativecommons.org/licenses/by/4.0/
The gist: We prove RE-completeness of the quantum homomorphism problem parameterised by families of graphs derived from the classic metric association schemes.
Terminology
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.
Sources
- Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
- Existence and nonexistence of commutativity gadgets for entangled CSPs
- Binary Constraint System Games and Locally Commutative Reductions
- Spectral upper bound on the quantum k-independence number of a graph
Related papers
- Exponential random graph models with soft clique constraints
- Exact Enumeration of Phylogenetic Networks: The Tree-Child, Reticulation-Visible and Orchard Hierarchy
- Arithmetic Circuits and Neural Networks for Regular Matroids
- On composition and decomposition operations for vector spaces, graphs and matroids
- Sedentary quantum walks on bipartite and planar graphs
- An introduction to local differential privacy protocols using block designs