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

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.

Combinatorics (math.CO); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Operator Algebras (math.OA); Quantum Physics (quant-ph)

arXiv:2609.20678 [math.CO]

(or arXiv:2609.20678v1 [math.CO] for this version)

https://doi.org/10.48550/arXiv.2609.20678 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.