Quantum graph homomorphism problem proven undecidable for key graph families
Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism
Computational ComplexityDiscrete Mathematics
Summary
Some problems about assigning one graph’s points to another’s using quantum rules are super hard to solve–so hard that no computer can always decide them. The authors show this undecidability for special graphs often studied in math and computer science, like Kneser and Johnson graphs. They do this by blending tools from quantum theory, graph structure, and combinatorics. Their method includes analyzing certain numerical bounds called the theta numbers and using ideas from a field studying sets with special overlap properties.
What this means in practice
- •For quantum algorithm designers: Identify which quantum graph homomorphism problems cannot be resolved algorithmically, guiding focus toward tractable problem classes.
- •For network security analysts: Recognize hard-to-decide quantum constraints in network mapping problems, helping avoid relying on undecidable checks in protocol design.
A theory result. No direct application yet.
Authors
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.