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:2605.19543

The Quantum Homomorphism Orders are Universal

Yangjing Long

Published May 19, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2605.19543

Related papers

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•1 citation

Quantum graphs of homomorphisms

Andre Kornell, Bert Lindenhovius

We introduce a category $\mathsf{qGph}$ of quantum graphs, whose definition is motivated entirely from noncommutative geometry. For all quantum graphs $G$ and $H$ in $\mathsf{qGph}$, we then construct a quantum graph $[G,H]$ of homomorphisms from $G$ to $H$, making $\mathsf{qGph}$ a closed symmetric monoidal category. We prove that for all finite graphs $G$ and $H$, the quantum graph $[G,H]$ is nonempty iff the $(G,H)$-homomorphism game has a winning quantum strategy, directly generalizing the classical case. The finite quantum graphs in $\mathsf{qGph}$ are tracial, real, and self-adjoint, and the morphisms between them are CP morphisms that are adjoint to a unital $*$-homomorphism. We prove that Weaver's two notions of a CP morphism coincide in this context. We also include a short proof that every finite reflexive quantum graph is the confusability quantum graph of a quantum channel.

quant-pharXiv:2601.09685•Jan 15, 2026•0 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•0 citations

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

Lorenzo Ciardo, Iris Hebbeker, Gideo Joubert +2 more

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.

math.COCross-listedarXiv:2609.20678•Sep 18, 2026•0 citations

Quantum Property Testing for Bounded-Degree Directed Graphs

Pan Peng, Jingyu Wu

We study quantum property testing of directed graphs whose maximum in-degree and out-degree are bounded by a fixed constant $d$. For a proximity parameter $\varepsilon$, we prove that every property testable with $O_{\varepsilon,d}(1)$ quantum queries in the bidirectional model, where both incoming and outgoing neighbors are accessible, can also be tested in the quantum unidirectional model, where only outgoing neighbors are accessible, using $n^{1/2-Ω_{\varepsilon,d}(1)}$ queries. This gives an almost quadratic quantum speedup over the best known generic classical transformation. Our proof has two main ingredients. First, we show that, in the bidirectional model for bounded-degree digraphs, the class of properties testable with constantly many classical queries coincides with the class testable with constantly many quantum queries. Second, we give a transformation from classical bidirectional testers to quantum unidirectional testers by designing a quantum unidirectional algorithm for estimating the frequency vector of constant-radius rooted discs. The algorithm combines quantum counting and Grover search with a correction procedure that removes false local appearances of smaller disc types inside larger neighborhoods. We further show that this transformation is essentially tight. For every sufficiently small fixed $\varepsilon>0$, there is a degree bound $d=d(\varepsilon)$ and an explicit property $P_\varepsilon$ for $d$-bounded-degree digraphs that is $\varepsilon$-testable with $O_\varepsilon(1)$ classical, and hence quantum, bidirectional queries, but requires $ \widetildeΩ_\varepsilon \left(n^{1/2-f'(\varepsilon)}\right) $ quantum queries in the unidirectional model, where $f'(\varepsilon)\to 0$ as $\varepsilon\to 0$.

quant-pharXiv:2604.07954•Apr 10, 2026•0 citations

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups

Jin‐Yi Cai, Ashwin Maran, Ben Young

We study the complexity of counting (weighted) planar graph homomorphism problem $\tt{Pl\text{-}GH}(M)$ parametrized by an arbitrary symmetric non-negative real valued matrix $M$. For matrices with pairwise distinct diagonal values, we prove a complete dichotomy theorem: $\tt{Pl\text{-}GH}(M)$ is either polynomial-time tractable, or $\#$P-hard, according to a simple criterion. More generally, we obtain a dichotomy whenever every vertex pair of the graph represented by $M$ can be separated using some planar edge gadget. A key question in proving complexity dichotomies in the planar setting is the expressive power of planar edge gadgets. We build on the framework of Mančinska and Roberson to establish links between \textit{planar} edge gadgets and the theory of the \textit{quantum automorphism group} $\tt{Qut}(M)$. We show that planar edge gadgets that can separate vertex pairs of $M$ exist precisely when $\tt{Qut}(M)$ is \emph{trivial}, and prove that the problem of whether $\tt{Qut}(M)$ is trivial is undecidable. These results delineate the frontier for planar homomorphism counting problems and uncover intrinsic barriers to extending nonplanar reduction techniques to the planar setting.

arXiv:2601.23198•Jan 30, 2026•0 citations
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 [ 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.
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.
We introduce a category qGph\mathsf{qGph}qGph of quantum graphs, whose definition is motivated entirely from noncommutative geometry. For all quantum graphs GGG and HHH in qGph\mathsf{qGph}qGph, we then construct a quantum graph [G,H][G,H][G,H] of homomorphisms from GGG to HHH, making qGph\mathsf{qGph}qGph a closed symmetric monoidal category. We prove that for all finite graphs GGG and HHH, the quantum graph [G,H][G,H][G,H] is nonempty iff the (G,H)(G,H)(G,H)-homomorphism game has a winning quantum strategy, directly generalizing the classical case. The finite quantum graphs in qGph\mathsf{qGph}qGph are tracial, real, and self-adjoint, and the morphisms between them are CP morphisms that are adjoint to a unital ∗*∗-homomorphism. We prove that Weaver's two notions of a CP morphism coincide in this context. We also include a short proof that every finite reflexive quantum graph is the confusability quantum graph of a quantum channel.
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.
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.
We study quantum property testing of directed graphs whose maximum in-degree and out-degree are bounded by a fixed constant ddd. For a proximity parameter ε\varepsilonε, we prove that every property testable with Oε,d(1)O_{\varepsilon,d}(1)Oε,d​(1) quantum queries in the bidirectional model, where both incoming and outgoing neighbors are accessible, can also be tested in the quantum unidirectional model, where only outgoing neighbors are accessible, using n1/2−Ωε,d(1)n^{1/2-Ω_{\varepsilon,d}(1)}n1/2−Ωε,d​(1) queries. This gives an almost quadratic quantum speedup over the best known generic classical transformation. Our proof has two main ingredients. First, we show that, in the bidirectional model for bounded-degree digraphs, the class of properties testable with constantly many classical queries coincides with the class testable with constantly many quantum queries. Second, we give a transformation from classical bidirectional testers to quantum unidirectional testers by designing a quantum unidirectional algorithm for estimating the frequency vector of constant-radius rooted discs. The algorithm combines quantum counting and Grover search with a correction procedure that removes false local appearances of smaller disc types inside larger neighborhoods. We further show that this transformation is essentially tight. For every sufficiently small fixed ε>0\varepsilon>0ε>0, there is a degree bound d=d(ε)d=d(\varepsilon)d=d(ε) and an explicit property PεP_\varepsilonPε​ for ddd-bounded-degree digraphs that is ε\varepsilonε-testable with Oε(1)O_\varepsilon(1)Oε​(1) classical, and hence quantum, bidirectional queries, but requires $ \widetildeΩ_\varepsilon \left(n^{1/2-f'(\varepsilon)}\right) $ quantum queries in the unidirectional model, where f′(ε)→0f'(\varepsilon)\to 0f′(ε)→0 as ε→0\varepsilon\to 0ε→0.
We study the complexity of counting (weighted) planar graph homomorphism problem Pl-GH(M)\tt{Pl\text{-}GH}(M)Pl-GH(M) parametrized by an arbitrary symmetric non-negative real valued matrix MMM. For matrices with pairwise distinct diagonal values, we prove a complete dichotomy theorem: Pl-GH(M)\tt{Pl\text{-}GH}(M)Pl-GH(M) is either polynomial-time tractable, or #\##P-hard, according to a simple criterion. More generally, we obtain a dichotomy whenever every vertex pair of the graph represented by MMM can be separated using some planar edge gadget. A key question in proving complexity dichotomies in the planar setting is the expressive power of planar edge gadgets. We build on the framework of Mančinska and Roberson to establish links between \textit{planar} edge gadgets and the theory of the \textit{quantum automorphism group} Qut(M)\tt{Qut}(M)Qut(M). We show that planar edge gadgets that can separate vertex pairs of MMM exist precisely when Qut(M)\tt{Qut}(M)Qut(M) is \emph{trivial}, and prove that the problem of whether Qut(M)\tt{Qut}(M)Qut(M) is trivial is undecidable. These results delineate the frontier for planar homomorphism counting problems and uncover intrinsic barriers to extending nonplanar reduction techniques to the planar setting.