Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

math.COcs.CCcs.DMmath.OAquant-phSubmitted Sep 17, 2026• Announced Sep 18, 2026• 0 citations
arXivHTMLPDF

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.

Little sign of AI-generated textAI use disclosed
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.

Related papers

Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism — E8 Intelligence Research

Andrew Stewart Caldin

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. Source: http://arxiv.org/abs/2609.20678v1 (arXiv:2609.20678v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 7, 2026•0 citations

Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction

Lorenzo Ciardo, Gideo Joubert, Antoine Mottet

We introduce the concept of quantum polymorphisms to the complexity theory of quantum constraint satisfaction. Via this notion, we build an algebraic framework of reductions between quantum CSPs, and we establish a Galois connection between quantum polymorphism minions and quantum relational constructions. By leveraging a contextuality property of quantum polymorphisms, we fully characterise the existence of commutativity gadgets for relational structures, introduced by Ji as a method for achieving quantum soundness of classical CSP reductions. Prior to our work, only a partial classification was known for a subclass of Boolean languages and for non-Boolean languages meeting specific structural conditions [Culf--Mastel, FOCS'25]. As an application of our framework, we prove that the quantum CSPs parameterised by odd cycles and the quantum CSP expressing quantum satisfiability of Siggers clauses are undecidable.

quant-pharXiv:2511.23445•Dec 1, 2025•5 citations

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

Prem Nigam Kar, David E. Roberson, Tim Seppelt +1 more

Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general, which motivates the study of its relaxations. In the classical setting, Roberson and Seppelt [ICALP'23] characterized the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism in terms of equality of homomorphism counts from an appropriate graph class. The NPA hierarchy, a noncommutative generalization of the Lasserre hierarchy, provides a sequence of semidefinite programming relaxations for quantum isomorphism. In the quantum setting, we show that the feasibility of each level of the NPA hierarchy for quantum isomorphism is equivalent to equality of homomorphism counts from an appropriate class of planar graphs. Combining this characterization with the convergence of the NPA hierarchy, and noting that the union of these classes is the set of all planar graphs, we obtain a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of quantum groups. Moreover, this homomorphism indistinguishability characterization also yields a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.

arXiv:2407.10635•Quantum•Jan 28, 2026•7 citations

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

Prem Nigam Kar, David E. Roberson, Tim Seppelt +1 more

Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over the class of planar graphs. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general. The NPA hierarchy gives a sequence of semidefinite programming relaxations of quantum isomorphism. Recently, Roberson and Seppelt [ICALP'23] obtained a homomorphism indistinguishability characterization of the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism. We prove a quantum analogue of this result by showing that each level of the NPA hierarchy of SDP relaxations for quantum isomorphism of graphs is equivalent to homomorphism indistinguishability over an appropriate class of planar graphs. By combining the convergence of the NPA hierarchy with the fact that the union of these graph classes is the set of all planar graphs, we are able to give a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of the theory of quantum groups. This homomorphism indistinguishability characterization also allows us to give a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.

•Jan 1, 2025•7 citations

Quantum polymorphism characterisation of commutativity gadgets in all quantum models

Eric Culf, Josse van Dobben de Bruyn, Peter Zeman

Commutativity gadgets provide a technique for lifting classical reductions between constraint satisfaction problems to quantum-sound reductions between the corresponding nonlocal games. We develop a general framework for commutativity gadgets in the setting of quantum homomorphisms between finite relational structures. Building on the notion of quantum homomorphism spaces, we introduce a uniform notion of commutativity gadget capturing the finite-dimensional quantum, quantum approximate, and commuting-operator models. In the robust setting, we use the weighted-algebra formalism for approximate quantum homomorphisms to capture corresponding notions of robust commutativity gadgets. Our main results characterize both non-robust and robust commutativity gadgets purely in terms of quantum polymorphism spaces: in any model, existence of a commutativity gadget is equivalent to the collapse of the corresponding quantum polymorphisms to classical ones at arity $|A|^2$, and robust gadgets are characterized by stable commutativity of the appropriate weighted polymorphism algebra. We use this characterisation to show relations between the classes of commutativity gadget, notably that existence of a robust commutativity gadget is equivalent to the existence of a corresponding non-robust one. Finally, we prove that quantum polymorphisms of complete graphs $K_n$ have a very special structure, wherein the noncommutative behaviour only comes from the quantum permutation group $S_n^+$. Combining this with techniques from combinatorial group theory, we construct separations between commutativity-gadget classes: we exhibit a relational structure admitting a finite-dimensional commutativity gadget but no quantum approximate gadget, and, conditional on the existence of a non-hyperlinear group, a structure admitting a quantum approximate commutativity gadget but no commuting-operator gadget.

quant-pharXiv:2604.01408•Apr 3, 2026•2 citations

The Quantum Homomorphism Orders are Universal

Yangjing Long

Quantum graph homomorphisms, introduced by Mančinska and Roberson, form a natural quantum relaxation of classical graph homomorphisms. Since this relaxation may create new comparabilities, it could in principle collapse antichains and other order-theoretic configurations. We prove that this does not happen: the quantum homomorphism quasi-order of finite directed graphs is countably universal, and the quantum homomorphism quasi-order of finite planar graphs of maximum degree at most $7$ is also countably universal. Consequently, the same universality holds for finite undirected graphs and for the corresponding quotient partial orders. The result is constructive for finite patterns. Given any finite poset $P$, we explicitly construct finite planar graphs $G_p$, $p\in P$, with $Δ(G_p)\le 7$, such that \[ p\le_P q \quad\Longleftrightarrow\quad G_p\toq G_q. \] For directed graphs, the proof uses disjoint unions of clockwise directed cycles, where quantum and classical homomorphisms coincide. For undirected graphs, the main ingredient is a finite ordered indicator whose terminals are quantum endpoint-forcing. This gives a quantum analogue of the classical ordered-indicator method: the classical endpoint-image condition is replaced by the projection-level vanishing condition \[ F_{a,p}F_{b,q}=0 \] for every illegal ordered terminal pair. The fixed indicator encodes directed-cycle constructions inside planar bounded-degree graphs without creating extra quantum homomorphisms.

arXiv:2605.19543•May 19, 2026•0 citations
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, qqq-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.
The paper studies which fixed target graphs GGG make deciding the existence of a finite-dimensional quantum homomorphism F→GF\to GF→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 RE\mathsf{RE}RE-completeness for Kneser graphs KG(n,k)KG(n,k)KG(n,k) and qqq-Kneser graphs KGq(n,k)KG_q(n,k)KGq​(n,k) with n>2k≥2n>2k\geq2n>2k≥2; complements of Johnson and Grassmann graphs with n>2k≥4n>2k\geq4n>2k≥4; and complements of Hamming graphs H(d,q)‾\overline{H(d,q)}H(d,q)​ with d≥2d\geq2d≥2, q≥3q\geq3q≥3. For Grassmann families, qqq is a prime power. Odd graphs On=KG(2n−1,n−1)O_n=KG(2n-1,n-1)On​=KG(2n−1,n−1) also receive RE\mathsf{RE}RE-completeness and commutativity gadgets in the non-oracular model, resolving a previously posed question.
The method analyses equality in Roberson’s bound αp(G)≤ϑ−(G)\alpha_p(G)\leq\vartheta^-(G)αp​(G)≤ϑ−(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 RE\mathsf{RE}RE-complete targets have contextual quantum polymorphisms and no commutativity gadget, including a core example discussed in the paper.
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, qqq-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. Source: http://arxiv.org/abs/2609.20678v1 (arXiv:2609.20678v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
We introduce the concept of quantum polymorphisms to the complexity theory of quantum constraint satisfaction. Via this notion, we build an algebraic framework of reductions between quantum CSPs, and we establish a Galois connection between quantum polymorphism minions and quantum relational constructions. By leveraging a contextuality property of quantum polymorphisms, we fully characterise the existence of commutativity gadgets for relational structures, introduced by Ji as a method for achieving quantum soundness of classical CSP reductions. Prior to our work, only a partial classification was known for a subclass of Boolean languages and for non-Boolean languages meeting specific structural conditions [Culf--Mastel, FOCS'25]. As an application of our framework, we prove that the quantum CSPs parameterised by odd cycles and the quantum CSP expressing quantum satisfiability of Siggers clauses are undecidable.
Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general, which motivates the study of its relaxations. In the classical setting, Roberson and Seppelt [ICALP'23] characterized the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism in terms of equality of homomorphism counts from an appropriate graph class. The NPA hierarchy, a noncommutative generalization of the Lasserre hierarchy, provides a sequence of semidefinite programming relaxations for quantum isomorphism. In the quantum setting, we show that the feasibility of each level of the NPA hierarchy for quantum isomorphism is equivalent to equality of homomorphism counts from an appropriate class of planar graphs. Combining this characterization with the convergence of the NPA hierarchy, and noting that the union of these classes is the set of all planar graphs, we obtain a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of quantum groups. Moreover, this homomorphism indistinguishability characterization also yields a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.
Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over the class of planar graphs. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general. The NPA hierarchy gives a sequence of semidefinite programming relaxations of quantum isomorphism. Recently, Roberson and Seppelt [ICALP'23] obtained a homomorphism indistinguishability characterization of the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism. We prove a quantum analogue of this result by showing that each level of the NPA hierarchy of SDP relaxations for quantum isomorphism of graphs is equivalent to homomorphism indistinguishability over an appropriate class of planar graphs. By combining the convergence of the NPA hierarchy with the fact that the union of these graph classes is the set of all planar graphs, we are able to give a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of the theory of quantum groups. This homomorphism indistinguishability characterization also allows us to give a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.
Commutativity gadgets provide a technique for lifting classical reductions between constraint satisfaction problems to quantum-sound reductions between the corresponding nonlocal games. We develop a general framework for commutativity gadgets in the setting of quantum homomorphisms between finite relational structures. Building on the notion of quantum homomorphism spaces, we introduce a uniform notion of commutativity gadget capturing the finite-dimensional quantum, quantum approximate, and commuting-operator models. In the robust setting, we use the weighted-algebra formalism for approximate quantum homomorphisms to capture corresponding notions of robust commutativity gadgets. Our main results characterize both non-robust and robust commutativity gadgets purely in terms of quantum polymorphism spaces: in any model, existence of a commutativity gadget is equivalent to the collapse of the corresponding quantum polymorphisms to classical ones at arity ∣A∣2|A|^2∣A∣2, and robust gadgets are characterized by stable commutativity of the appropriate weighted polymorphism algebra. We use this characterisation to show relations between the classes of commutativity gadget, notably that existence of a robust commutativity gadget is equivalent to the existence of a corresponding non-robust one. Finally, we prove that quantum polymorphisms of complete graphs KnK_nKn​ have a very special structure, wherein the noncommutative behaviour only comes from the quantum permutation group Sn+S_n^+Sn+​. Combining this with techniques from combinatorial group theory, we construct separations between commutativity-gadget classes: we exhibit a relational structure admitting a finite-dimensional commutativity gadget but no quantum approximate gadget, and, conditional on the existence of a non-hyperlinear group, a structure admitting a quantum approximate commutativity gadget but no commuting-operator gadget.
Quantum graph homomorphisms, introduced by Mančinska and Roberson, form a natural quantum relaxation of classical graph homomorphisms. Since this relaxation may create new comparabilities, it could in principle collapse antichains and other order-theoretic configurations. We prove that this does not happen: the quantum homomorphism quasi-order of finite directed graphs is countably universal, and the quantum homomorphism quasi-order of finite planar graphs of maximum degree at most 777 is also countably universal. Consequently, the same universality holds for finite undirected graphs and for the corresponding quotient partial orders. The result is constructive for finite patterns. Given any finite poset PPP, we explicitly construct finite planar graphs GpG_pGp​, p∈Pp\in Pp∈P, with Δ(Gp)≤7Δ(G_p)\le 7Δ(Gp​)≤7, such that \[ p\le_P q \quad\Longleftrightarrow\quad G_p\toq G_q. \] For directed graphs, the proof uses disjoint unions of clockwise directed cycles, where quantum and classical homomorphisms coincide. For undirected graphs, the main ingredient is a finite ordered indicator whose terminals are quantum endpoint-forcing. This gives a quantum analogue of the classical ordered-indicator method: the classical endpoint-image condition is replaced by the projection-level vanishing condition Fa,pFb,q=0 F_{a,p}F_{b,q}=0 Fa,p​Fb,q​=0 for every illegal ordered terminal pair. The fixed indicator encodes directed-cycle constructions inside planar bounded-degree graphs without creating extra quantum homomorphisms.