{"ID":23629744,"CreatedAt":"2026-09-18T07:04:54.147703138Z","UpdatedAt":"2026-09-18T07:04:54.147703138Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.20678","arxiv_id":"2609.20678","title":"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.","short_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-c...","url_abs":"https://arxiv.org/abs/2609.20678","url_pdf":"https://arxiv.org/pdf/2609.20678v1","authors":"[\"Lorenzo Ciardo\",\"Iris Hebbeker\",\"Gideo Joubert\",\"Jana Kreiß\",\"Antoine Mottet\"]","published":"2026-09-17T16:49:26Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.CC\",\"cs.DM\",\"math.OA\",\"quant-ph\"]","methods":"[]","has_code":false}