Quantum graphs of homomorphisms

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.