arXiv:2601.09685

Quantum graphs of homomorphisms

Andre Kornell, Bert Lindenhovius

quant-phmath-phmath.CTmath.OASubmitted Jan 14, 2026• Announced Jan 15, 2026• 0 citations• Revised Jan 26, 2026 (v2)

Abstract

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.

Comments: 32 pages; added reference

Related papers

The quantum-to-classical graph homomorphism game

Michael Brannan, Priyanga Ganesan, Samuel J. Harris

arXiv:2009.07229Journal of Mathematical PhysicsNov 1, 202220 citations

A compositional approach to quantum functions

Benjamin Musto, David Reutter, Dominic Verdon

arXiv:1711.07945Journal of Mathematical PhysicsAug 1, 201853 citations

Covariant Quantum Combinatorics with Applications to Zero-Error Communication

Dominic Verdon

arXiv:2302.07776Communications in Mathematical PhysicsFeb 1, 20243 citations

Quantum games and synchronicity

Adina Goldberg

arXiv:2408.15444QuantumJan 14, 20260 citations

The Quantum Monad on Relational Structures

Samson Abramsky, Rui Soares Barbosa, Nadish de Silva +1 more

arXiv:1705.07310Leibniz international proceedings in informaticsJan 1, 201723 citations

The Quantum Homomorphism Orders are Universal

Yangjing Long

arXiv:2605.19543May 19, 20260 citations

arXiv:2601.09685

Quantum graphs of homomorphisms

Andre Kornell, Bert Lindenhovius

quant-phmath-phmath.CTmath.OASubmitted Jan 14, 2026• Announced Jan 15, 2026• 0 citations• Revised Jan 26, 2026 (v2)

arXiv HTML PDF

Abstract

We introduce a category

\mathsf{qGph}

of quantum graphs, whose definition is motivated entirely from noncommutative geometry. For all quantum graphs

G

and

H

\mathsf{qGph}

, we then construct a quantum graph

[G,H]

of homomorphisms from

G

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.

Comments: 32 pages; added reference

Related papers

The quantum-to-classical graph homomorphism game

Michael Brannan, Priyanga Ganesan, Samuel J. Harris

Motivated by non-local games and quantum coloring problems, we introduce a graph homomorphism game between quantum graphs and classical graphs. This game is naturally cast as a “quantum–classical game,” that is, a non-local game of two players involving quantum questions and classical answers. This game generalizes the graph homomorphism game between classical graphs. We show that winning strategies in the various quantum models for the game is an analog of the notion of non-commutative graph homomorphisms due to Stahlke [IEEE Trans. Inf. Theory 62(1), 554–577 (2016)]. Moreover, we present a game algebra in this context that generalizes the game algebra for graph homomorphisms given by Helton et al. [New York J. Math. 25, 328–361 (2019)]. We also demonstrate explicit quantum colorings of all quantum complete graphs, yielding the surprising fact that the algebra of the four coloring game for a quantum graph is always non-trivial, extending a result of Helton et al. [New York J. Math. 25, 328–361 (2019)].Motivated by non-local games and quantum coloring problems, we introduce a graph homomorphism game between quantum graphs and classical graphs. This game is naturally cast as a “quantum–classical game,” that is, a non-local game of two players involving quantum questions and classical answers. This game generalizes the graph homomorphism game between classical graphs. We show that winning strategies in the various quantum models for the game is an analog of the notion of non-commutative graph homomorphisms due to Stahlke [IEEE Trans. Inf. Theory 62(1), 554–577 (2016)]. Moreover, we present a game algebra in this context that generalizes the game algebra for graph homomorphisms given by Helton et al. [New York J. Math. 25, 328–361 (2019)]. We also demonstrate explicit quantum colorings of all quantum complete graphs, yielding the surprising fact that the algebra of the four coloring game for a quantum graph is always non-trivial, extending a result of Helton et al. [New York J. Math. 25, 328–361 (2019)].

arXiv:2009.07229Journal of Mathematical PhysicsNov 1, 202220 citations

A compositional approach to quantum functions

Benjamin Musto, David Reutter, Dominic Verdon

We introduce a notion of quantum function and develop a compositional framework for finite quantum set theory based on a 2-category of quantum sets and quantum functions. We use this framework to formulate a 2-categorical theory of quantum graphs, which captures the quantum graphs and quantum graph homomorphisms recently discovered in the study of nonlocal games and zero-error communication and relates them to quantum automorphism groups of graphs considered in the setting of compact quantum groups. We show that the 2-categories of quantum sets and quantum graphs are semisimple. We analyze dualisable and invertible 1-morphisms in these 2-categories and show that they correspond precisely to the existing notions of quantum isomorphism and classical isomorphism between sets and graphs.We introduce a notion of quantum function and develop a compositional framework for finite quantum set theory based on a 2-category of quantum sets and quantum functions. We use this framework to formulate a 2-categorical theory of quantum graphs, which captures the quantum graphs and quantum graph homomorphisms recently discovered in the study of nonlocal games and zero-error communication and relates them to quantum automorphism groups of graphs considered in the setting of compact quantum groups. We show that the 2-categories of quantum sets and quantum graphs are semisimple. We analyze dualisable and invertible 1-morphisms in these 2-categories and show that they correspond precisely to the existing notions of quantum isomorphism and classical isomorphism between sets and graphs.

arXiv:1711.07945Journal of Mathematical PhysicsAug 1, 201853 citations

Covariant Quantum Combinatorics with Applications to Zero-Error Communication

Dominic Verdon

Abstract We develop the theory of quantum (a.k.a. noncommutative) relations and quantum (a.k.a. noncommutative) graphs in the finite-dimensional covariant setting, where all systems (finite-dimensional $C^*$ C ∗ -algebras) carry an action of a compact quantum group G , and all channels (completely positive maps preserving a certain G -invariant functional) are covariant with respect to the G -actions. We motivate our definitions by applications to zero-error quantum communication theory with a symmetry constraint. Some key results are the following: (1) We give a necessary and sufficient condition for a covariant quantum relation to be the underlying relation of a covariant channel. (2) We show that every quantum confusability graph with a G -action (which we call a quantum G -graph) arises as the confusability graph of a covariant channel. (3) We show that a covariant channel is reversible precisely when its confusability G -graph is discrete. (4) When G is quasitriangular (this includes all compact groups), we show that covariant zero-error source-channel coding schemes are classified by covariant homomorphisms between confusability G -graphs.Abstract We develop the theory of quantum (a.k.a. noncommutative) relations and quantum (a.k.a. noncommutative) graphs in the finite-dimensional covariant setting, where all systems (finite-dimensional $$C^*$$ C ∗ -algebras) carry an action of a compact quantum group G , and all channels (completely positive maps preserving a certain G -invariant functional) are covariant with respect to the G -actions. We motivate our definitions by applications to zero-error quantum communication theory with a symmetry constraint. Some key results are the following: (1) We give a necessary and sufficient condition for a covariant quantum relation to be the underlying relation of a covariant channel. (2) We show that every quantum confusability graph with a G -action (which we call a quantum G -graph) arises as the confusability graph of a covariant channel. (3) We show that a covariant channel is reversible precisely when its confusability G -graph is discrete. (4) When G is quasitriangular (this includes all compact groups), we show that covariant zero-error source-channel coding schemes are classified by covariant homomorphisms between confusability G -graphs.

arXiv:2302.07776Communications in Mathematical PhysicsFeb 1, 20243 citations

Quantum games and synchronicity

Adina Goldberg

In the flavour of categorical quantum mechanics, we extend nonlocal games to allow quantum questions and answers, using quantum sets (special symmetric dagger Frobenius algebras) and the quantum functions of Musto, Reutter, and Verdon. Equations are presented using a diagrammatic calculus for tensor categories. To this quantum question and answer setting, we extend the standard definitions, including strategies, correlations, and synchronicity, and we use these definitions to extend results about synchronicity. We extend the graph homomorphism (isomorphism) game to quantum graphs, and show it is synchronous (bisynchronous) and connect its perfect (bi)strategies to quantum graph homomorphisms (isomorphisms). Our extended definitions agree with the existing quantum games literature, except in the case of synchronicity.In the flavour of categorical quantum mechanics, we extend nonlocal games to allow quantum questions and answers, using quantum sets (special symmetric dagger Frobenius algebras) and the quantum functions of Musto, Reutter, and Verdon. Equations are presented using a diagrammatic calculus for tensor categories. To this quantum question and answer setting, we extend the standard definitions, including strategies, correlations, and synchronicity, and we use these definitions to extend results about synchronicity. We extend the graph homomorphism (isomorphism) game to quantum graphs, and show it is synchronous (bisynchronous) and connect its perfect (bi)strategies to quantum graph homomorphisms (isomorphisms). Our extended definitions agree with the existing quantum games literature, except in the case of synchronicity.

arXiv:2408.15444QuantumJan 14, 20260 citations

The Quantum Monad on Relational Structures

Samson Abramsky, Rui Soares Barbosa, Nadish de Silva +1 more

Homomorphisms between relational structures play a central role in finite model theory, constraint satisfaction and database theory. A central theme in quantum computation is to show how quantum resources can be used to gain advantage in information processing tasks. In particular, non-local games have been used to exhibit quantum advantage in boolean constraint satisfaction, and to obtain quantum versions of graph invariants such as the chromatic number. We show how quantum strategies for homomorphism games between relational structures can be viewed as Kleisli morphisms for a quantum monad on the (classical) category of relational structures and homomorphisms. We show a general connection between these notions and state-independent quantum realizations of strong contextuality in the Abramsky-Brandenburger formulation of contextuality. We use these results to exhibit a wide range of examples of contextuality-powered quantum advantage, and to unify several apparently diverse strands of previous work.Homomorphisms between relational structures play a central role in finite model theory, constraint satisfaction and database theory. A central theme in quantum computation is to show how quantum resources can be used to gain advantage in information processing tasks. In particular, non-local games have been used to exhibit quantum advantage in boolean constraint satisfaction, and to obtain quantum versions of graph invariants such as the chromatic number. We show how quantum strategies for homomorphism games between relational structures can be viewed as Kleisli morphisms for a quantum monad on the (classical) category of relational structures and homomorphisms. We show a general connection between these notions and state-independent quantum realizations of strong contextuality in the Abramsky-Brandenburger formulation of contextuality. We use these results to exhibit a wide range of examples of contextuality-powered quantum advantage, and to unify several apparently diverse strands of previous work.

arXiv:1705.07310Leibniz international proceedings in informaticsJan 1, 201723 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.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.19543May 19, 20260 citations

We introduce a category

\mathsf{qGph}

of quantum graphs, whose definition is motivated entirely from noncommutative geometry. For all quantum graphs

G

and

H

\mathsf{qGph}

, we then construct a quantum graph

[G,H]

of homomorphisms from

G

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

*

C^*

C ∗ -algebras) carry an action of a compact quantum group G , and all channels (completely positive maps preserving a certain G -invariant functional) are covariant with respect to the G -actions. We motivate our definitions by applications to zero-error quantum communication theory with a symmetry constraint. Some key results are the following: (1) We give a necessary and sufficient condition for a covariant quantum relation to be the underlying relation of a covariant channel. (2) We show that every quantum confusability graph with a G -action (which we call a quantum G -graph) arises as the confusability graph of a covariant channel. (3) We show that a covariant channel is reversible precisely when its confusability G -graph is discrete. (4) When G is quasitriangular (this includes all compact groups), we show that covariant zero-error source-channel coding schemes are classified by covariant homomorphisms between confusability G -graphs.

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.