Constructing the category of quantum graphs

Quantum graphs are structures that first arose in the problem of quantum error correction [2]. This talk will describe the closed symmetric monoidal category of quantum graphs that was recently introduced in [4]. The focus of the talk will be the construction of this category from the perspective of category theory and the relevance of this category to quantum information theory.

The symmetric monoidal category $\mathrm{𝗊𝖦𝗉𝗁}$ of quantum graphs can be obtained from the complex numbers $ℂ$ by a sequence of category-theoretic constructions, where we view $ℂ$ as an $\mathrm{𝖠𝖻}$-enriched dagger category with a single object. This sequence of constructions passes through the $\mathrm{𝖲𝗎𝗉}$-enriched dagger category $\mathrm{𝗊𝖱𝖾𝗅}$ of quantum sets and relations, which serves as an allegory-like setting for discrete quantum mathematics [3]. The structure of $\mathrm{𝗊𝖱𝖾𝗅}$ yields definitions of both the category $\mathrm{𝗊𝖦𝗉𝗁}$ of (discrete) quantum graphs and the category $\mathrm{𝗊𝖦𝗋𝗉}$ of (discrete) quantum groups via allegorical internalization.

The symmetric monoidal category $\mathrm{𝗊𝖦𝗉𝗁}$ contains the symmetric monoidal category $\mathrm{𝖦𝗉𝗁}$ as a full monoidal subcategory. Here, $\mathrm{𝖦𝗉𝗁}$ consists of graphs in which loops are allowed and multiple edges are forbidden, and its monoidal product is the box product $G\square H$, for which $(g_1,h_1)\sim (g_2,h_2)$ if both $g_1\sim g_2$ and $h_1=h_2$ or both $g_1=g_2$ and $h_1\sim h_2$. The symmetric monoidal structure on $\mathrm{𝗊𝖦𝗉𝗁}$ is defined analogously. We prove that $\mathrm{𝖦𝗉𝗁}$ and $\mathrm{𝗊𝖦𝗉𝗁}$ are closed by internalizing the same abstract argument in $\mathrm{𝖱𝖾𝗅}$ and $\mathrm{𝗊𝖱𝖾𝗅}$, respectively. Furthermore, $\mathrm{𝗊𝖦𝗉𝗁}$ is enriched over $\mathrm{𝖦𝗉𝗁}$, and the functor $\mathrm{𝗊𝖦𝗉𝗁}(K_1,-):\mathrm{𝗊𝖦𝗉𝗁}\to \mathrm{𝖦𝗉𝗁}$ has a full and faithful left adjoint, making $\mathrm{𝖦𝗉𝗁}$ a coreflective monoidal subcategory of $\mathrm{𝗊𝖦𝗉𝗁}$.

The category $\mathrm{𝗊𝖦𝗉𝗁}$ is connected to two topics in quantum information theory in the possibilistic regime. The first topic is zero-error transmission over a quantum channel. We associate with every quantum channel $\phi$ a morphism $T_{\phi }$ of $\mathrm{𝗊𝖱𝖾𝗅}$ that retains its possibilistic data, so that the confusability quantum graph of $\phi$ has adjacency relation $T_{\phi }^{†}\circ T_{\phi }$. The classical and quantum capacities of the quantum channel can then be defined in terms of this confusability quantum graph using the structure of $\mathrm{𝗊𝖦𝗉𝗁}$. We show that every finite quantum graph is a confusability quantum graph, answering a question of Daws [1, section 6.2]. From this perspective, the morphisms of $\mathrm{𝗊𝖦𝗉𝗁}$ correspond to those quantum channels that respect this implicit confusability structure in a natural sense and that do not increase a variant of von Neumann entropy.

The second topic in quantum information theory that has a connection to $\mathrm{𝗊𝖦𝗉𝗁}$ is quantum nonlocality. Graph homomorphisms games form a key class of examples of quantum nonlocality in the possibilistic regime. For finite simple graphs $G$ and $H$, the $(G,H)$-homomorphism game is a nonlocal game that has a winning strategy iff the external hom graph $\mathrm{𝗊𝖦𝗉𝗁}(G,H)$ is nonempty, i.e., not initial. However, when the players share entangled quantum systems, they may have a winning strategy even when $\mathrm{𝗊𝖦𝗉𝗁}(G,H)$ is empty [5]. We show that the $(G,H)$-homomorphism game has such a winning quantum strategy iff the internal hom quantum graph $[G,H]$ is nonempty. Thus, the closed symmetric monoidal structure of $\mathrm{𝗊𝖦𝗉𝗁}$ encodes the existence of winning quantum strategies in a natural way that directly generalizes the classical case.