---
abstract: '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 analyse 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.'
bibliography:
- 'QSET.bib'
title: A compositional approach to quantum functions
---

Introduction
============

#### On quantum functions.

In this work, we introduce a notion of *quantum function* between finite *quantum sets* and propose a framework for finite quantum set theory.

These quantum functions underlie various notions of ‘quantum morphism’ previously defined in quantum information theory and noncommutative topology.[^1]

Several such notions

have recently emerged from the study of *quantum pseudo-telepathy* [@Brassard2005], a phenomenon in quantum theory where pre-shared entanglement is used to perform a task classically impossible without communication. Such tasks are usually formulated as games, where winning classical strategies correspond to certain homomorphisms between combinatorial structures; quantum strategies can then be understood as quantised versions of these homomorphisms. One such game is the *graph homomorphism game* [@Mancinska2016], leading to a notion of *quantum graph homomorphism*. We show that quantum graph homomorphisms are quantum functions between vertex sets preserving the graph structure; in fact, quantum functions can themselves be understood as perfect quantum strategies for a certain ‘function game’. The theory of quantum functions places this game-theoretic approach to quantisation into a broader mathematical context, in particular relating it to more conventional approaches to quantisation.=-2

Indeed, since the advent of quantum mechanics, quantisation has been associated with the passage from commuting to noncommuting variables. In the spirit of noncommutative topology[^2], we regard $C^*$-algebras as noncommutative analogues of topological spaces, or *quantum spaces*, with finite-dimensional $C^*$-algebras playing the role of *finite quantum sets*. Finding an appropriate definition of a quantum space of quantum functions between finite sets is a more subtle issue. Conventionally, these quantum spaces are defined as $C^*$-algebras satisfying a universal property. A prominent example is Wang’s *quantum permutation group* [@Wang1998] of a set, defined in the framework of compact quantum groups [@Woronowicz1998] and later extended to the *quantum automorphism group* [@Banica2005] of a graph. Our framework captures the finite-dimensional representation theory of these $C^*$-algebras and extends the existing theory of quantum permutation and automorphism groups to a theory of general morphisms between different sets and graphs. In particular, it relates quantum automorphism groups to the *quantum graph isomorphisms* [@Atserias2016] considered in the study of pseudo-telepathy, providing a concrete link between results in noncommutative topology and recent problems in quantum information theory.

Our theory of quantum functions — unifying and extending the above approaches to the quantisation of combinatorial structures — is formulated in categorical terms and allows us to apply techniques from categorical algebra, such as the notions of semisimplicity and dualisability. The following is a brief summary of our main results:

-   We show that quantum sets and quantum functions naturally form a 2-category $\QSet$ (Definition \[def:2catqset\]) ‘quantising’ the category of finite sets and functions. Similarly, quantum graphs (Definition \[def:quantumgraphsbyadjmats\], see also [@Duan2013; @Weaver2015]) and quantum graph homomorphisms naturally form a 2-category $\QGraph$ (Definition \[def:2catqgraph\]) ‘quantising’ the category of finite graphs and graph homomorphisms. This higher compositional structure has not been noticed before.

-   We characterise quantum bijections and quantum isomorphisms as *dagger-dualisable* 1-morphisms (Definition \[def:daggerdualisable\]) in the 2-categories $\QSet$ and $\QGraph$, respectively (Theorem \[thm:dual2\], Theorem \[thm:dualisablequantumgraph\]). We also show that classical bijections and graph isomorphisms are equivalences in these 2-categories (see Proposition \[prop:equivalence\]). In particular, we emphasise that quantum bijections and quantum graph isomorphisms should not be thought of as invertible but merely as dualisable, a characterisation which crucially depends on the $2$-categorical structure.

-   We show that the categories $\QSet(A,B)$ of quantum functions between quantum sets $A$ and $B$, and the categories $\QGraph(G,H)$ of quantum homomorphisms between quantum graphs $G$ and $H$, are *semisimple*, a categorical property which commonly arises in representation theory. This is crucial for the structural understanding of quantum functions, and allows us to characterise certain quantum functions as essentially classical (Definition \[def:classical\]).

Our notions of quantum graph homomorphism and quantum graph isomorphism coincide with those considered in the theory of nonlocal games [@Mancinska2016; @Atserias2016] (Propositions \[prop:mancinskagraphhom\] and \[prop:Atserias\]). We also show that the monoidal category of quantum bijections on a quantum set is the category of finite-dimensional representations of the Hopf $C^*$-algebra associated to Wang’s quantum permutation group (Proposition \[prop:Wang\], [@Wang1998]). Similarly, we show that the monoidal category of quantum automorphisms of a graph is the category of finite-dimensional representations of the Hopf $C^*$-algebra associated to Banica’s quantum automorphism group (Proposition \[prop:Banica\], [@Banica2005]).

The $2$-categories $\QSet$ and $\QGraph$ therefore extend these quantum groups analogously to the way in which categories extend groups or monoids.

The results in this work serve as a foundation for finite quantum set and quantum graph theory. In a subsequent paper [@paper1b], we use this framework to classify quantum isomorphic graphs in terms of algebraical and group theoretical data.

#### A new approach to quantum functions.

While noncommutative topology is formulated in the language of operator algebras, we present a compositional, linear algebraic framework based on the graphical calculus of string diagrams. In our diagrams, wires represent finite-dimensional Hilbert spaces, and vertices represent linear maps between them. Wiring diagrams, read from bottom to top, represent composite linear maps in the obvious way. We start from the following simple graphical observation:[^3]

\[eq:basicidea\]

(1.5,0) to node\[zxnode=, pos=0.25,scale=1.2\](a) [$a$]{} node\[zxnode=, pos=0.75,scale=1.2\] (b) [$b$]{}(0,2); (\[xshift=+, yshift=-\]b.center) to \[out=20, in=70,looseness=1.1\] (\[xshift=-,yshift=+\]a.center); (\[xshift=--, yshift=-+\] a.center) to \[out=-160, in=-110, looseness=1.1\] (\[xshift=-+, yshift=--\] b.center) ;

  =  

(1.5,0) to node\[zxnode=, pos=0.25,scale=1.2\][$b$]{} node\[zxnode=, pos=0.75,scale=1.2\] [$a$]{}(0,2);

&

(1.5,0) to node\[zxnode=, pos=0.25,scale=1.2\][$a$]{} node\[zxnode=, pos=0.75,scale=1.2\] [$b$]{}(0,2);

    

(1.5,0) to node\[zxnode=, pos=0.25,scale=1.2\][$b$]{} node\[zxnode=, pos=0.75,scale=1.2\] [$a$]{}(0,2);

The two free-floating vertices on the left can move around each other, whereas on the right they are confined to move on a line and do not commute.[^4] In other words, adding a wire to a diagram can turn a commutative situation into a noncommutative one.

Taking this idea seriously leads to the following sketch of a programme. By Gelfand duality, a combinatorial theory, such as the theory of finite sets and functions or finite graphs and graph homomorphisms, can be expressed in terms of finite-dimensional commutative algebra and therefore represented in the graphical calculus. To quantise the objects of the theory — in our case, sets or graphs — one simply passes from commutative to noncommutative algebras. The novelty of our approach lies in our treatment of morphisms: having formulated the theory in term of string diagrams, we quantise morphisms by adding a wire through the corresponding vertices. We illustrate this idea with an example:

\[eq:quantisationexample\]

(0,0) to (0,2) to \[out=135\] (-0.75,3); (0,2) to \[out=45\] (0.75, 3); at (0,1) [$f$]{}; at (0,2) ;

   =   

(0,0) to (0,0.75) to \[out=135\] (-0.75,1.75) to (-0.75,3); (0,0.75) to \[out=45\] (0.75, 1.75) to +(0,1.25); at (-0.75,2) [$f$]{}; at (0.75,2) [$f$]{}; at (0,0.75) ;

(0,0) to (0,2) to \[out=45\] (0.75,3); (0,2) to \[out=135\] (-0.75,3); (1.75,0) to \[looseness=0.9\] node\[zxnode=, pos=0.5\] [$f$]{} (-1.75,2.5) to (-1.75,3); at (0,2);

   =   

(0,0) to (0,0.75) to \[out=45\] (0.75,1.75) to (0.75,3); (0,0.75) to \[out=135\] (-0.75,1.75) to (-0.75,3); (1.75,0) to (1.75,0.75) to \[looseness=1.1, in looseness=0.9\] node\[zxnode=, pos=0.36\] [$f$]{} node\[zxnode=, pos=0.64\] [$f$]{}(-1.75,3); at (0,0.75);

The equation on the left is one of the properties of any function between two sets, while the equation on the right is its ‘quantisation’. Further examples of classical morphisms and their quantisations are displayed in Figure \[fig:classicalquantum\].

#### The compositional structure of quantum functions.

Due to the presence of the additional Hilbert space wire introduced in our quantisation procedure, we are naturally led to consider maps on this Hilbert space, which interact in a particular way with quantum functions.

With these additional maps as morphisms, quantum functions between quantum sets $A$ and $B$ are the objects of a category $\QSet(A,B)$. This category of quantum functions between two quantum sets can be understood as a quantisation of the set of classical functions between two classical sets. In other words, our approach to quantisation leads to categorification. In particular, the category of quantum bijections on a set $X$ quantises the symmetric group $S_X$; as stated above, this is the category of quantum elements of Wang’s quantum permutation group.

A shortcoming of the compact quantum group approach is that it is restricted to automorphisms and cannot easily be applied to study quantum functions or graph homomorphisms between nonisomorphic sets or graphs, as is for example necessary for quantum pseudo-telepathy. In contrast, our approach allows us to consider all quantum functions and quantum graph homomorphisms, including those between nonisomorphic sets and graphs. We show that these form 2-categories $\QSet$ and $\QGraph$, which incorporate all the categories of quantum functions and homomorphisms between different sets and graphs into a single mathematical structure. These $2$-categories unify, generalise, and most importantly expose the connection between work on quantum permutations and quantum graph automorphisms in noncommutative topology, and on quantum graph homomorphisms and isomorphisms in quantum information theory.

Outlook
-------

We hope that our results lead to the development of further connections between the work on compact quantum groups and quantum information theory. In particular, we expect that the structural understanding of the automorphism categories $\QBij(B,B)$ and $\QIso(G,G)$ can lead to new insights into pseudo-telepathy. First considerations along these lines will appear in a companion paper [@paper1b].

We now suggest a number of other possible applications of our categorical :

-   Quantum functions are closely related to quantum communication. Indeed, in Remark \[rem:teleportation\], we note that quantum bijections between a matrix algebra $\mathrm{Mat}_n$ and an $n^2$-element classical set can be understood as generalised teleportation protocols. More generally, it has been observed that quantum homomorphisms between quantum graphs admit an interpretation in terms of zero-error source-channel coding [@Stahlke2016].

-   Our classification in [@paper1b] is based on the study of Frobenius monads in $\QGraph$. As symmetric monoidal $2$-categories (see Remark \[rem:symmmon2cat\]), $\QSet$ and $\QGraph$ admit several other as yet unexplored algebraic structures.

-   Our quantisation framework may be extended to other combinatorial theories besides finite set theory and graph theory. In particular, in Section \[app:quantumrelation\], we show how Kuperberg and Weaver’s finite-dimensional quantum relations [@Kuperberg2012] fit into our framework; this suggests, for example, a $2$-category of quantum posets and quantum monotone functions.=-2

Outline of the paper
--------------------

In Section \[sec:background\], we recall the diagrammatic calculus for Hilbert spaces and linear maps as well as the correspondence between finite-dimensional $C^*$-algebras and certain Frobenius algebras. We express Gelfand duality between finite sets and finite-dimensional commutative $C^*$-algebras in this setting.

In Section \[sec:quantumset\], we introduce quantum sets, quantum elements and quantum functions, and define the 2-category $\QSet$ which encodes their compositional structure. We justify our definitions by a universal property.

In Section \[sec:quantumbijection\], we quantise bijections and prove that the resulting quantum bijections are precisely dagger-dualisable 1-morphisms in $\QSet$. We show that quantum bijections between classical sets correspond to projective permutation matrices as defined in the theory of nonlocal games [@Atserias2016], and to finite-dimensional representations of Wang’s quantum symmetry group algebras [@Wang1998].

In Section \[sec:qgt\], we quantise finite graphs and their homomorphisms and define the $\QGraph$ which encodes their compositional structure. We show that our definitions capture the quantum graph homomorphisms and isomorphisms of Man[č]{}inska and Roberson [@Mancinska2016] and Atserias et al [@Atserias2016], as well as the finite-dimensional representation theory of Banica and Bichon’s quantum automorphism group algebras [@Banica2005; @Bichon2003]. We also show that quantum graph isomorphisms are precisely dagger-dualisable 1-morphisms in $\QGraph$.

In Section \[sec:semisimple\], we show that the categories of quantum functions and quantum graph homomorphisms are semisimple. We discuss the operational interpretation of the direct sum of quantum functions and show how this can be used to distinguish between classical and quantum structures.

In Section \[app:quantumrelation\], we show that our reflexive quantum graphs are precisely symmetric and reflexive quantum relations in the sense of Kuperberg and Weaver [@Kuperberg2012; @Weaver2010; @Weaver2015] and fully capture the noncommutative graphs appearing in zero-error communication [@Duan2013].

Related work {#sec:relatedwork}
------------

A compressed summary of this section can be found in Figure \[fig:relatedwork\].

  -- -- --
        
  -- -- --

#### Quantum symmetry groups and noncommutative topology.

The study of quantum permutation groups — quantum variants of the symmetric groups $S_n$ in noncommutative topology — was suggested by Connes, and carried out by Wang, Banica, Bichon and others [@Wang1998; @Banica2005; @Banica2007; @Banica2007_2; @Bichon2003; @Banica2009; @Banica2007_3]. These quantum permutation groups are compact quantum groups in the sense of Woronowicz [@Woronowicz1998], obtained from a universal construction [@Wang1998]. Quantum automorphism groups of finite graphs are defined similarly [@Bichon2003; @Banica2005]. A more general universal construction of quantum spaces of maps is given by So[ł]{}tan [@Soltan2009] (see Remark \[rem:soltan\]). In Section \[sec:universal\], we show that our categories of quantum functions $\QSet(A,B)$ can be obtained from an analogous universal construction, as the category of finite-dimensional representations of an internal hom $[A,B]$ in the opposite of the category of $C^*$-algebras. Likewise, our categories $\QBij([n],[n])$ of quantum bijections on an $n$-element set are the categories of finite-dimensional representations of the Hopf $C^*$-algebra $A(n)$ corresponding to Wang’s quantum permutation group [@Wang1998] (Proposition \[prop:Wang\]), and our categories $\QIso(G,G)$ of quantum automorphisms of a graph $G$ are the categories of finite-dimensional representations of the Hopf $C^*$-algebra $A(G)$ corresponding to Banica’s quantum automorphism group of the graph [@Banica2007]

Our framework therefore captures the finite-dimensional representation theory of the Hopf $C^*$-algebras considered in noncommutative topology. However, we note that a Tannakian correspondence exists only between these algebras and their categories of corepresentations (or, in the language of quantum group theory, with the representations of their associated compact quantum groups [@Neshveyev2013]. Also see Remark \[rem:problemTannaka\] and Remark \[rem:Wangnotdiscrete\]).

Based on the theory of quantum relations developed by Kuperberg and Weaver [@Kuperberg2012; @Weaver2010; @Weaver2015], Kornell [@Kornell2011; @Kornell2018] defines (possibly infinite) quantum sets and quantum functions between them. His notion of finite quantum set coincides with ours; his quantum functions between finite quantum sets are \*-homomorphisms and thus one-dimensional quantum functions in our sense.

#### Quantum information theory.

Quantum graph homomorphisms were defined by Mančinska and Roberson [@Mancinska2016] as generalisations of quantum graph colourings [@Cameron2007] in the context of nonlocal games (see Remark \[rem:quantumhomMancinska\]) and have been the subject of intensive study in their various forms [@Mancinska2016; @Scarpa2012; @Avis2006; @Cameron2007; @Paulsen2015; @Paulsen2016; @Roberson2016]. Quantum graph isomorphisms are originally due to Atserias et al [@Atserias2016] (see Remark \[rem:Atseriasquantumiso\]).

A related $C^*$-algebraic approach to quantum homomorphisms between classical graphs was recently discovered by Ortiz and Paulsen [@Ortiz2016]. They define a $C^*$-algebra which is essentially an internal hom, analogous to the algebra of quantum functions in Remark \[rem:quantumfunctionalgebra\].

Our notion of reflexive quantum graph coincides with that of Kuperberg and Weaver [@Kuperberg2012; @Weaver2015; @Weaver2010] (see Remark \[rem:literatureqgraph\] and Theorem \[thm:relationadjacency\]) and in particular generalises Duan, Severini and Winter’s noncommutative graphs [@Duan2013] (see Proposition \[prop:quantumgraphDuanthesame\]). Quantum graph homomorphisms between noncommutative graphs can be understood as pure versions of Stahlke’s entanglement-assisted morphisms [@Stahlke2016] (see Remark \[rem:stahlkegraphhoms\]).

#### Categorical quantum mechanics (CQM).

Our work emerges from the CQM research programme, initiated by Abramsky and Coecke [@Abramsky2008] and developed by them and others [@Coecke2008; @Coecke2007; @Coecke2009; @Vicary2010; @Coecke2014], which uses the graphical calculus of monoidal categories to provide a high-level syntax for quantum information flow. In particular, Vicary’s reformulation of the theory of finite-dimensional $C^*$-algebras in terms of Frobenius algebras [@Vicary2010] and Coecke, Pavlovi[ć]{} and Vicary’s proof of Gelfand duality in this setting [@Coecke2009] are important starting points and guide posts for our work (see Section \[sec:background\]). Many of our proofs and constructions can be understood as simple quantisations, in the sense of equation , of constructions from categorical quantum mechanics.

A related 2-categorical framework for quantum theory based on the 2-category $\mathrm{2Hilb}$ of categorified Hilbert spaces was studied by Vicary and the second author [@Vicary2012hq; @Vicary2012_2; @Reutter2016]; we remark that there is a locally faithful 2-functor $\QSet \to \mathrm{2Hilb}$ allowing us to translate most of our results into this setting.

#### Monads.

The 2-category of quantum sets $\QSet$ is an instance of Street’s 2-category of monads [@Street1972] in the $2$-category $\BHilb$, the delooping of the monoidal category $\Hilb$ (see Remark \[rem:street\]). Hinze and Marsden [@Marsden2014; @Hinze2016] give an analogous graphical treatment of the 2-category $\mathrm{Mnd}(\mathrm{Cat})$ of monads in the 2-category $\mathrm{Cat}$ of categories, functors and natural transformations.

Recent work by Abramsky and others [@Abramsky2017] uses monads to study binary constraint systems and quantum graph homomorphisms. There are many similarities between their work and ours; for example, composition in their Kleisli category corresponds to the composition of $1$-morphisms in $\QSet$ (see Remark \[rem:ppmcomposition\]).

Definitions and conventions
---------------------------

We assume some basic familiarity with monoidal category theory [@Selinger2010] and $2$-category theory [@Borceux1994 Chapter 7]. Dagger categories are defined in [@Selinger2010]; strict dagger $2$-categories[^5] and dagger $2$-functors are defined in [@Heunen2016]. When we refer to local properties of a 2-functor (such as local faithfulness), we mean that these properties are true of the induced functors on hom-categories. We use the words *module* and *representation* interchangeably. A projector on a Hilbert space $H$ is an endomorphism $P: H \to H$ which is idempotent and self-adjoint $P = P^{\dagger} = P^2$. All sets appearing in this work are finite and, except where clearly specified, all vector spaces and all algebras are finite-dimensional; a notable exception is Section \[sec:universal\]. Consequently, we use the labels  and  for the categories of finite sets and finite-dimensional Hilbert spaces respectively. We also take all $C^*$-algebras to be unital. We denote the $n$-element set by $[n]$.

Acknowledgments {#acknowledgments .unnumbered}
---------------

We are especially grateful to Jamie Vicary for many useful conversations and comments on an earlier draft of this paper. We thank Andre Kornell for a useful conversation about our definitions of quantum functions. We also thank Samson Abramsky, and Rui Soares Barbosa for discussing the relationship between our categorical frameworks; Giulio Chiribella for introducing us to existing notions of noncommutative graphs; and Matty Hoban for informative conversations about nonlocal games. We appreciate the helpful comments of an anonymous referee regarding the presentation of these results.

$$\hspace{-2.3cm}
\setlength\arraycolsep{1pt}
\begin{array}{|c|c||c|c|}
\hline
\rule{0pt}{3ex} 
\begin{minipage}{1.7cm}\center
\text{set}
\end{minipage}&
\text{commutative algebra} &\text{non-commutative algebra} & \text{quantum set}
\\[-9pt] \rule{0pt}{0ex}&&&\\\hline
\text{element}& 
\begin{minipage}{\wl\textwidth}
\begin{calign}\nonumber
\begin{tz}[zx, master, every to/.style={out=up, in=down},xscale=-1]
\draw (0,1) to (0,2) to [out=135] (-0.75,3);
\draw (0,2) to [out=45] (0.75, 3);
\node[zxnode=\zxwhite] at (0,1) {$\psi$};
\node[zxvertex=\zxwhite, zxup] at (0,2) {};
\end{tz}
=~~~
\begin{tz}[zx,slave, every to/.style={out=up, in=down},xscale=-1]
\draw (-0.75,2) to (-0.75,3);
\draw (0.75, 2) to +(0,1.);
\node[zxnode=\zxwhite] at (-0.75,2) {$\psi$};
\node[zxnode=\zxwhite] at (0.75,2) {$\psi$};
\end{tz}
\hspace{1cm}
\begin{tz}[zx, every to/.style={out=up, in=down},xscale=-1]
\draw (0,1) to (0,2) ;
\node[zxnode=\zxwhite] at (0,1) {$\psi$};
\node[zxvertex=\zxwhite, zxup] at (0,2) {};
\end{tz}
~~=~~
\emptydiagram
\\\nonumber
\begin{tz}[zx,slave, every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,1.5);
\node[zxnode=\zxwhite] at (0,1.5) {$\psi^\dagger$};
\end{tz}
=~~~
\begin{tz}[zx,slave,every to/.style={out=up, in=down},xscale=-1]
\draw (0,1.5) to (0,2) to [in=left] node[pos=1] (r){} (0.5,2.5) to [out=right, in=up] (1,2)  to (1,0);
\node[zxnode=\zxwhite] at (0,1.5) {$\psi$};
\node[zxvertex=\zxwhite,zxdown] at (r.center){};
\end{tz}
\end{calign}
\end{minipage}
\hspace{\bnd}
&
%%%%%%%
\hspace{\bndm}
\begin{minipage}{\wr\textwidth}
\begin{calign}\nonumber
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,2) to [out=45] (0.75,3);
\draw (0,2) to [out=135] (-0.75,3);
\draw[arrow data={0.2}{>}, arrow data={0.8}{>}] (1.75,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5](Q) {$Q$} (-1.75,2.5) to (-1.75,3);
\node[zxvertex=\zxwhite, zxup] at (0,2){};
\draw[white,double] (0,0) to (Q.center);
\end{tz}
=
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0.75,1.75) to (0.75,3);
\draw  (-0.75,1.75) to (-0.75,3);
\draw[arrow data={0.2}{>}, arrow data={0.9}{>}] (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9] node[zxnode=\zxwhite, pos=0.36] {$Q$} node[zxnode=\zxwhite, pos=0.64] {$Q$}(-1.75,3);
\end{tz}
\hspace{1cm}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,2.25);
\draw[arrow data={0.2}{>}, arrow data={0.8}{>}] (1,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5](Q) {$Q$} (-1,2.5) to (-1,3);
\node[zxvertex=\zxwhite] at (0,2.25){};
\draw[white,double] (0,0) to (Q.center);
\end{tz}
=
\begin{tz}[zx, every to/.style={out=up, in=down},xscale=-1]
\draw[arrow data={0.2}{>}, arrow data={0.9}{>}] (1.,0) to [looseness=0.9]  (-1,2.5) to (-1,3);
\end{tz}
\\[-3pt]\nonumber
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-0.8]
\draw [arrow data={0.2}{>},arrow data={0.8}{>}]  (0,0) to (2.25,3);
\draw (2.25,0) to [in=-45] node[zxnode=\zxwhite, pos=1] (Q) {$Q^\dagger$} (1.125,1.5);
\node at (1,-0.5){};
\node at (1,3.5){};
\end{tz}
~=~~
\begin{tz}[zx,xscale=-0.6,yscale=-1]
\draw[arrow data={0.5}{<}] (0.25,-0.5) to (0.25,0) to [out=up, in=-135] (1,1);
\draw[arrow data={0.5}{>}] (1.75,2.5) to (1.75,2) to [out=down, in=45] (1,1);
\draw (1,1) to [out= -45, in= left] node[zxvertex=\zxwhite, pos=1] {} (2.3,0.3) to [out=right, in=down] (3.25,1) to (3.25,2.5);
\node [zxnode=\zxwhite] at (1,1) {$Q$};
\node at (1,-1){};
\node at (1,3){};
\end{tz}
\end{calign}
\end{minipage}
\hspace{\bndr}
&
\begin{minipage}{\wtext}\center quantum \\ element \end{minipage}\\
\hline
\text{function} &
\begin{minipage}{\wl\textwidth}
\begin{calign}\nonumber
\begin{tz}[zx, master, every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,2) to [out=135] (-0.75,3);
\draw (0,2) to [out=45] (0.75, 3);
\node[zxnode=\zxwhite] at (0,1) {$f$};
\node[zxvertex=\zxwhite, zxup] at (0,2) {};
\end{tz}
=
\begin{tz}[zx, every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,0.75) to [out=135] (-0.75,1.75) to (-0.75,3);
\draw (0,0.75) to [out=45] (0.75, 1.75) to +(0,1.25);
\node[zxnode=\zxwhite] at (-0.75,2) {$f$};
\node[zxnode=\zxwhite] at (0.75,2) {$f$};
\node[zxvertex=\zxwhite, zxup] at (0,0.75) {};
\end{tz}
\hspace{1cm}
\begin{tz}[zx,slave, every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,2) ;
\node[zxnode=\zxwhite] at (0,1) {$f$};
\node[zxvertex=\zxwhite, zxup] at (0,2) {};
\end{tz}
=
\begin{tz}[zx,slave, every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,0.75) ;
\node[zxvertex=\zxwhite, zxup] at (0,0.75) {};
\end{tz}
\\\nonumber
\begin{tz}[zx,slave, every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,3);
\node[zxnode=\zxwhite] at (0,1.5) {$f^\dagger$};
\end{tz}
=~~
\begin{tz}[zx,slave,every to/.style={out=up, in=down},xscale=-1]
\draw (0,1.5) to (0,2) to [in=left] node[pos=1] (r){} (0.5,2.5) to [out=right, in=up] (1,2)  to (1,0);
\draw (-1,3) to [out=down,in=up] (-1,1) to [out=down, in=left] node[pos=1] (l){} (-0.5,0.5) to [out=right, in=down] (0,1) to (0,1.5);
\node[zxnode=\zxwhite] at (0,1.5) {$f$};
\node[zxvertex=\zxwhite,zxup] at (l.center){};
\node[zxvertex=\zxwhite,zxdown] at (r.center){};
\end{tz}
\end{calign}\\[-15pt]
\end{minipage}
\hspace{\bnd}
%%%%%
&
\hspace{\bndm}
\begin{minipage}{\wr\textwidth}
\begin{calign}\nonumber
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,2) to [out=45] (0.75,3);
\draw (0,2) to [out=135] (-0.75,3);
\draw[arrow data={0.2}{>}, arrow data={0.8}{>}] (1.75,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5] {$P$} (-1.75,2.5) to (-1.75,3);
\node[zxvertex=\zxwhite, zxup] at (0,2){};
\end{tz}
=
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,0.75) to [out=45] (0.75,1.75) to (0.75,3);
\draw (0,0.75) to [out=135] (-0.75,1.75) to (-0.75,3);
\draw[arrow data={0.2}{>}, arrow data={0.9}{>}] (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9] node[zxnode=\zxwhite, pos=0.36] {$P$} node[zxnode=\zxwhite, pos=0.64] {$P$}(-1.75,3);
\node[zxvertex=\zxwhite, zxup] at (0,0.75){};
\end{tz}
\hspace{1cm}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,2.25);
\draw[arrow data={0.2}{>}, arrow data={0.8}{>}] (1,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5] {$P$} (-1,2.5) to (-1,3);
\node[zxvertex=\zxwhite] at (0,2.25){};
\end{tz}
=
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,0.75);
\draw[arrow data={0.2}{>}, arrow data={0.9}{>}] (1.,0) to (1.,0.75) to   (-1,3);
\node[zxvertex=\zxwhite, zxup] at (0,0.75){};
\end{tz}
\\[2pt]\nonumber
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-0.8]
\draw [arrow data={0.2}{>},arrow data={0.8}{>}]  (0,0) to (2.25,3);
\draw (2.25,0) to node[zxnode=\zxwhite, pos=0.5] {$P^\dagger$} (0,3);
\end{tz}
=~~
\begin{tz}[zx,xscale=-0.6,yscale=-1]
\draw[arrow data={0.5}{<}] (0.25,-0.5) to (0.25,0) to [out=up, in=-135] (1,1);
\draw (1,1) to [out=135, in=right] node[zxvertex=\zxwhite, pos=1]{} (-0.3, 1.7) to [out=left, in=up] (-1.25,1) to (-1.25,-0.5);
\draw[arrow data={0.5}{>}] (1.75,2.5) to (1.75,2) to [out=down, in=45] (1,1);
\draw (1,1) to [out= -45, in= left] node[zxvertex=\zxwhite, pos=1] {} (2.3,0.3) to [out=right, in=down] (3.25,1) to (3.25,2.5);
\node [zxnode=\zxwhite] at (1,1) {$P$};
\end{tz} 
\end{calign}\\[-15pt]
\end{minipage}
\hspace{\bndr}
%%%%%%%
&
\begin{minipage}{\wtext}\center quantum \\ function \end{minipage} \\ \hline
\text{bijection} &
%%%%%
\begin{minipage}{\wl\textwidth}
\vspace{0.2cm}
\hspace{0.1cm}function $+$
\vspace{-0.1cm}
\begin{calign}\nonumber
\begin{tz}[zx, master, every to/.style={out=up, in=down},yscale=-1,xscale=-1]
\draw (0,0) to (0,2) to [out=135] (-0.75,3);
\draw (0,2) to [out=45] (0.75, 3);
\node[zxnode=\zxwhite] at (0,1) {$f$};
\node[zxvertex=\zxwhite, zxdown] at (0,2) {};
\end{tz}
=
\begin{tz}[zx, every to/.style={out=up, in=down},yscale=-1,xscale=-1]
\draw (0,0) to (0,0.75) to [out=135] (-0.75,1.75) to (-0.75,3);
\draw (0,0.75) to [out=45] (0.75, 1.75) to +(0,1.25);
\node[zxnode=\zxwhite] at (-0.75,2) {$f$};
\node[zxnode=\zxwhite] at (0.75,2) {$f$};
\node[zxvertex=\zxwhite, zxdown] at (0,0.75) {};
\end{tz}
\hspace{1cm}
\begin{tz}[zx,slave, every to/.style={out=up, in=down},yscale=-1,xscale=-1]
\draw (0,0) to (0,2) ;
\node[zxnode=\zxwhite] at (0,1) {$f$};
\node[zxvertex=\zxwhite, zxup] at (0,2) {};
\end{tz}
=
\begin{tz}[zx,slave, every to/.style={out=up, in=down},yscale=-1,xscale=-1]
\draw (0,0) to (0,0.75) ;
\node[zxvertex=\zxwhite, zxup] at (0,0.75) {};
\end{tz}
\end{calign}\\[-15pt]
\end{minipage}
\hspace{\bnd}
&
%%%%%%%
\hspace{\bndm}
\begin{minipage}{\wr\textwidth}
\vspace{0.2cm}
quantum function $+$
\vspace{-0.1cm}
\begin{calign}\nonumber
\begin{tz}[zx,every to/.style={out=up, in=down},scale=-1,xscale=-1]
\draw (0,0) to (0,2) to [out=45] (0.75,3);
\draw (0,2) to [out=135] (-0.75,3);
\draw[arrow data={0.2}{<}, arrow data={0.8}{<}] (1.75,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5] {$P$} (-1.75,2.5) to (-1.75,3);
\node[zxvertex=\zxwhite, zxdown] at (0,2){};
\end{tz}
=
\begin{tz}[zx,every to/.style={out=up, in=down},scale=-1,xscale=-1]
\draw (0,0) to (0,0.75) to [out=45] (0.75,1.75) to (0.75,3);
\draw (0,0.75) to [out=135] (-0.75,1.75) to (-0.75,3);
\draw[arrow data={0.2}{<}, arrow data={0.9}{<}] (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9] node[zxnode=\zxwhite, pos=0.36] {$P$} node[zxnode=\zxwhite, pos=0.64] {$P$}(-1.75,3);
\node[zxvertex=\zxwhite, zxdown] at (0,0.75){};
\end{tz}
\hspace{1cm}
\begin{tz}[zx,every to/.style={out=up, in=down},scale=-1,xscale=-1]
\draw (0,0) to (0,2.25);
\draw[arrow data={0.2}{<}, arrow data={0.8}{<}] (1,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5] {$P$} (-1,2.5) to (-1,3);
\node[zxvertex=\zxwhite] at (0,2.25){};
\end{tz}
=
\begin{tz}[zx,every to/.style={out=up, in=down},scale=-1,xscale=-1]
\draw (0,0) to (0,0.75);
\draw[arrow data={0.2}{<}, arrow data={0.9}{<}] (1.,0) to (1.,0.75) to   (-1,3);
\node[zxvertex=\zxwhite] at (0,0.75){};
\end{tz}
\end{calign}\\[-15pt]
\end{minipage}
\hspace{\bndr}
&
\begin{minipage}{\wtext}\center quantum \\ bijection \end{minipage}   \\
\hline \nonumber
\begin{minipage}{1.5cm}\center graph \\homom.\end{minipage}&
%%%%%%%%
\begin{minipage}{\wl\textwidth}
\vspace{0.2cm}
\hspace{0.01cm}function $+$
\vspace{-0.2cm}
\def\d{2}
\begin{calign}\nonumber
\begin{tz}[zx,yscale=0.8,xscale=-1]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.5] {$f$} (0,5);\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.5] {$f$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G$};
\end{tz}
~~=~~
\begin{tz}[zx,yscale=0.8,xscale=-1]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.5] {$f$} (0,5);\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.5] {$f$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G$};
\draw[string] (0, 4) to (\d,4);
\node[zxvertex=\zxwhite] at (0,4){};
\node[zxvertex=\zxwhite] at (\d,4){};
\node[zxnode=\zxwhite] at (\d/2, 4 ) {$H$};
\end{tz}
\end{calign}\\[-15pt]
\end{minipage}
\hspace{\bnd}
&
%%%%%%%%%%%%
\hspace{\bndm}
\begin{minipage}{\wr\textwidth}
\vspace{0.2cm}
\hspace{-0.36cm}quantum function $+$
\vspace{-0.2cm}
\def\d{2}
\begin{calign}\nonumber
\begin{tz}[zx,yscale=0.8,xscale=-1]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.57] {$P$} (0,5);\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.43] {$P$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G$};
\draw[string, arrow data={0.08}{>},arrow data={0.5}{>}, arrow data ={0.95}{>}] (3, -0.5)  to (3,0.5) to [out=up, in=down] (-1.,4) to (-1.,5);
\end{tz}
~=~
\begin{tz}[zx,yscale=0.8,xscale=-1]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.57] {$P$} (0,5);\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.43] {$P$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G$};
\draw[string] (0, 4) to (\d,4);
\node[zxvertex=\zxwhite] at (0,4){};
\node[zxvertex=\zxwhite] at (\d,4){};
\node[zxnode=\zxwhite] at (\d/2, 4 ) {$H$};
\draw[string, arrow data={0.08}{>}, arrow data ={0.5}{>},arrow data ={0.95}{>}] (3, -0.5)  to (3,0.5) to [out=up, in=down] (-1.,4) to (-1.,5);
\end{tz}
\end{calign}\\[-15pt]
\end{minipage}
\hspace{\bndr}
&
\begin{minipage}{\wtext}\center quantum \\ graph\\homom. \end{minipage}\\
\hline\nonumber
\begin{minipage}{1.5cm}\center graph \\iso.\end{minipage} &
%%%%%
\begin{minipage}{\wl\textwidth}
\vspace{0.2cm}
\hspace{-0.0cm}bijection $+$
\vspace{-0.1cm}
\begin{calign}\nonumber
\begin{tz}[zx,every to/.style={out=up, in=down},scale=1,xscale=-1]
\draw (0,0) to (0,3);
\path (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9]  node[zxnode=\zxwhite, pos=0.5] {$P$}(-1.75,3);
\node[zxnode=\zxwhite] at (0,0.9){$G$};
\end{tz}
=
\begin{tz}[zx,every to/.style={out=up, in=down},scale=1,xscale=-1]
\draw (0,0) to (0,3);
\path (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9]  node[zxnode=\zxwhite, pos=0.5] {$H$}(-1.75,3);
\node[zxnode=\zxwhite] at (0,0.9){$P$};
\end{tz}
\end{calign}\\[-25pt]
\end{minipage}
\hspace{\bnd}
&
%%%%%%%
\hspace{\bndm}
\begin{minipage}{\wr\textwidth}
\vspace{0.2cm}
\hspace{-0.35cm}quantum bijection $+$
\vspace{-0.1cm}
\begin{calign}\nonumber
\begin{tz}[zx,every to/.style={out=up, in=down},scale=1,xscale=-1]
\draw (0,0) to (0,3);
\draw[arrow data={0.2}{>}, arrow data={0.9}{>}] (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9]  node[zxnode=\zxwhite, pos=0.5] {$P$}(-1.75,3);
\node[zxnode=\zxwhite] at (0,0.9){$G$};
\end{tz}
\quad =\quad 
\begin{tz}[zx,every to/.style={out=up, in=down},scale=1,xscale=-1]
\draw (0,0) to (0,3);
\draw[arrow data={0.2}{>}, arrow data={0.8}{>}] (1.75,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5] {$P$} (-1.75,2.5) to (-1.75,3);
\node[zxnode=\zxwhite] at (0,2.35) {$H$};
\end{tz}
\end{calign}\\[-25pt]
\end{minipage}
\hspace{\bndr}
&
\begin{minipage}{\wtext}\begin{center} quantum \\ graph\\iso.\end{center} \end{minipage}\\ \nonumber&\nonumber&&\\ \hline\end{array}$$

Background {#sec:background}
==========

Gelfand duality
---------------

Our approach to defining a theory of quantum sets and quantum functions is based on *Gelfand duality*.

\[thm:gelfandduality\] The category of commutative $C^*$-algebras and -morphisms is equivalent to the opposite of the category of compact Hausdorff spaces and continuous functions.

The equivalence takes a space to the algebra of continuous complex-valued functions on that space; in the other direction, a $C^*$-algebra is taken to its spectrum. In some sense, therefore, one may consider the theory of compact Hausdorff spaces — classical topology — to be the theory of commutative $C^*$-algebras.

The idea of noncommutative geometry is to consider *noncommutative* in light of Gelfand duality, thus enabling us to study the ‘noncommutative’ or ‘quantum’ spaces to which they would be dual. In this paper, we consider only finite discrete spaces and finite-dimensional $C^*$-algebras. In this case, Theorem \[thm:gelfandduality\] reduces to the following statement.

\[cor:finiteGelfandduality\] The category of finite-dimensional commutative $C^*$-algebras and $*$-homomorphisms is equivalent to the opposite of the category of finite sets and functions.

The string diagram calculus
---------------------------

In order to investigate finite Gelfand duality and its noncommutative generalisation, we make use of the string diagram calculus for monoidal categories. This calculus is well established and has been treated in detail elsewhere [@Joyal1991a; @Joyal1991b; @Selinger2010; @Coecke2010]; here we only provide a brief and informal introduction. We remark that this calculus is quite general. Although we only consider the graphical calculus of , the category of finite-dimensional Hilbert spaces and linear maps, most of what we prove holds in the general setting of dagger compact categories [@Kelly1972; @Kelly1980; @Abramsky2004].

In the string diagram calculus

, wires correspond to finite-dimensional Hilbert spaces and boxes correspond to linear maps.

We read diagrams from bottom to top.

Composition and tensor product are depicted as follows:

(0,0) to (0,3.5); at (0,1.05) [$f$]{}; at (0,2.45) [$g$]{}; at (0,0)[$V_1$]{}; at (0, 1.75) [$V_2$]{}; at (0, 3.5) [$V_3$]{};

&

(0,0) to (0,3.5); (1.5,0) to (1.5,3.5); at (0,1.75) [$f$]{}; at (1.5,1.75) [$g$]{}; at (0,0)[$V_1$]{}; at (1.5, 0) [$V_3$]{}; at (0, 3.5) [$V_2$]{}; at (1.5, 3.5) [$V_4$]{};

\
gf:V\_1V\_3 & fg: V\_1V\_3V\_2V\_4

All finite-dimensional Hilbert spaces $V$ have dual spaces $V^*=\Hom(V,\mathbb{C})$, represented in the graphical calculus as an oriented wire with the opposite orientation as $V$. Duality is characterized by the following linear maps, here called *cups and caps*:

\[eq:cupscapsHilb\]

(0,0) to \[out=up, in=up, looseness=2.5\] (2,0) ; at (2.05,0) [$\pv V$]{}; at (0,0) [$V^*$]{};

&

(0,0) to \[out=up, in=up, looseness=2.5\] (2,0) ; at (2.0,0) [$\pv V$]{}; at (0,0) [$V^*$]{};

&

(0,0) to \[out=up, in=up, looseness=2.5\] (2,0) ; at (2.0,0) [$\pv V$]{}; at (0,0) [$V^*$]{};

&

(0,0) to \[out=up, in=up, looseness=2.5\] (2,0) ; at (2.05,0) [$\pv V$]{}; at (0,0) [$V^*$]{};

\
fv f(v) &  1\_V & vff(v) &   1\_V

To define the second and fourth map, we have identified $V\otimes V^* \cong V^*\otimes V \cong\End(V)$. It may be verified that these maps fulfill the following *snake equations*:

\[eq:snake\]

(0,0) to (0,1) to \[out=up, in=up, looseness=2\] (1,1) to \[out=down, in=down, looseness=2\] (2,1) to (2,2);

   =   

(0,0) to (0,2);

   =    

(0,0) to (0,1) to \[out=up, in=up, looseness=2\] (1,1) to \[out=down, in=down, looseness=2\] (2,1) to (2,2);

&

(0,0) to (0,1) to \[out=up, in=up, looseness=2\] (1,1) to \[out=down, in=down, looseness=2\] (2,1) to (2,2);

    =   

(0,0) to (0,2);

   =    

(0,0) to (0,1) to \[out=up, in=up, looseness=2\] (1,1) to \[out=down, in=down, looseness=2\] (2,1) to (2,2);

Together with the swap map $\sigma_{V,W}:\ignore{V\otimes W\to W\otimes V$,~$}v\otimes w\mapsto w\otimes v$, depicted as a crossing of wires, this leads to an extremely flexible topological calculus, allowing us to untangle arbitrary diagrams and straighten out any twists:

&

(0,0) to \[out=up, in=right\] (-1.25, 2.25) to \[out=left, in=left, looseness=1\] (-1.25,0.75) to \[out=right, in=down\] (0,3);

   =   

(0,0) to (0,3);

   =   

(0,0) to \[out=up, in=right\] (-1.25, 2.25) to \[out=left, in=left, looseness=1\] (-1.25,0.75) to \[out=right, in=down\] (0,3);

Given a linear map $f:V\to W$ between Hilbert spaces, we can express its adjoint as a reflection of the corresponding diagram across a horizontal axis. This is justified, since the following holds:

(  

(0,0) to \[out=up, in=up, looseness=2.5\] (2,0) ;

  )\^   =   

(0,0) to \[out=up, in=up, looseness=2.5\] (2,0) ;

& (  

(0,0) to \[out=up, in=up, looseness=2.5\] (2,0) ;

  )\^   =   

(0,0) to \[out=up, in=up, looseness=2.5\] (2,0) ;

The following generalisation will be important in what follows.

\[def:daggerduality\]Let $V$ and $W$ be Hilbert spaces. A *dagger duality* between $V$ and $W$ is given by linear maps $\epsilon: W\otimes V \to \mathbb{C}$ and $\eta: \mathbb{C} \to V\otimes W$ fulfilling the snake equations  and such that the following holds: $$\label{eq:daggerduality}
\begin{tz}[zx]
\draw (0,0) to (0,1.25);
\draw (1.5,0) to (1.5,1.25);
\draw (-0.2,0) rectangle (1.7, -0.8);
\node[scale=0.8] at (0.75,-0.4) {$\epsilon^\dagger$};
\node[dimension, left] at (0,1.25){$W$};
\node[dimension, right] at (1.5,1.25) {$V$};
\end{tz}
~~~=~~~
\begin{tz}[zx]
\draw (0,0) to [out=up, in=down] (1.5,1.25);
\draw (1.5,0) to [out=up, in=down](0,1.25);
\draw (-0.2,0) rectangle (1.7, -0.8);
\node[scale=0.8] at (0.75,-0.4) {$\eta$};
\node[dimension, left] at (0,1.25){$W$};
\node[dimension, right] at (1.5,1.25) {$V$};
\end{tz}$$

The cups and caps defined in are dagger duals. Dagger dualities are unique up to a unique unitary map [@Selinger2007 Section 7], meaning that if $V$ and $W$ are dagger dual, then there is a unitary map $U: V^*\to W$ such that the following holds:

(-0.6, 1.5) rectangle (2.1, -1.1); (0,0) to (0,1.25); (1.5,0) to (1.5,1.25); (-0.2,0) rectangle (1.7, -0.8); at (0.75,-0.4) [$\eta$]{}; at (0,1.25)[$V$]{}; at (1.5,1.25) [$W$]{};

   =   

(-0.6, 1.5) rectangle (2.1, -1.1); (0,1.25) to (0,0.25) to \[out=down, in=down, looseness=2.5\] (1.5,0.25) to (1.5,1.25); at (1.5, 0.5) [$U$]{}; at (0,1.25)[$V$]{}; at (1.5,1.25) [$W$]{};

&

(-0.6, 1.5) rectangle (2.1, -1.1); (0,0) to (0,1.25); (1.5,0) to (1.5,1.25); (-0.2,0) rectangle (1.7, -0.8); at (0.75,-0.4) [$\epsilon$]{}; at (0,1.25)[$W$]{}; at (1.5,1.25) [$V$]{};

   =   

(-0.6, 1.5) rectangle (2.1, -1.1); (0,1.25) to (0,0.25) to \[out=down, in=down, looseness=2.5\] (1.5,0.25) to (1.5,1.25); at (0, 0.5) [$U^\dagger$]{}; at (0,1.25)[$W$]{}; at (1.5,1.25) [$V$]{};

Diagrams for $C^*$-algebras {#sec:diagramsforC*}
---------------------------

Following Vicary [@Vicary2010], we define $C^*$-algebras in a categorical manner, as dagger Frobenius algebras in the category $\Hilb$.

Of course, algebras can be defined on any vector space, but in order to discuss $C^*$-algebras we require the inner product.

We will refrain from drawing an orientation on the wire corresponding to the Hilbert space on which the algebra is defined, for reasons which will soon become apparent.

\[def:algebra\]An *algebra* is a Hilbert space $H$ with a multiplication and a unit map, depicted as follows:

\(A) at (0,0); (0.75,1) to (0.75,2);

&

\(A) at (0.75,2);

\
m:HH H& u: H

These maps satisfy the following associativity and unitality equations:

\[eq:assocandunitality\]

\(A) at (0.25,0); (1,1) to \[out=up, in=-135\] (1.75,2); (1.75,2) to \[out=-45, in=up\] (3.25,0); (1.75,2) to (1.75,3); at (1.75,2);

=

\(A) at (0.25,0); (1,1) to \[out=up, in=-135\] (1.75,2); (1.75,2) to \[out=-45, in=up\] (3.25,0); (1.75,2) to (1.75,3); at (1.75,2);

&

\(A) at (0,0); (0,-0.25) to (0,0); (0.75,1) to (0.75,2); at (1.5,0);

=

(0,0) to (0,2);

=

\(A) at (0,0); (0,-0.25) to (0,0); (0.75,1) to (0.75,2); at (1.5,0);

Analogously, a *coalgebra* is a Hilbert space $H$ with a coassociative comultiplication $\delta: H \to H\otimes H$ and a counit $\epsilon:H\to \mathbb{C}$. The adjoint of an algebra is a coalgebra.

Note that for the multiplication and unit maps of an algebra we simply draw white nodes rather than labelled boxes, for concision. Likewise, we draw the comultiplication and counit maps of the adjoint coalgebra as white nodes. Despite having the same label in the diagram, they can be easily distinguished by their type.

A *dagger Frobenius algebra* is an algebra where the algebra and adjoint coalgebra structures are related by the following Frobenius equation: $$\label{eq:Frobenius}
\begin{tz}[zx]
\draw (0,0) to [out=up, in=-135] (0.75,2) to (0.75,3);
\draw (0.75,2) to [out=-45, in=135] (2.25,1);
\draw (2.25,0) to (2.25,1) to [out=45, in=down] (3,3);
\node[zxvertex=\zxwhite,zxup] at (2.25,1){};
\node[zxvertex=\zxwhite,zxdown] at (0.75,2){};
\end{tz}
\quad = \quad
\begin{tz}[zx]
\coordinate (A) at (0,0);
\coordinate (B) at (0,3);
\draw (0.75,1) to (0.75,2);
\mult{A}{1.5}{1}
\comult{B}{1.5}{1}
\end{tz}
\quad = \quad 
\begin{tz}[zx]
\draw (0,0) to [out=up, in=-135] (0.75,2) to (0.75,3);
\draw (0.75,2) to [out=-45, in=135] (2.25,1);
\draw (2.25,0) to (2.25,1) to [out=45, in=down] (3,3);
\node[zxvertex=\zxwhite,zxup] at (2.25,1){};
\node[zxvertex=\zxwhite,zxdown] at (0.75,2){};
\end{tz}$$ A Frobenius algebra is *special*, *symmetric* or *commutative* if one of the following additional equations holds:

\[eq:special\]

(0,0) to (0,1) to \[out=135\] (-0.75,2) to \[in=-135\] (0,3) to (0,4); (0,1) to \[out=45\] (0.75,2) to \[in=-45\] (0,3); at (0,1); at (0,3);

=

(0,0) to +(0,4);

&

(0.25,-1.5) to (1.75,0) to \[in=-45\] (1,1) to (1,1.5); (1.75,-1.5) to (0.25,0) to \[in=-135\] (1,1); at (1,1); at (1,1.5);

=

(1.75,-1.5) to (1.75,0) to \[in=-45\] (1,1) to (1,1.5); (0.25,-1.5) to (0.25,0) to \[in=-135\] (1,1); at (1,1); at (1,1.5);

&

(0.25,-1.5) to (1.75,0) to \[in=-45\] (1,1) to (1,2); (1.75,-1.5) to (0.25,0) to \[in=-135\] (1,1); at (1,1);

=

(1.75,-1.5) to (1.75,0) to \[in=-45\] (1,1) to (1,2); (0.25,-1.5) to (0.25,0) to \[in=-135\] (1,1); at (1,1);

\
&&

In this work, we will focus on special symmetric and special commutative dagger Frobenius algebras, which we abbreviate as s and s, respectively.

Frobenius algebras are closely related to dualities. In particular, it is a direct consequence of  and  that the following cups and caps fulfill the snake equations :

\[eq:cupcapfrob\]

(-0.1,0) rectangle (2.1,2.); (0,0) to \[out=up, in=up, looseness=2\] node\[zxvertex=, pos=0.5\] (2,0);

 := 

(-0.1,0) rectangle (2.1,2.2); (0,0) to \[out=up, in=up, looseness=2\] node\[front,zxvertex=, pos=0.5\](A) (2,0); (A.center) to (1,1.8); at (1,1.8) ;

&

(-0.1,0) rectangle (2.1,2.); (0,0) to \[out=up, in=up, looseness=2\] node\[zxvertex=, pos=0.5\] (2,0);

 := 

(-0.1,0) rectangle (2.1,2.2); (0,0) to \[out=up, in=up, looseness=2\] node\[front,zxvertex=, pos=0.5\](A) (2,0); (A.center) to (1,1.8); at (1,1.8) ;

It follows that every Frobenius algebra is canonically self-dual, $A^*\cong A$; we therefore do not need to draw an orientation on the corresponding wire.

A major reason for defining these structures is the fact that $\F$s coincide with finite-dimensional $C^*$-algebras.

Every finite-dimensional $C^*$-algebra has an inner product making it into a special symmetric dagger Frobenius algebra. Conversely, every $\F$ $A$ admits a norm such that the canonical involution, defined by its action on vectors $\ket{a}\in A$ as the following antihomomorphism, endows it with the structure of a $C^*$-algebra:

(0.25,3) to (0.25,1); at (0.25,1) [$a$]{};

(0.25,3) to (0.25,2) to \[out=down, in=135\] (1,1) to \[out=45, in=down\] (1.75,2); (1,1) to (1,0.5); at (1.75,2) [$a^\dagger$]{}; at (1,1); at (1,0.5);

\

One advantage of explicitly using $\F$s over $C^*$-algebras is that $\F$s already contain ‘up-front’ all emergent structures of finite-dimensional $C^*$-algebras, such as the comultiplication $\Delta = m^\dagger : H\to H \otimes H$; they are therefore more amenable to the purely compositional reasoning of the graphical calculus. Notions from the theory of , such as $*$-homomorphisms, can be reformulated in the language of s.=-2

\[def:starhoms\]A *$*$-homomorphism* between s $A$ and $B$ is a linear map $f:A\to B$ satisfying the following equations:

\[eq:homo\]

(0,0) to (0,2) to \[out=135\] (-0.75,3); (0,2) to \[out=45\] (0.75, 3); at (0,1) [$f$]{}; at (0,2) ;

=

(0,0) to (0,0.75) to \[out=135\] (-0.75,1.75) to (-0.75,3); (0,0.75) to \[out=45\] (0.75, 1.75) to +(0,1.25); at (-0.75,2) [$f$]{}; at (0.75,2) [$f$]{}; at (0,0.75) ;

&

(0,0) to (0,2) ; at (0,1) [$f$]{}; at (0,2) ;

=

(0,0) to (0,0.75) ; at (0,0.75) ;

&

(0,0) to (0,3); at (0,1.5) [$f^\dagger$]{};

=  

(0,1.5) to (0,2) to \[in=left\] node\[pos=1\] (r) (0.5,2.5) to \[out=right, in=up\] (1,2) to \[out=down, in=up\] (1,0); (-1,3) to \[out=down,in=up\] (-1,1) to \[out=down, in=left\] node\[pos=1\] (l) (-0.5,0.5) to \[out=right, in=down\] (0,1) to (0,1.5); at (0,1.5) [$f$]{}; at (l.center); at (r.center);

A *$*$-cohomomorphism* is a linear map $f:A\to B$ satisfying the following equations:

\[eq:cohomo\]

(0,0) to (0,2) to \[out=135\] (-0.75,3); (0,2) to \[out=45\] (0.75, 3); at (0,1) [$f$]{}; at (0,2) ;

=

(0,0) to (0,0.75) to \[out=135\] (-0.75,1.75) to (-0.75,3); (0,0.75) to \[out=45\] (0.75, 1.75) to +(0,1.25); at (-0.75,2) [$f$]{}; at (0.75,2) [$f$]{}; at (0,0.75) ;

&

(0,0) to (0,2) ; at (0,1) [$f$]{}; at (0,2) ;

=

(0,0) to (0,0.75) ; at (0,0.75) ;

&

(0,0) to (0,3); at (0,1.5) [$f^\dagger$]{};

=  

(0,1.5) to (0,2) to \[in=left\] node\[pos=1\] (r) (0.5,2.5) to \[out=right, in=up\] (1,2) to \[out=down, in=up\] (1,0); (-1,3) to \[out=down,in=up\] (-1,1) to \[out=down, in=left\] node\[pos=1\] (l) (-0.5,0.5) to \[out=right, in=down\] (0,1) to (0,1.5); at (0,1.5) [$f$]{}; at (l.center); at (r.center);

A *$*$-isomorphism* is a linear map $f:A\to B$ which is both a $*$-homomorphism and a $*$-cohomomorphism.

Observe that the adjoint of a $*$-homomorphism is a $*$-cohomomorphism, that every [$*$-isomorphism]{} is unitary, and that every unitary $*$-homomorphism of s is a In particular, a $*$-isomorphism is precisely an invertible \*-homomorphism (see Proposition \[prop:Frobeniusinvertible\] for the converse).

The notion of a $*$-homomorphism between $\F$s coincides with the notion of a $*$-homomorphism between finite-dimensional

Finite-dimensional Gelfand duality in diagrams {#sec:gelfanddiagram}
----------------------------------------------

Having established the graphical calculus and the correspondence between finite-\
dimensional $C^*$-algebras and $\F$s, we now recall the graphical version of finite-dimensional Gelfand duality in the framework established by Coecke, Pavlovi[ć]{} and Vicary [@Coecke2009]. We first observe that every orthonormal basis on a Hilbert space $H$ defines a special commutative dagger Frobenius algebra on $H$.

\[exm:Frob\]Let $\left\{\ket{i}\right\}_{1\leq i\leq n}$ be an orthonormal basis of a Hilbert space $H$. Then the following multiplication and unit maps, together with their adjoints, form a special commutative dagger Frobenius algebra on $H$:

\[eq:classicalcopy\]

\(A) at (0,0); (0.75,1) to (0.75,2);

:=  \_[i=1]{}\^[n]{}    

(0,0) to (0,0.5); (1.5,0) to (1.5,0.5); (0.75,1.5) to (0.75,2); at (0,0.5) [$i^\dagger$]{}; at (1.5,0.5) [$i^\dagger$]{}; at (0.75,1.5) [$i$]{};

&

(0.75,1) to (0.75,2); at (0.75,1);

:=  \_[i=1]{}\^[n]{}

(0.75,1.25) to (0.75,2); at (0.75,1.25) [$i$]{};

\
m: \_[i,j]{} & u: 1 \_[i=1]{}\^[n]{}

Conversely, every special commutative dagger Frobenius algebra $A$ gives rise to an orthonormal basis of $A$; the basis vectors are given by the copyable element of $A$, defined as follows:

\[def:copyablestates\] A *copyable element* of a $\CF$ $A$ is a $*$-cohomomorphism $\psi: \mathbb{C} \to A$; that is, a vector $\ket{\psi} \in A$ such that the following hold[^6]:

\[eq:ordinaryelement\]

(0,1) to (0,2) to \[out=135\] (-0.75,3); (0,2) to \[out=45\] (0.75, 3); at (0,1) [$\psi$]{}; at (0,2) ;

=   

(-0.75,2) to (-0.75,3); (0.75, 2) to +(0,1.); at (-0.75,2) [$\psi$]{}; at (0.75,2) [$\psi$]{};

&

(0,1) to (0,2) ; at (0,1) [$\psi$]{}; at (0,2) ;

  =   &

(0,0) to (0,1.5); at (0,1.5) [$\psi^\dagger$]{};

=   

(0,1.5) to (0,2) to \[in=left\] node\[pos=1\] (r) (0.5,2.5) to \[out=right, in=up\] (1,2) to \[out=down, in=up\] (1,0); at (0,1.5) [$\psi$]{}; at (r.center);

\

These copyable elements indeed form an orthonormal basis of the Hilbert space underlying $A$.

\[thm:classificationONB\]The copyable elements of a special commutative dagger Frobenius algebra $A$ form an orthonormal basis of $A$ for which the algebra is of the form given in Example \[exm:Frob\].

In other words, every special dagger commutative Frobenius algebra is of the form  for some orthonormal basis on a Hilbert space.

Given a $\CF$ $A$, we denote its set of copyable elements by $\widehat{A}$. For $\CF$s $A$ and $B$, it can easily be verified that every function $\widehat{A}\to \widehat{B}$ gives rise to a $*$-cohomomorphism between $A$ and $B$ and that conversely every $*$-cohomomorphism $A\to B$ comes from such a function $\widehat{A} \to \widehat{B}$. Therefore, Theorem \[thm:classificationONB\] gives rise to the following Frobenius algebraic version of finite Gelfand duality:

The category of commutative special dagger Frobenius algebras and $*$-cohomomorphisms[^7] is equivalent to the category of finite sets and functions.

Explicitly, this equivalence maps a $\CF$ $A$ to its set of copyable elements $\widehat{A}$ and a set $X$ to the algebra associated to the orthonormal basis $\{ \ket{x}~|~x\in X\}$ of the Hilbert space $\mathbb{C}^{|X|}$. Under this correspondence, we may therefore consider the category of finite sets as ‘contained within $\Hilb$’ using the following identification.

  $\Set$                        $\mathrm{Hilb}$
  ----------------------------- -----------------------------------
  set of cardinality $n$         of dimension $n$
  elements of the set           copyable states of the
  functions                     $*$-cohomomorphisms
  bijections                    $*$-isomorphisms
  the one element set $\{*\}$   the one-dimensional  $\mathbb{C}$

\[not:setalgebra\] Throughout this paper, we will take pairs of words in this table to be synonymous. In particular, we will denote a set and its corresponding commutative algebra by the same symbol. It will always be clear from context whether we refer to the set $X$ or the algebra $X$.

The fact that the category of finite sets and functions can be faithfully embedded into $\Hilb$ will be central to our quantisation procedure described in the introduction. We formalise this important concept by adopting terminology initially used by Freyd and developed by Ad[á]{}mek and others [@Adamek1990; @Freyd1970].

\[def:Hilbcategory\] A *concrete dagger category* is a pair $(\mathcal{C}, F)$, where $\mathcal{C}$ is a dagger category and $F:\mathcal{C} \to \Hilb$ is a faithful dagger functor, which we refer to as the *forgetful functor*.

In other words, Gelfand duality allows us to treat the category of finite sets and functions as a concrete dagger category.

\[phil:concretedagger\]All categories in this paper are concrete dagger categories, with a forgetful functor specifying an underlying Hilbert space for every object and an underlying linear map for every morphism. The quantum mechanical interpretation of our categories depends on this forgetful functor. We will formulate all categorical concepts in terms of concrete dagger categories, and ensure that they are compatible with the forgetful functor to .

Quantum sets and quantum functions {#sec:quantumset}
==================================

The fundamental idea of noncommutative topology is to generalise the correspondence between spaces and commutative algebras by considering noncommutative algebras in light of Gelfand duality. We will now begin our exploration of the world of finite-dimensional noncommutative algebras, or ‘finite quantum sets’.

By analogy with Gelfand duality, we think of a special symmetric dagger Frobenius algebra as being associated to an imagined finite *quantum set*, just as a commutative special dagger Frobenius algebra is associated to a finite set. We follow Terminology \[not:setalgebra\] and Wang [@Wang1998 page 3] in denoting both the algebra and its associated imagined quantum set by the same symbol.

Quantum elements {#sec:qelem}
----------------

A set is completely determined by its elements. What is the appropriate notion of a *quantum element* of a quantum set? In particular, is there a notion of quantum element such that a quantum set is completely determined by its quantum elements? Copyable states cannot play this role, since it can easily be verified that matrix algebras have no copyable states whatsoever. Adopting the ideas outlined in the introduction, we make the following definition, ‘quantising’ the notion of a copyable state .

\[def:quantumelement\] A *quantum element* of a quantum set $A$ is a pair ($H,Q$), where $H$ is a Hilbert space and $Q: H\to A \otimes H$ is a linear map satisfying the following equations:

\[eq:quantumelement\]

(0,0) to (0,2) to \[out=45\] (0.75,3); (0,2) to \[out=135\] (-0.75,3); (1.75,0) to \[looseness=0.9\] node\[zxnode=, pos=0.5\](Q) [$Q$]{} (-1.75,2.5) to (-1.75,3); at (0,2); (0,0) to (Q.center);

=

(0.75,1.75) to (0.75,3); (-0.75,1.75) to (-0.75,3); (1.75,0) to (1.75,0.75) to \[looseness=1.1, in looseness=0.9\] node\[zxnode=, pos=0.36\] [$Q$]{} node\[zxnode=, pos=0.64\] [$Q$]{}(-1.75,3);

&

(0,0) to (0,2.25); (1,0) to \[looseness=0.9\] node\[zxnode=, pos=0.5\](Q) [$Q$]{} (-1,2.5) to (-1,3); at (0,2.25); (0,0) to (Q.center);

=

(1.,0) to \[looseness=0.9\] (-1,2.5) to (-1,3);

&

(0,0) to (2.25,3); (2.25,0) to \[in=-45\] node\[zxnode=, pos=1\] (Q) [$Q^\dagger$]{} (1.125,1.5);

 =  

(0.25,-0.5) to (0.25,0) to \[out=up, in=-135\] (1,1); (1.75,2.5) to (1.75,2) to \[out=down, in=45\] (1,1); (1,1) to \[out= -45, in= left\] node\[zxvertex=, pos=1\] (2.3,0.3) to \[out=right, in=down\] (3.25,1) to (3.25,2.5); at (1,1) [$Q$]{};

\[phil:quantumprooffromclassical\] The axioms defining a quantum element  look just like the axioms defining an ordinary element  with an additional oriented wire. This will be a guiding principle for the graphical calculus in this work. Many of the calculations presented here were derived in the ‘classical’ setting with an additional oriented wire only added later. Here, and in what follows, we always draw this additional wire with an orientation, while we draw the original wire — carrying a Frobenius algebra structure — without orientation (see also the discussion after ).

We have drawn the Hilbert space wires from the bottom left to the top right. This is just a convention, and we could equally have defined quantum elements — and later quantum functions — using the opposite convention.

We will show in Proposition \[prop:reconstruct\] that every quantum set is completely determined by its quantum elements, thereby justifying Definition \[def:quantumelement\].

\[rem:operationalinterpretationofquantumels\] If $X$ is an ordinary set (that is, a $\CF$), then it follows that a quantum element of $X$ is a projective measurement with outcomes in $X$ (see Corollary \[cor:quantumelementmeasurement\]). The first diagram of  corresponds to orthogonality and idempotency; the second to completeness; and the third to self-adjointness. This diagrammatic representation of projective measurements has been known at least since the work of Coecke and Pavlovi[ć]{} [@Coecke2007]. A direct operational intepretation of  has recently been

\[rem:interpretationquantumelement\] A (non-probabilistic, discrete) classical observable can be thought of both as a process $x:\{*\} \to \{*\} \times X$ producing an element of a set $X$ from a trivial system — that is, a process picking out one and only one element — or simply as an element $x\in X$.=-2

Similarly, a quantum observable can either be thought of as projective measurement $P:H\to X\otimes H$ producing an element of $X$ from an underlying quantum mechanical system $H$ or simply as a *quantum element* $P\in_Q X$, shifting attention away from the underlying Hilbert space. This is similar in spirit to random variables in probability theory which are defined as functions $x$ from an underlying probability space to a set $X$, but are usually thought of as random elements of this set $x\in_R X$.

This perspective is reflected in our quantisation approach: By appending a Hilbert space wire to a diagram defining some set-theoretic concept, we retain any operational interpretation, only now allowing the relevant processes to make use of an underlying quantum mechanical system. This is similar to quantisation in the sense of nonlocal games, where classical concepts are quantised by formulating them as strategies for multi-player games and allowing the use of an additional shared quantum resource [@Atserias2016]. As we will see in Section \[sec:quantumperm\] and \[sec:qgt\], our approach to quantisation indeed leads to the same concepts as those appearing in the study of such nonlocal games.

Due to the presence of the additional Hilbert space wire introduced in our quantisation procedure, we are led to consider maps on this Hilbert space, which interact in a particular way with quantum elements.

An *intertwiner* of quantum elements $(H,Q) \to (H', Q')$ is a linear map $f:H\to H'$ such that the following holds:$$\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (1,2)to [out=45] (2,3);
\draw[arrow data={0.35}{>}] (2,0) to node[zxnode=\zxwhite, pos=0.9] {$f$} (2,1);
\draw[string,arrow data={0.9}{>},arrow data={0.26}{>}](2,1) to node[zxnode=\zxwhite, pos=0.5]{$Q'$}  (0,3);
\end{tz}
\quad = \quad
\begin{tz}[zx,every to/.style={out=up, in=down},scale=-1,xscale=-1]
\draw (0,0) to (0,1) to [in=-135] (1,2);
\draw[arrow data={0.35}{<}] (2,0) to node[zxnode=\zxwhite, pos=0.9] {$f$} (2,1);
\draw[string,arrow data={0.9}{<},arrow data={0.26}{<}](2,1) to node[zxnode=\zxwhite, pos=0.5]{$Q$}  (0,3);
\end{tz}$$

Note that, in the case of classical elements , all linear maps $\C \to \C$ are scalars and commute trivially with the element, providing us with no information about its structure; intertwiners therefore only become relevant in the quantum setting.

Let $Q$ be a quantum element of a classical set $X$; in other words, a projective measurement with outcomes in $X$ (see Remark \[rem:operationalinterpretationofquantumels\]). In this case, examples of intertwiners $Q\to Q$ are given by projectors onto subspaces which are left undisturbed by the measurement. We will show in Section \[sec:semisimple\] that all intertwiners between quantum elements may be understood in this way.

As we will see, much of the structural difference between the classical and the quantum setting can be understood in terms of the existence or non-existence of such intertwiners. While ordinary elements form a set, quantum elements should properly be organized into a category, to keep track of the intertwiners.

\[def:intertwinerofelements\]For a quantum set $A$, we define the category (A) of quantum elements of $A$:

-   **objects** are quantum elements $(H,Q)$ of $A$;

-   **morphisms** $(H,Q) \to (H', Q')$ are intertwiners of quantum elements.

Composition of intertwiners is ordinary composition of linear maps.

Every category of quantum elements comes with a forgetful functor $F:\QEl(A) \to \Hilb$ mapping a quantum element to its underlying Hilbert space and an intertwiner to the underlying linear map. This underlying structure makes $(\QEl(A),F)$ a concrete dagger category as in Definition \[def:Hilbcategory\].

We now justify our definition of quantum elements by showing that a quantum set is completely determined by its concrete dagger category of quantum elements.

\[prop:reconstruct\] Up to isomorphism, a quantum set $A$ can be reconstructed from its category of elements $\QEl(A)$ and the forgetful functor $F:\QEl(A)\to \Hilb$.

By definition, $\QEl(A)$ is the category of left comodules of the special symmetric dagger Frobenius algebra $A$ and as such equivalent to the category of modules of $A$. The proposition therefore follows from existing results on Tannaka duality, which states that a semisimple algebra can be reconstructed from its category of modules and a forgetful (or fibre) functor (cf. [@Joyal1991]).

Explicitly, we can reconstruct the algebra $A$ as follows:

\[eqn:quantumcopy\]

(0.25,-0.25) to (0.25,0) to \[out=up, in=-135\] (1,1) to (1,2.25); (1.75,-0.25) to (1.75,0) to \[out=up, in=-45\] (1,1); at (1,1) ;

=   \_[i]{}   

(0.25,-0.25) to node\[zxnode=, pos=0.46\] [$i^\dagger$]{}(0.25,1); (1.75,-0.25) to node\[zxnode=, pos=0.82\] [$i^\dagger$]{} (1.75,1); (1,1) to node\[zxnode=, pos=0.35\] [$i$]{} (1,2.25); (-0.5,1) to \[out=down, in=-135\] (-0.05,0.05) to \[in looseness=0.3,out=45, in=down\] (2.25,1.) to \[out looseness=0.3,out=up, in=-45\] (-0.05,1.95) to \[out=135, in=up\] (-0.5,1);

&

(1,1) to (1,2.25); at (1,1);

 =  \_i  

(1,1) to node\[zxnode=, pos=0\] [$i$]{} (1,2.25); (1,1) to \[looseness=3.5, out=135, in=135\] (0.25,0.25) to \[out=-45, in=-45, looseness=3.5\] (1,1);

Here the sum ranges over the *simple quantum elements*, which we define in Section \[sec:semisimple\]. The equations  can be understood as a quantisation of equations .

Quantum functions {#sec:funct}
-----------------

Having defined quantum elements of quantum sets, we now consider the appropriate notion of quantum functions between them. We define these by quantisation of

\[def:quantumfunction\] A *quantum function* between quantum sets $A$ and $B$ is a pair ($H,P$), where $H$ is a Hilbert space and $P$ is a linear map $H\otimes A\! \to\! B \otimes H$ satisfying the =-2

\[eq:quantumfunction\]

(0,0) to (0,2) to \[out=45\] (0.75,3); (0,2) to \[out=135\] (-0.75,3); (1.75,0) to \[looseness=0.9\] node\[zxnode=, pos=0.5\] [$P$]{} (-1.75,2.5) to (-1.75,3); at (0,2);

=

(0,0) to (0,0.75) to \[out=45\] (0.75,1.75) to (0.75,3); (0,0.75) to \[out=135\] (-0.75,1.75) to (-0.75,3); (1.75,0) to (1.75,0.75) to \[looseness=1.1, in looseness=0.9\] node\[zxnode=, pos=0.36\] [$P$]{} node\[zxnode=, pos=0.64\] [$P$]{}(-1.75,3); at (0,0.75);

&

(0,0) to (0,2.25); (1,0) to \[looseness=0.9\] node\[zxnode=, pos=0.5\] [$P$]{} (-1,2.5) to (-1,3); at (0,2.25);

=

(0,0) to (0,0.75); (1.,0) to (1.,0.75) to (-1,3); at (0,0.75);

&

(0,0) to (2.25,3); (2.25,0) to node\[zxnode=, pos=0.5\] [$P^\dagger$]{} (0,3);

=  

(0.25,-0.5) to (0.25,0) to \[out=up, in=-135\] (1,1); (1,1) to \[out=135, in=right\] node\[zxvertex=, pos=1\] (-0.3, 1.7) to \[out=left, in=up\] (-1.25,1) to (-1.25,-0.5); (1.75,2.5) to (1.75,2) to \[out=down, in=45\] (1,1); (1,1) to \[out= -45, in= left\] node\[zxvertex=, pos=1\] (2.3,0.3) to \[out=right, in=down\] (3.25,1) to (3.25,2.5); at (1,1) [$P$]{};

The diagrammatic representation of quantum functions provides an interesting topological intuition: a quantum function behaves like a braiding or crossing between the directed and the undirected wire. From this perspective,  allows us to pull the comultiplication and counit through the braiding. Note that we cannot yet pull the multiplication and unit through the braiding; adding these additional pull-throughs defines a quantum bijection, as will be seen in Section \[sec:quantumbijection\].

\[rem:opintofquantumfunctions\] We show in Corollary \[cor:quantumelementmeasurement\] that quantum functions $X\to Y$ between classical sets are families of projective measurements with outcomes in $Y$, controlled by the set $X$. We can think of this as a non-deterministic function $X \to Y$ which uses quantum measurements on an underlying Hilbert space to determine the output $y \in Y$ for a given input $x \in X$ (cf. Remark \[rem:interpretationquantumelement\]).

Having defined quantum functions, we make the following elementary observations.

A quantum element of a quantum set $A$ is a quantum function from the one-element [set $\{*\}$]{} (or equivalently from the commutative special dagger Frobenius algebra $\mathbb{C}$) to the quantum set $A$.

is a special case of where the source is the trivial quantum set.

We also note that quantum functions map quantum elements to quantum elements:$$\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,3.5);
\draw[arrow data={0.2}{>}, arrow data={0.8}{>}] (1.75,0) to [looseness=0.8] node[zxnode=\zxwhite, pos=0.46](Q) {$Q$} (-2.25,2.5) to (-2.25,3.5);
\draw[string,arrow data={0.35}{>}, arrow data={0.9}{>}] (3,0)  to (3,0.25)to [in looseness=0.7] node[zxnode=\zxwhite, pos=0.67](Q2) {$P$}  (-1,3.25) to (-1,3.5);
\draw[white,double] (0,0) to (Q.center);
\end{tz}$$ In particular, a quantum function between quantum sets $A$ and $B$ induces a functor between their categories of quantum elements.

\[def:qfctdimension\]We define the *dimension* of a quantum function $(H,P)$ to be the dimension of the underlying Hilbert space $H$.

A one-dimensional quantum function is an ordinary $*$-cohomomorphism of Frobenius algebras, as can be seen by comparing  with . By Gelfand duality, a one-dimensional quantum function between classical sets is therefore just a function.

We can extend the notion of an intertwiner of quantum elements to all =-2

\[def:intertwiner\] An *intertwiner* of quantum functions $(H,P) \to (H', P')$ is a linear map $f:H\to H'$ such that the following holds:

(0,0) to (0,1) to (2,3); (2,0) to node\[zxnode=, pos=0.9\] [$f$]{} (2,1); (2,1) to node\[zxnode=, pos=0.5\][$P'$]{} (0,3);

=

(0,0) to (0,1) to (2,3); (2,0) to node\[zxnode=, pos=0.9\] [$f$]{} (2,1); (2,1) to node\[zxnode=, pos=0.5\][$P$]{} (0,3);

The 2-category $\QSet$
----------------------

We have seen in the discussion preceding Definition \[def:intertwiner\] that, while classical elements form a set, quantum elements should be organized into a *category*, keeping track of the additional layer of structure introduced by the intertwiners.

We thus expect the quantum analogue of the category of sets and functions to be a *2-category* of quantum sets and quantum functions, keeping track of the intertwiners between quantum functions.

Overall, we observe that our approach to quantisation leads to

\[def:2catqset\] The 2-category[^8] $\QSet$ is built from the following structures:

-   **objects** are quantum sets $A,B$, ...;

-   **1-morphisms** $A\to B$ are quantum functions $(H,P): A\to B$;

-   **2-morphisms** $(H,P) \to (H', P')$ are intertwiners of quantum functions.

The composition of two quantum functions $(H,P):A\to B$ and $(H', Q): B \to C$ is a quantum function $(H' \otimes H, Q\circ P)$ defined as follows:

\[eq:1composition\] (1.575,0) to (0.325,3.5); (2.175,0) to (0.925,3.5); (0,0) to node\[zxvertex=, pos=0.5\] [$Q\circ P$]{} (2.5,3.5); at (4.4,0) [$H' \otimes H$]{};

:=

(0,0) to (2.5,3.5); (1.25,0) to node\[zxnode=, pos=0.4\] [$P$]{} (0,3.5); (2.5,0) to node\[zxnode=, pos=0.58\] [$Q$]{} (1.25,3.5); at (1.25,0) [$H$]{}; at (2.5,0) [$H'$]{};

Vertical and horizontal composition of 2-morphisms is defined as the ordinary composition and tensor product of linear maps, respectively.

As expected, we observe that $\QSet(*,A) = \QEl(A)$ where $*$ is the one-element set (cf. Terminology \[not:setalgebra\]).

\[rem:street\] We denote by $\BHilb$ the *delooping* of $\Hilb$; that is, the 2-category with a single object $*$ and endomorphism category $\Hom(*,*)=\Hilb$. We observe that $\QSet$ is a sub-2-category of Street’s 2-category $\mathrm{CoMnd}(\BHilb)$ of comonads, comonad maps and comonad transformations in the 2-category $\BHilb$ [@Street1972]. Indeed, the first two equations of  can be understood as defining a comonad map (an analogous graphical definition of the 2-category $\mathrm{Mnd}(\Cat)$ of monads in the 2-category of categories, functors and natural transformations is given in [@Marsden2014; @Hinze2016]).

\[thm:QSetdagger2category\] $\QSet$ is a dagger 2-category.

Following Remark \[rem:street\], $\QSet$ is a sub-2-category of $\mathrm{CoMnd}(\BHilb)$, which is well known to be a 2-category (in the strict case the proof goes back at least to Street [@Street1972]). The dagger of a 2-morphism is defined to be the ordinary Hilbert space adjoint of the underlying linear map. This is well defined since the adjoint of an intertwiner $f:(H,P) \to (H', Q)$ is an intertwiner $f^\dagger: (H', Q) \to (H,P)$: $$\label{eq:qsetdagger}\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,1) to (2,3);
\draw[string, arrow data={0.35}{>}] (2,0) to node[zxnode=\zxwhite, pos=0.9] {$f$} (2,1);
\draw[string,arrow data={0.9}{>},arrow data={0.26}{>}](2,1) to node[zxnode=\zxwhite, pos=0.5]{$Q$}  (0,3);
\end{tz}
~=~
\begin{tz}[zx,every to/.style={out=up, in=down},scale=-1,xscale=-1]
\draw (0,0) to (0,1) to (2,3);
\draw[arrow data={0.35}{<}] (2,0) to node[zxnode=\zxwhite, pos=0.9] {$f$} (2,1);
\draw[string,arrow data={0.9}{<},arrow data={0.26}{<}](2,1) to node[zxnode=\zxwhite, pos=0.5]{$P$}  (0,3);
\end{tz}
\quad
\stackrel{~(-)^\dagger}{\Leftrightarrow}
\quad
%%%%%%%%%%%
\begin{tz}[zx,every to/.style={out=up, in=down},yscale=-1,xscale=-1]
\draw (0,0) to (0,1) to (2,3);
\draw[arrow data={0.35}{<}] (2,0) to node[zxnode=\zxwhite, pos=0.9] {$f^\dagger$} (2,1);
\draw[string,arrow data={0.9}{<},arrow data={0.26}{<}](2,1) to node[zxnode=\zxwhite, pos=0.5]{$Q^\dagger$}  (0,3);
\end{tz}
=
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=1]
\draw (0,0) to (0,1) to (2,3);
\draw[arrow data={0.35}{>}] (2,0) to node[zxnode=\zxwhite, pos=0.9] {$f^\dagger$} (2,1);
\draw[string,arrow data={0.9}{>},arrow data={0.26}{>}](2,1) to node[zxnode=\zxwhite, pos=0.5]{$P^\dagger$}  (0,3);
\end{tz}
\quad
\super{\eqref{eq:quantumfunction}}{\Leftrightarrow}
\quad
\begin{tz}[zx,every to/.style={out=up, in=down},scale=-1,xscale=-1]
\draw (0,0) to (0,1) to (2,3);
\draw[arrow data={0.35}{<}] (2,0) to node[zxnode=\zxwhite, pos=0.9] {$f^\dagger$} (2,1);
\draw[string,arrow data={0.9}{<},arrow data={0.26}{<}](2,1) to node[zxnode=\zxwhite, pos=0.5]{$Q$}  (0,3);
\end{tz}
~=~
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,1) to (2,3);
\draw[arrow data={0.35}{>}] (2,0) to node[zxnode=\zxwhite, pos=0.9] {$f^\dagger$} (2,1);
\draw[string,arrow data={0.9}{>},arrow data={0.26}{>}](2,1) to node[zxnode=\zxwhite, pos=0.5]{$P$}  (0,3);
\end{tz}$$

The underlying Hilbert space of the composite of two quantum functions is the tensor product of the underlying Hilbert spaces of the quantum functions. Similarly, vertical and horizontal composition of 2-morphisms coincides with composition and tensor product of linear maps. We therefore have a forgetful 2-functor $$\label{eq:fibrefunctor}F: \QSet \to \BHilb$$ from $\QSet$ to the delooping of $\Hilb$ (see Remark \[rem:street\]). As outlined in Philosophy \[phil:concretedagger\], the quantum mechanical interpretation of  depends on this 2-functor; in particular, it makes $\QSet$ into a concrete dagger 2-category.

\[def:Hilb2category\] A *concrete dagger 2-category* is a pair $(\mathbb{B}, F)$, where $\mathbb{B}$ is a dagger 2-category and $F:\mathbb{B} \to \BHilb$ is a locally faithful dagger 2-functor (see Section \[sec:background\]).

In particular, a *concrete dagger monoidal category* is a pair $(\mathcal{C}, F)$ where $\mathcal{C}$ is a dagger monoidal category and $F:\mathcal{C} \to \Hilb$ is a faithful dagger monoidal functor.

In other words, a concrete dagger 2-category is a $2$-category for which every $\Hom$-category is a concrete dagger category in a compatible way. The 2-functor $F:\QSet\to \BHilb$ has in fact already appeared in Proposition \[prop:reconstruct\].

\[rem:setsubset\] By Gelfand duality, every set is itself a quantum set and every function is a quantum function. We may therefore think of $\Set$ as contained in $\QSet$; there is a faithful inclusion $2$-functor $\Set\hookrightarrow \QSet$, where we think of $\Set$ as a $2$-category with only identity $2$-morphisms.

Given two functions $f$ and $g$ between sets, $\QSet(f,g) = \delta_{f,g} \mathbb{C}$.

\[rem:symmmon2cat\] Using the cartesian product of sets, the category of sets and functions is a symmetric monoidal category. Similarly, it can be shown that , using the tensor product of the underlying algebras, becomes a symmetric monoidal 2-category.

A universal property {#sec:universal}
--------------------

In this section, we show that the categories of quantum functions $A \to B$ between quantum sets may be obtained via a universal construction, as categories of

quantum elements of the internal hom $[A,B]$ in the category of *quantum spaces* — the opposite of the category of $C^*$-algebras. Our definition of the quantum space of quantum functions between finite quantum sets is analogous to [@Soltan2009 Definition 3.1.], and generalises the construction used to define quantum permutation groups [@Wang1998].

To present these results, we work with infinite-dimensional $C^*$-algebras. Various parts of our presentation in Sections \[sec:background\] and \[sec:quantumset\] do not apply here (for instance, there are no infinite-dimensional Frobenius algebras), and we will therefore need to modify some definitions. Any such modifications will apply only in this section.

It is an observation of Wang [@Wang1998] that quantum functions between classical spaces should form a quantum set rather than a classical set. Let $\CAlg$ be the category of (possibly infinite-dimensional) $C^*$-algebras and $*$-homomorphisms. By analogy with Gelfand duality, we might treat the category $\CAlg^\op$ as the category of ‘quantum spaces’. However, given two finite sets $A$ and $B$, understood as commutative $C^*$-algebras, then $\CAlg^\op (A,B) =\Set(A,B)$ is just a set; from this perspective there are only classical functions between $A$ and $B$. This inspires the following definition, analogous to constructions in [@Wang1998] and [@Soltan2009].

\[def:internalhom\]

The *quantum space of quantum functions* between two finite quantum sets $A$ and $B$ is the internal hom $[A,B]$ in $\CAlg^\op$; that is, the universal $C^*$-algebra such that there are bijections[^9] $$\label{eq:internalhom}\CAlg^\op (C, [A,B]) \cong \CAlg^\op (C\otimes A, B)$$ which are natural in $C\in \CAlg^\op$.

\[rem:soltan\] Sołtan’s *quantum space of all maps* between two quantum spaces [@Soltan2009 Definition 3.1.] is precisely the internal hom in the category $\CAlg^\op$. It follows from [@Soltan2009 Theorem 3.3] that the quantum space of quantum functions between finite quantum sets always exists.

The internal hom $[A,B]$ is in general an infinite-dimensional noncommutative $C^*$-algebra. In the finite-dimensional case, we showed that a quantum set could be recovered from its category of quantum elements. In the infinite-dimensional setting we cannot define the category of quantum elements as the category of comodules, due to the lack of a comultiplication on $[A,B]$. We can nevertheless define the category of quantum elements of $[A,B]$ as the *opposite* of the category of modules of $[A,B]$; this coincides with the usual definition in the finite-dimensional case.

The *category of finite quantum elements* $\QEl(A)$ of a quantum space $A$ is the opposite of the category $\mathrm{Rep}_{\text{fd}}(A)$ of finite-dimensional $C^*$-representations[^10] of the $C^*$-algebra $A$.

We now show that our category of quantum functions between finite quantum sets $A$ and $B$ coincides with the category of quantum elements of the internal hom $[A,B]$.

\[thm:universalprop\] The category of finite quantum elements of $[A,B]$ is equivalent to the category of quantum functions $\QSet(A,B)$: $$\QEl([A,B]) \cong \QSet(A,B)$$

We need to show that $\mathrm{Rep}_{\text{fd}}([A,B])^\op \cong \QSet(A,B)$. A representation of $[A,B]$ is a $*$-homomorphism $[A,B]\to \End(H)$ for some finite-dimensional Hilbert space. We have the following series of bijections: $$\label{eq:universalsequence}\CAlg([A,B], \End(H)) = \CAlg^\op(\End(H),[A,B])$$$$\hspace{1cm}\cong \CAlg^\op(\End(H)\otimes A, B) = \CAlg(B, \End(H)\otimes A)$$ The representation therefore corresponds to a $*$-homomorphism $B\to \End(H) \otimes A$. Since all algebras $A,B$ and $\End(H)$ are finite-dimensional, we can now use the Frobenius algebra formalism established in Section \[sec:background\]. Taking the Hilbert space adjoint of the homomorphism $B\to \End(H)\otimes A$ yields a $*$-cohomomorphism (in the sense of equation ) $P:\End(H)\otimes A\to B$. Explicitly, this means:

(0,0) to (0,0.5) to \[out=135\] (-0.75, 1.5) to (-0.75,1.7); (0, 0.5) to \[out=45\] (0.75,1.5) to (0.75,1.7); (-2\*, 0)to (-2\*, ) to(-0.75-2\*, 1.7); (-, 0) to (-,) to (0.75-, 1.7) to (0.75-, 3); (-0.75-, 1.8) to (-0.75-, 3); (-0.75-, 1.7) to \[out=down, in=down,looseness=1.6\] (0.75-2\*, 1.7) ; at (0.75-, 1.8) [$P$]{}; at (-0.75-, 1.8) [$P$]{}; at (0,0.5);

=

(-,0) to (-,1); (0,0) to (0,1); (,0) to (,1); (0,1) to (0,2) to \[out=135\] (-0.75, 3); (0,2) to \[out=45\] (0.75,3); at (0,1) [$P$]{}; at (0,2);

&

(-,0) to (-,1); (0,0) to (0,1); (,0) to (,1); (0,1) to (0,2); at (0,1) [$P$]{}; at (0,2);

= 

(-,0) to (-,0.5) to \[out=up, in=up\] (0,0.5) to (0,0); (,0) to (,1); at (,1);

&

(-0.5, 0) rectangle (0.5,3); (-,0) to (-,1.5); (0,0) to (0,1.5); (,0) to (,1.5); (0,1.5) to (0,3); at (0,1.5) [$P^\dagger$]{};

 = 

(-1.5, 0) rectangle (1.5,3); (0,1.5) to \[out=up, in=up,looseness=\] node\[zxvertex=, pos=0.5\](1,1.5) to (1,0); (-,1.5) to \[out=down, in=down,looseness=\] (-1, 1.5) to (-1,3); (0,1.5) to \[out=down, in=down,looseness=2.5\] (-1-, 1.5) to (-1-,3); (,1.5) to \[out=down, in=down,looseness=4\]node\[zxvertex=, pos=0.5\] (-1+, 1.5) to (-1+,3); at (0,1.5) [$P$]{};

But these are exactly the axioms of a quantum function for the following morphism $H\otimes A \to B\otimes H$: $$\begin{tz}[zx,every to/.style={out=up, in=down},scale=1.2]
\draw (0,1.5) to (-0.75, 3);
\draw (0.75,0) to (\d-0.05, 1.5);
\draw[arrow data={0.35}{>}] (-0.75,0) to (-\d+0.1,1.5); 
\draw[arrow data={0.2}{>},arrow data={0.85}{>}] (0,1.5) to[out=down, in=down, looseness=5] (0.7, 1.5) to[out=up, in=down] (0.75, 3);
\node[zxnode=\zxwhite] at (0,1.5) {$P$};
\end{tz}$$ Analogously, an intertwiner $f$ of $[A,B]$-actions is mapped to the intertwiner $f^\dagger$ of the corresponding quantum functions. This defines the desired equivalence.

From this perspective, $\QSet$ provides a high-level approach to the representation theory of the algebras of quantum functions, in particular clarifying their compositional behaviour.

\[rem:quantumfunctionalgebra\] It is not hard to show that for classical sets $X$ and $Y$, the $C^*$-algebra $[X,Y]$ is the universal $C^*$-algebra with generators $p_{x,y}$ for $x\in X, y \in Y$ and the following relations for $x\in X, y \in Y$ (also see Theorem \[thm:quantumfunctionsinprojectors\] and Proposition \[prop:Wang\]):

p\_[x,y]{}\^\* = p\_[x,y]{} = p\_[x,y]{}\^2 & p\_[x,y]{} p\_[x,y’]{} = \_[y,y’]{} p\_[x,y]{} &\_[yY]{} p\_[x,y]{}=1

For general finite-dimensional $C^*$-algebras $A$ and $B$, there is a similar =-2

\[rem:problemTannaka\] We remark that the categories $\QSet(A,B)\cong \mathrm{Rep}_{\mathrm{fd}}([A,B])^{op}$ only keep track of the *finite-dimensional* representation theory of the internal hom $[A,B]$.

It is tempting to try to reconstruct the algebra $[A,B]$ from the abstract $C^*$-category $\QSet(A,B)$ and the fibre functor $\QSet([A,B])\to \Hilb$. However, if neither $A$ nor $B$ are the one-element set — and if therefore $[A,B]$ is infinite-dimensional — we will see in Section \[sec:semisimple\] that the set of isomorphism classes of simple objects of $\QSet(A,B)$ in uncountable and carries a natural non-discrete topology. This cannot be captured with the inherently discrete tools of (ordinary) category theory; we cannot reconstruct $[A,B]$ from the abstract category $\QSet(A,B) \to \Hilb$. This is analogous to the inability to recover a discrete group from its (naive) representation category.

Quantum bijections {#sec:quantumbijection}
==================

The quantum graph isomorphisms of Atserias et al. [@Atserias2016], the quantum permutation groups of Wang [@Wang1998], and the quantum automorphism groups of Banica [@Banica2005] are all intended as quantisations of classical bijections. In this section, we define within our $2$-categorical framework a notion of quantum bijection which we show to be equivalent to the quantum bijections of these authors.

In particular, we show that quantum bijections can be exactly characterised as the *dagger-dualisable* $1$-morphisms in the $2$-category $\QSet$. We emphasise that quantum bijections should not be thought of as invertible but merely as dualisable. In fact, categorical equivalences in $\QSet$ are just classical bijections, or more generally [$*$-isomorphisms]{}.

Equivalences in $\QSet$
-----------------------

We first prove that equivalences in the sense of 2-category theory correspond to ordinary $*$-isomorphisms of Frobenius algebras; this shows that categorical equivalence is too strong a notion to characterise quantum bijections in $\QSet$.

Ordinary bijections — and more generally ordinary $*$-isomorphisms between Frobenius algebras — can be characterised by the following algebraic condition:

\[prop:Frobeniusinvertible\]A $*$-cohomomorphism between symmetric special Frobenius algebras is invertible if and only if it is also a $*$-homomorphism.[^11]

\[eq:Frobeniusmonoidlemma\]

(0,0) to (0,2) to \[out=135\] (-0.75,3); (0,2) to \[out=45\] (0.75, 3); at (0,1) [$f$]{}; at (0,2) ;

=

(0,0) to (0,0.75) to \[out=135\] (-0.75,1.75) to (-0.75,3); (0,0.75) to \[out=45\] (0.75, 1.75) to +(0,1.25); at (-0.75,2) [$f$]{}; at (0.75,2) [$f$]{}; at (0,0.75) ;

&

(0,0) to (0,2) ; at (0,1) [$f$]{}; at (0,2) ;

=

(0,0) to (0,0.75) ; at (0,0.75) ;

The proposition follows as a corollary from Theorem \[thm:dual2\], as shown in Remark \[rem:lemma42fromlemma46\].=-2

Now we show that equivalences in $\QSet$ are ordinary $*$-isomorphisms between Frobenius algebras.

\[prop:equivalence\]Equivalences between quantum sets in $\QSet$ are $*$-isomorphisms of Frobenius algebras.

Equivalences are preserved by the 2-functor $F:\QSet\to \BHilb$ of equation . In particular, the underlying Hilbert space $H$ of such an equivalence is invertible; there is another Hilbert space $H'$ such that $H\otimes H' \cong \mathbb{C}$. Therefore, $H\cong \mathbb{C}$ and the equivalence is a quantum function with one-dimensional Hilbert space and thus an invertible $*$-cohomomorphism. It follows from Proposition \[prop:Frobeniusinvertible\] that invertible $*$-cohomomorphisms are $*$-isomorphisms.

Two characterisations of quantum bijections {#sec:twocharacterisations}
-------------------------------------------

Having established that equivalences in $\QSet$ are ordinary $*$-isomorphisms, we must look elsewhere for an appropriate definition of quantum bijection. There are two possible approaches. The first is to quantise the algebraic characterisation of $*$-isomorphism from Proposition \[prop:Frobeniusinvertible\], following the procedure outlined in Section \[sec:quantumset\]. The other more structural approach is to define quantum bijections in terms of a genuinely categorical notion of weakened equivalence — the notion of *dagger adjunction* or *dagger duality*. We will show that both these approaches lead to the same definition of quantum bijection.

We first quantise the algebraic characterisation .

\[def:quantumbijection\] A *quantum bijection* between quantum sets $A$ and $B$ is a quantum function $(H,P)$ between $A$ and $B$ fulfilling the following additional equations:

\[eq:monadmap\]

(0,0) to (0,2) to \[out=45\] (0.75,3); (0,2) to \[out=135\] (-0.75,3); (1.75,0) to \[looseness=0.9\] node\[zxnode=, pos=0.5\] [$P$]{} (-1.75,2.5) to (-1.75,3); at (0,2);

=

(0,0) to (0,0.75) to \[out=45\] (0.75,1.75) to (0.75,3); (0,0.75) to \[out=135\] (-0.75,1.75) to (-0.75,3); (1.75,0) to (1.75,0.75) to \[looseness=1.1, in looseness=0.9\] node\[zxnode=, pos=0.36\] [$P$]{} node\[zxnode=, pos=0.64\] [$P$]{}(-1.75,3); at (0,0.75);

&

(0,0) to (0,2.25); (1,0) to \[looseness=0.9\] node\[zxnode=, pos=0.5\] [$P$]{} (-1,2.5) to (-1,3); at (0,2.25);

=

(0,0) to (0,0.75); (1.,0) to (1.,0.75) to (-1,3); at (0,0.75);

Alternatively, quantum bijections can be characterised as duals in $\QSet$. F[[\^\* F]{}]{}

\[def:duals\] A $1$-morphism $F:A\to B$ in a 2-category has a *right dual* $\F*:B\to A$ if there are 2-morphisms $\epsilon_R:F{\circ}\F*\to 1_{B}$ (counit) and $\eta_R:1_A\to \F*{\circ} F$ (unit) fulfilling the triangle equations[^12]:

(\_R 1\_[F]{})(1\_[F]{}\_R) = 1\_[F]{} & (1\_\_R )(\_R1\_) = 1\_

A $1$-morphism has a *left dual* $\*F:B\to A$ if there are 2-morphisms $\epsilon_L:\*F {\circ}F\to 1_{A}$ and $\eta_L:1_B\to F {\circ}\*F$ fulfilling the triangle equations:

(\_L 1\_[F]{})(1\_[F]{}\_L) = 1\_[F]{} & (1\_F\_L )(\_L1\_[F]{}) = 1\_[F]{}

In a dagger 2-category, a $1$-morphism has a *dual* $\overline{F}:B\to A$ if $\overline{F}$ is both a left and a right dual and the corresponding 2-morphisms are related as follows:

\_L\^= \_R & \_L\^= \_R

\[rem:daggerdual\] In a dagger $2$-category, every left (or right) dual is automatically a dual in the sense of Definition \[def:duals\]. We refer to a $1$-morphism that has a dual as *dualisable*.

As discussed in Philosophy \[phil:concretedagger\], $\QSet$ should be thought of not only as a 2-category but as a concrete dagger 2-category (see Definition \[def:Hilb2category\]), equipped with its forgetful $2$-functor $\QSet \to \BHilb$. In particular, the notion of a dual in $\QSet$ should be compatible with the underlying Hilbert space structure. This leads to the following definition.

\[def:daggerdualisable\]In a concrete dagger 2-category $(\mathbb{B}, F)$, a $1$-morphism $S$ is *dagger dualisable* if it has a dual $\conj{S}$ such that the underlying duality between $F(S)$ and $F(\conj{S})$ in $\Hilb$ is a dagger duality in the sense of Definition \[def:daggerduality\].

We will refer to such a $1$-morphism $\conj{S}$ as a *dagger dual* of $S$.

To characterise dagger-dualisable quantum functions, we adopt terminology from [@Vicary2012hq; @Reutter2016] and make the following definition.

\[def:biinvertible\]Let $A,B$ and $H$ be finite-dimensional Hilbert spaces. A linear map\
is *bi-invertible* if it is invertible and if $$\label{eq:biinv}\begin{tz}[zx,xscale=0.6,yscale=1,scale=1]
\draw(0.25,-0.5) to (0.25,0) to [out=up, in=-135] (1,1);
\draw [arrow data={0.34}{>}]  (1,1) to [out=135, in=right]  (-0.3, 1.7) to [out=left, in=up] (-1.25,1) to (-1.25,-0.5);
\draw(1.75,2.5) to (1.75,2) to [out=down, in=45] (1,1);
\draw[arrow data={0.32}{<}] (1,1) to [out= -45, in= left]   (2.3,0.3) to [out=right, in=down] (3.25,1) to (3.25,2.5);
\node [zxnode=\zxwhite] at (1,1) {$P^{-1}$};
\end{tz}
~~\text{ is inverse to }~~
\begin{tz}[zx,xscale=0.6,yscale=-1,scale=1]
\draw(0.25,-0.5) to (0.25,0) to [out=up, in=-135] (1,1);
\draw [arrow data={0.34}{<}]  (1,1) to [out=135, in=right]  (-0.3, 1.7) to [out=left, in=up] (-1.25,1) to (-1.25,-0.5);
\draw(1.75,2.5) to (1.75,2) to [out=down, in=45] (1,1);
\draw[arrow data={0.32}{>}] (1,1) to [out= -45, in= left]   (2.3,0.3) to [out=right, in=down] (3.25,1) to (3.25,2.5);
\node [zxnode=\zxwhite] at (1,1) {$P$};
\end{tz}$$

We now show that quantum bijections as in Definition \[def:quantumbijection\] are precisely dagger-dualisable quantum functions.

\[thm:dual2\]For a quantum function $(H,P)$ between quantum sets $A$ and $B$, the following are equivalent:

1.  $(H,P)$ is dagger-dualisable in $\QSet$.

2.  The underlying linear map $P:H\otimes A \to B \otimes H$ is bi-invertible.

3.  The underlying linear map $P:H\otimes A \to B\otimes H$ is unitary.

4.  $(H,P)$ is a quantum bijection as in Definition \[def:quantumbijection\].

If these properties hold, then the quantum function $(H^*,\overline{P}): B\to A$ whose underlying linear map $\overline{P}:H^* \otimes B \to A \otimes H^*$ is defined as follows, is a dagger dual of $(H,P)$: $$\label{eq:daggerdual}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=0.8]
\draw [arrow data={0.2}{<},arrow data={0.8}{<}]  (0,0) to (2.25,3);
\draw (2.25,0) to node[zxnode=\zxwhite, pos=0.5] {$\overline{P}$} (0,3);
\end{tz}
~~~:=~~~
\begin{tz}[zx,xscale=0.6,xscale=1]
\draw(0.25,-0.5) to (0.25,0) to [out=up, in=-135] (1,1);
\draw [arrow data={0.34}{>}]  (1,1) to [out=135, in=right]  (-0.3, 1.7) to [out=left, in=up] (-1.25,1) to (-1.25,-0.5);
\draw(1.75,2.5) to (1.75,2) to [out=down, in=45] (1,1);
\draw[arrow data={0.32}{<}] (1,1) to [out= -45, in= left]   (2.3,0.3) to [out=right, in=down] (3.25,1) to (3.25,2.5);
\node [zxnode=\zxwhite] at (1,1) {$P^\dagger$};
\end{tz} 
~~~=~~~
\begin{tz}[zx,xscale=0.6,xscale=1]
\draw[arrow data={0.68}{>}]  (4.75,2.5) to (4.75, 0.5) to [out=down, in=right] (2.65,-0.6) to [out=left, in=down] (0.55,0.5);
\draw (0.55,0.5) to [out=up, in=-135] (1,1);
\draw  (1,1) to [out=135, in=right]  (-0.3, 1.7) to [out=left, in=up]  node[zxvertex=\zxwhite, pos=0] {}(-1.25,1) to (-1.25,-0.5);
\draw[string, arrow data={0.68}{<}] (-2.75, -0.5) to (-2.75,1.5) to [out=up, in=left] (-0.65, 2.6) to [out=right, in=up] (1.45,1.5);
\draw  (1.45,1.5) to [out=down, in=45] (1,1);
\draw (1,1) to [out= -45, in= left]  node[zxvertex=\zxwhite, pos=1] {}  (2.3,0.3) to [out=right, in=down] (3.25,1) to (3.25,2.5);
\node [zxnode=\zxwhite] at (1,1) {$P$};
\end{tz}$$ The units and counits witnessing the duality between $(H,P)$ and $(H^*, \conj{P})$ are given by the standard cups and caps in $\Hilb$ . Moreover, $(H^*, \conj{P})$ is the unique dagger dual with these units and counits.

We prove the implications $1.\Rightarrow 2.\Rightarrow 4.\Rightarrow 3.\Rightarrow 1.$

$1. \Rightarrow 2.$ Suppose that $P$ has a dagger dual $Q'$. Since a dagger duality in $\QSet$ induces a dagger duality of the underlying Hilbert spaces and since dagger dualities are unique up to unitary isomorphism, the underlying Hilbert space of $Q'$ is unitarily isomorphic to the dual space $H^*$. Conjugating $Q'$ by this unitary isomorphism leads to a quantum function $Q$, dagger dual to $P$, whose underlying Hilbert space is exactly $H^*$ and such that the underlying linear maps of the unit and counit of the adjunction are the ‘standard’ cups and caps in $\Hilb$ . In other words, a quantum function $P:H\otimes A \to B \otimes H$ has a dagger dual, if and only if there is a quantum function $Q:H^* \otimes B \to A \otimes H^*$ such that the following holds:

\[eq:rightdual\]

(-2.05,-0.05) rectangle (4.05,4.05); (0,0) to \[out=up, in=up, looseness=6.\] (2,0); (-2,0) to \[out=up, in=down\] node\[zxnode=, pos=0.4\] [$P$]{} node\[zxnode=, pos=0.6\] [$Q$]{}(4,4);

=

(-2.05,-0.05) rectangle (4.05,4.05); (0,0) to \[out=up, in=up, looseness=2.\] (2,0); (-2,0) to \[out=up, in=down\] (4,4);

&

(-2.05,-0.05) rectangle (4.05,4.05); (0,0) to \[out=up, in=up, looseness=6.\] (2,0); (-2,0) to \[out=up, in=down\] node\[zxnode=, pos=0.4\] [$P$]{} node\[zxnode=, pos=0.6\] [$Q$]{}(4,4);

=

(-2.05,-0.05) rectangle (4.05,4.05); (0,0) to \[out=up, in=up, looseness=2.\] (2,0); (-2,0) to \[out=up, in=down\] (4,4);

\[eq:leftdual\]

(-2.05,-0.05) rectangle (4.05,4.05); (0,0) to \[out=up, in=up, looseness=6.\] (2,0); (-2,0) to \[out=up, in=down\] node\[zxnode=, pos=0.4\] [$Q$]{} node\[zxnode=, pos=0.6\] [$P$]{}(4,4);

=

(-2.05,-0.05) rectangle (4.05,4.05); (0,0) to \[out=up, in=up, looseness=2.\] (2,0); (-2,0) to \[out=up, in=down\] (4,4);

&

(-2.05,-0.05) rectangle (4.05,4.05); (0,0) to \[out=up, in=up, looseness=6.\] (2,0); (-2,0) to \[out=up, in=down\] node\[zxnode=, pos=0.4\] [$Q$]{} node\[zxnode=, pos=0.6\] [$P$]{}(4,4);

=

(-2.05,-0.05) rectangle (4.05,4.05); (0,0) to \[out=up, in=up, looseness=2.\] (2,0); (-2,0) to \[out=up, in=down\] (4,4);

Equations  and  can equivalently be expressed as stating the following:

(0.25,-0.5) to (0.25,0) to \[out=up, in=-135\] (1,1); (1,1) to \[out=135, in=right\] (-0.3, 1.7) to \[out=left, in=up\] (-1.25,1) to (-1.25,-0.5); (1.75,2.5) to (1.75,2) to \[out=down, in=45\] (1,1); (1,1) to \[out= -45, in= left\] (2.3,0.3) to \[out=right, in=down\] (3.25,1) to (3.25,2.5); at (1,1) [$Q$]{};

(0,0) to (2.25,3); (2.25,0) to node\[zxnode=, pos=0.5\] [$P$]{} (0,3);

&

(0,0) to (2.25,3); (2.25,0) to node\[zxnode=, pos=0.5\] [$Q$]{} (0,3);

(0.25,-0.5) to (0.25,0) to \[out=up, in=-135\] (1,1); (1,1) to \[out=135, in=right\] (-0.3, 1.7) to \[out=left, in=up\] (-1.25,1) to (-1.25,-0.5); (1.75,2.5) to (1.75,2) to \[out=down, in=45\] (1,1); (1,1) to \[out= -45, in= left\] (2.3,0.3) to \[out=right, in=down\] (3.25,1) to (3.25,2.5); at (1,1) [$P$]{};

We have therefore shown that $P$ is bi-invertible. $2.\Rightarrow 4.$ Suppose that $P:H\otimes A \to B \otimes H$ is a bi-invertible quantum function. We now demonstrate that it fulfills the second equation in :

$$\def\l{2.25}
\def\h{1}
\def\top{5.5}
\def\bottom{-2}
\def\bottomright{2}
\def\topleft{-0.5}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw[string] (0.75,0.25) to node[zxnode=\zxwhite, pos=0.26] {$P$} (0.75,\top);
\node[zxvertex=\zxwhite] at (0.75,0.25){};
\draw[string,arrow data={0.2}{>}, arrow data={0.8}{>}] (\bottomright, \bottom) to (\topleft, \top);
\end{tz}
~=~~
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\l{2.25}
\def\h{1}
\def\top{5.5}
\def\bottom{-2}
\def\bottomright{2}
\def\topleft{-0.5}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\node at (0,0) (C){};
\draw (C.center) to [out=down, in=down,looseness=2] node[zxvertex=\zxwhite, pos=0.5] {} (-\l, 0) to [out=up, in=down] (-2.25,\h);
\draw[string] (C.center) to [out=45, in=down] ([xshift=0.75cm, yshift=1cm]C.center) to node[zxnode=\zxwhite, pos=0.16] {$P$} (0.75,\top);
\draw[string] (C.center) to [out=135, in=down]  ([xshift=-0.75cm, yshift=1cm]C.center) to (-0.75,\h) to [out=up, in=down] (-2.25, \h+1) to [out=up, in=up] node[zxvertex=\zxwhite, pos=0.5]{} (-0.75,\h+1) to [out=down, in=up] (-2.25,\h);
\node[zxvertex=\zxwhite,zxup] at (C.center){};
\draw[string,arrow data={0.2}{>}, arrow data={0.8}{>}] (\bottomright, \bottom) to (\topleft, \top);
\end{tz}
~~=~
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\l{2.25}
\def\h{3.5}
\def\top{5.5}
\def\bottom{-2}
\def\bottomright{2}
\def\topleft{-0.2}
\def \middle{2.3}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\node at (0,0) (C){};
\draw (C.center) to [out=down, in=down,looseness=2] node[zxvertex=\zxwhite, pos=0.5] {} (-\l, 0) to [out=up, in=down] (-2.25,\h);
\draw[string] (C.center) to [out=45, in=down] ([xshift=0.75cm, yshift=1cm]C.center) to node[zxnode=\zxwhite, pos=0.0] {$P$} (0.75,\top);
\draw[string] (C.center) to [out=135, in=down]  ([xshift=-0.75cm, yshift=1cm]C.center) to node[zxnode=\zxwhite, pos=0.18] {$P$}node[zxnode=\zxwhite, pos=0.85] {$P^{-1}$}(-0.75,\h) to [out=up, in=down] (-2.25, \h+1) to [out=up, in=up] node[zxvertex=\zxwhite, pos=0.5]{} (-0.75,\h+1) to [out=down, in=up] (-2.25,\h);
\node[zxvertex=\zxwhite,zxup] at (C.center){};
\draw[string,arrow data={0.15}{>}, arrow data={0.64}{>},arrow data={0.9}{>}] (\bottomright, \bottom) to (\bottomright, -0.1) to (-1.5, \middle) to  (\topleft, \h+0.5) to (\topleft, \top);
\end{tz}
~~=~
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\l{2.25}
\def\h{1.5}
\def\top{5.5}
\def\bottom{-2}
\def\bottomright{2}
\def\topleft{-0.2}
\def \middle{0.2}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\node at (0,0) (C){};
\draw (C.center) to [out=down, in=down,looseness=2] node[zxnode=\zxwhite, pos=0.15] {$P$} node[zxvertex=\zxwhite, pos=0.5] {} (-\l, 0) to [out=up, in=down] (-2.25,\h);
\draw[string] (C.center) to [out=45, in=down] ([xshift=0.75cm, yshift=1cm]C.center) to  (0.75,\top);
\draw[string] (C.center) to [out=135, in=down]  ([xshift=-0.75cm, yshift=1cm]C.center) to node[zxnode=\zxwhite, pos=-0.2] {$P^{-1}$}(-0.75,\h) to [out=up, in=down] (-2.25, \h+1) to [out=up, in=up] node[zxvertex=\zxwhite, pos=0.5]{} (-0.75,\h+1) to [out=down, in=up] (-2.25,\h);
\node[zxvertex=\zxwhite,zxup] at (C.center){};
\draw[string,arrow data={0.15}{>}, arrow data={0.4}{>},arrow data={0.9}{>}] (\bottomright, \bottom) to  (-1., \middle) to  (\topleft, \h+0.5) to (\topleft, \top);
\end{tz}
~~=~
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\l{2.25}
\def\h{3.5}
\def\top{5.5}
\def\bottom{-2}
\def\bottomright{2}
\def\topleft{-0.2}
\def \middle{2.3}
\def\xgap{-0.9cm}
\def\loose{3}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\node at (0,0) (C){};
\draw (C.center) to [out=down, in=down,looseness=2] node[zxvertex=\zxwhite, pos=0.5] {} (-\l, 0) to [out=up, in=down] (-2.25,\h);
\draw[string] (C.center) to [out=45, in=down] ([xshift=0.75cm, yshift=1cm]C.center) to (0.75,\top);
\draw[string] (C.center) to [out=135, in=down]  ([xshift=-0.75cm, yshift=1cm]C.center) to node[zxnode=\zxwhite, pos=0.1](b) {$P^{-1}$}node[zxnode=\zxwhite, pos=0.7](t) {$P$}(-0.75,\h) to [out=up, in=down] (-2.25, \h+1) to [out=up, in=up] node[zxvertex=\zxwhite, pos=0.5]{} (-0.75,\h+1) to [out=down, in=up] (-2.25,\h);
\draw[arrow data={0.5}{>}][string] (t.center) to [looseness=\loose,out=135, in=up]([xshift=\xgap]t.center) to ([xshift=\xgap]b.center) to [looseness=\loose,out=down, in=-135] (b.center);
\node[zxvertex=\zxwhite,zxup] at (C.center){};
\draw[string,arrow data={0.25}{>}] (\bottomright, \bottom) to [in=-45] (t.center);
\draw[string,arrow data = {0.7}{>}] (b.center) to [out=45]  (\topleft, \top);
\end{tz}$$

ł[2.25]{} $$=~\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\node at (0,0) (C){};
\draw (C.center) to [out=down, in=down,looseness=2] node[zxvertex=\zxwhite, pos=0.5] {} (-\l, 0) to [out=up, in=down] (-2.25,\h);
\draw[string] (C.center) to [out=45, in=down] ([xshift=0.75cm, yshift=1cm]C.center) to (0.75,\top);
\draw[string] (C.center) to [out=135, in=down]  ([xshift=-0.75cm, yshift=1cm]C.center) to (-0.75,\h) to [out=up, in=down] (-2.25, \h+1) to [out=up, in=up] node[zxvertex=\zxwhite, pos=0.5]{} (-0.75,\h+1) to [out=down, in=up] (-2.25,\h);
\node[zxvertex=\zxwhite,zxup] at (C.center){};
\coordinate (loopcenter) at (0.05,2);
\draw[string,arrow data={0.2}{>}, arrow data={0.8}{>}] (\bottomright, \bottom) to  [in=-45] (loopcenter) to [looseness=\looploose,out=135, in=up] ([xshift=\loop]loopcenter) to [looseness=\looploose,out=down, in=-135] (loopcenter) to [out=45] (\topleft, \top);
\end{tz}
~~=~
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\l{2.25}
\def\h{1}
\def\top{5.5}
\def\bottom{-2}
\def\bottomright{2}
\def\topleft{-0.5}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw[string] (0.75,4) to (0.75,\top);
\node[zxvertex=\zxwhite] at (0.75,4){};
\draw[string,arrow data={0.2}{>}, arrow data={0.8}{>}] (\bottomright, \bottom) to (\topleft, \top);
\end{tz}$$ Here, the first equation follows from the axioms of symmetric special Frobenius algebras, the second equation is invertibility of $P$, the third equation uses the fact that $P$ is a quantum function, the fourth equation follows from the graphical calculus moving $P$ along the right wire onto the top of $P^{-1}$. Finally, in the first equation of the second line, we use bi-invertibility of $P$.

We now show that if $P$ is invertible, then the second equation in implies the first equation. $$\def\scl{0.85}
\begin{tz}[zx,scale=-1,scale=\scl,xscale=-1]
\clip (-3.05,-0.2) rectangle (1.8,4.2);
\draw[arrow data={0.1}{<},arrow data={0.5}{<}, arrow data={0.95}{<}] (1.75,0) to [out=up,in=-45] (1,1) to (-1,3) to [out=135, in=down] (-1.75,4);
\draw (0.25,0) to [out=up, in=-135] (1,1) to [in looseness=2.5,out=45, in=65] node[pos=0.72](c){} (-1,3) to [out=-135, in=right] (-2,2) to [out=left, in=down] (-3,4) ;
\node[zxnode=\zxwhite] at (1,1) {$P$};
\node[zxnode=\zxwhite] at (-1,3) {$P$};
\node[zxvertex=\zxwhite] at (c.center){};
\node[zxvertex=\zxwhite] at (-2,2){};
\end{tz}
~~\superequals{\eqref{eq:quantumfunction}~\&~\eqref{eq:cupcapfrob}}~~~~
\begin{tz}[zx,scale=-1,scale=\scl,xscale=-1]
\draw  (1.75,0) to (1.75,1) to[out=up, in=-45] (1,2) to [out=-135, in=up] (0.25,1) to [looseness=1.5,out=down,  in=down] node[pos=0.5] (b){}(-1.25,1) to (-1.25,4);
\draw (1,2) to [looseness=0.4,out=up, in=down] (1.75,3.25);
\draw[arrow data={0.4}{<},arrow data={0.9}{<}] (3.5,0) to [looseness=0.5,out=up,in=down]node[zxnode=\zxwhite, pos=0.64] {$P$} (0.5,4);
\node[zxvertex=\zxwhite] at (b.center){};
\node[zxvertex=\zxwhite,zxup] at (1,2){};
\node[zxvertex=\zxwhite] at (1.75,3.25){};
\end{tz}
~~\superequalseq{eq:monadmap}~~
\begin{tz}[zx,scale=-1,scale=\scl,xscale=-1]
\draw (0,0) to (0, 2) to [looseness=1.5,out=up, in=up] node[zxvertex=\zxwhite,pos=0.5]{} (-1.5,2) to [looseness=1.5,out=down, in=down]node[zxvertex=\zxwhite,pos=0.5]{} (-3,2) to (-3,4);
\draw[string,arrow data={0.5}{<}] (1.5,0) to + (0,4);
\end{tz}
~~=~~
\begin{tz}[zx,xscale=1,scale=\scl]
\draw (0,0) to + (0,4);
\draw[string,arrow data={0.5}{>}] (1.5,0) to + (0,4);
\end{tz}
\hspace{0.5cm} \Rightarrow \hspace{0.5cm}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=0.8,scale=1]
\draw [arrow data={0.2}{>},arrow data={0.8}{>}]  (0,0) to (2.25,3);
\draw (2.25,0) to node[zxnode=\zxwhite, pos=0.5] {$P^{-1}$} (0,3);
\end{tz}
~~=~~
\begin{tz}[zx,xscale=-0.6,yscale=-1,scale=\scl]
\draw[arrow data={0.5}{<}] (0.25,-0.5) to (0.25,0) to [out=up, in=-135] (1,1);
\draw (1,1) to [out=135, in=right] node[zxvertex=\zxwhite, pos=1]{} (-0.3, 1.7) to [out=left, in=up] (-1.25,1) to (-1.25,-0.5);
\draw[arrow data={0.5}{>}] (1.75,2.5) to (1.75,2) to [out=down, in=45] (1,1);
\draw (1,1) to [out= -45, in= left] node[zxvertex=\zxwhite, pos=1] {} (2.3,0.3) to [out=right, in=down] (3.25,1) to (3.25,2.5);
\node [zxnode=\zxwhite] at (1,1) {$P$};
\end{tz}$$ Since $P^{-1}$ is also a left inverse of $P$, this implies the following: $$\label{eq:proofbijection}\begin{tz}[zx,scale=\scl,xscale=1]
\clip (-2.05,-0.05) rectangle (4.05,4.05);
\draw(0,0) to [out=up, in=up, looseness=6.] node[zxvertex=\zxwhite,pos=0.5] {} (2,0);
\draw [string,arrow data={0.1}{>},arrow data={0.9}{>}] (-2,0) to [out=up, in=down]  node[zxnode=\zxwhite, pos=0.4] {$P$} node[zxnode=\zxwhite, pos=0.6] {$P$}(4,4);
\end{tz}
=
\begin{tz}[zx,scale=\scl,xscale=1]
\clip (-2.05,-0.05) rectangle (4.05,4.05);
\draw (0,0) to [out=up, in=up, looseness=2.] node[zxvertex=\zxwhite, pos=0.5] {}(2,0);
\draw[arrow data={0.2}{>}, arrow data={0.8}{>}] (-2,0) to [out=up, in=down]  (4,4);
\end{tz}$$ We can then prove the first equation as follows: $$\begin{tz}[zx,every to/.style={out=up, in=down},scale=-1,xscale=-1]
\draw (0,0) to (0,2) to [out=45] (0.75,3);
\draw (0,2) to [out=135] (-0.75,3);
\draw[arrow data={0.2}{<}, arrow data={0.8}{<}] (1.75,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5] {$P$} (-1.75,2.5) to (-1.75,3);
\node[zxvertex=\zxwhite, zxdown] at (0,2){};
\end{tz}
~~\superequalseq{eq:Frobenius}~~
\begin{tz}[zx,every to/.style={out=up, in=down},scale=-1,xscale=-1]
\draw (0,0) to (0,1.7) to [in=-135] (0.5,2.3) to (0.5,3);
\draw (0.5,2.3) to [out=-45, in=up] (1,1.7) to [out=down, in=down, looseness=1.5] node[zxvertex=\zxwhite, pos=0.5] {}(1.75,1.7) to (1.75,3);
\draw[string,arrow data={0.2}{<}, arrow data={0.8}{<}] (1.75,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5] {$P$} (-1.75,2.5) to (-1.75,3);
\node[zxvertex=\zxwhite, zxup] at (0.5,2.3){};
\end{tz}
~~~~~\superequals{\eqref{eq:quantumfunction}~\&~\eqref{eq:proofbijection}}~~
\begin{tz}[zx,every to/.style={out=up, in=down},scale=-1,xscale=-1]
\draw (-1,0) to (-1,0.7) to [in=-135] node[pos=1] (a) {}(-0.5,1.3) to (-0.5,3);
\draw[string] (-0.5,1.3) to [out=-45, in=up] (0,0.7) to [out=down, in=down, looseness=1.5] node[zxvertex=\zxwhite, pos=0.5] {}(0.75,0.7) to (0.75,3);
\draw[string,arrow data={0.2}{<}, arrow data={0.9}{<}] (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9] node[zxnode=\zxwhite, pos=0.34] {$P$} node[zxnode=\zxwhite, pos=0.6] {$P$}(-1.75,3);
\node[zxvertex=\zxwhite,zxup] at (a.center){};
\end{tz}
~~\superequalseq{eq:Frobenius}~~
\begin{tz}[zx,every to/.style={out=up, in=down},scale=-1,xscale=-1]
\draw (0,0) to (0,0.75) to [out=45] (0.75,1.75) to (0.75,3);
\draw (0,0.75) to [out=135] (-0.75,1.75) to (-0.75,3);
\draw[arrow data={0.2}{<}, arrow data={0.9}{<}] (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9] node[zxnode=\zxwhite, pos=0.36] {$P$} node[zxnode=\zxwhite, pos=0.64] {$P$}(-1.75,3);
\node[zxvertex=\zxwhite, zxdown] at (0,0.75){};
\end{tz}$$

$4.\Rightarrow 3.$ $$\begin{tz}[zx,every to/.style={out=up, in=down},scale=1,xscale=-1]
\draw (0.25,0) to [out=up, in=-135] (1,1) to [looseness=1.5,out=45, in=-45] (1,3) to [out=135, in=down] (0.25,4);
\draw[arrow data={0.1}{>}, arrow data={0.5}{>}, arrow data={0.95}{>}] (1.75,0) to [out=up, in=-45] (1,1) to [looseness=1.5, out=135, in=-135] (1,3) to [out=45, in=down] (1.75,4);
\node[zxnode=\zxwhite] at (1,1) {$P$};
\node[zxnode=\zxwhite] at (1,3) {$P^\dagger$};
\end{tz}
~~\superequalseq{eq:quantumfunction}~~
\begin{tz}[zx,xscale=-1]
\clip (-3.05,-0.2) rectangle (1.8,4.2);
\draw[arrow data={0.1}{>},arrow data={0.5}{>}, arrow data={0.95}{>}] (1.75,0) to [out=up,in=-45] (1,1) to (-1,3) to [out=135, in=down] (-1.75,4);
\draw (0.25,0) to [out=up, in=-135] (1,1) to [in looseness=2.5,out=45, in=65] node[pos=0.72](c){} (-1,3) to [out=-135, in=right] (-2,2) to [out=left, in=down] (-3,4) ;
\node[zxnode=\zxwhite] at (1,1) {$P$};
\node[zxnode=\zxwhite] at (-1,3) {$P$};
\node[zxvertex=\zxwhite] at (c.center){};
\node[zxvertex=\zxwhite] at (-2,2){};
\end{tz}
~~\superequalseq{eq:monadmap}~~
\begin{tz}[zx,xscale=-1]
\draw  (1.75,0) to (1.75,1) to[out=up, in=-45] (1,2) to [out=-135, in=up] (0.25,1) to [looseness=1.5,out=down,  in=down] node[pos=0.5] (b){}(-1.25,1) to (-1.25,4);
\draw (1,2) to [looseness=0.4,out=up, in=down] (1.75,3.25);
\draw[arrow data={0.4}{>},arrow data={0.9}{>}] (3.5,0) to [looseness=0.5,out=up,in=down]node[zxnode=\zxwhite, pos=0.64] {$P$} (0.5,4);
\node[zxvertex=\zxwhite] at (b.center){};
\node[zxvertex=\zxwhite,zxdown] at (1,2){};
\node[zxvertex=\zxwhite] at (1.75,3.25){};
\end{tz}
~~\superequalseq{eq:quantumfunction}~~
\begin{tz}[zx,xscale=-1]
\draw (0,0) to (0, 2) to [looseness=1.5,out=up, in=up] node[zxvertex=\zxwhite,pos=0.5]{} (-1.5,2) to [looseness=1.5,out=down, in=down]node[zxvertex=\zxwhite,pos=0.5]{} (-3,2) to (-3,4);
\draw[string,arrow data={0.5}{>}] (1.5,0) to + (0,4);
\end{tz}
~~=~~
\begin{tz}[zx,xscale=-1]
\draw (0,0) to + (0,4);
\draw[string,arrow data={0.5}{>}] (1.5,0) to + (0,4);
\end{tz}$$ $$\begin{tz}[zx,every to/.style={out=up, in=down},xscale=1]
\draw (0.25,0) to [out=up, in=-135] (1,1) to [looseness=1.5,out=45, in=-45] (1,3) to [out=135, in=down] (0.25,4);
\draw[arrow data={0.1}{>}, arrow data={0.5}{>}, arrow data={0.95}{>}] (1.75,0) to [out=up, in=-45] (1,1) to [looseness=1.5, out=135, in=-135] (1,3) to [out=45, in=down] (1.75,4);
\node[zxnode=\zxwhite] at (1,1) {$P^\dagger$};
\node[zxnode=\zxwhite] at (1,3) {$P$};
\end{tz}
~~\superequalseq{eq:quantumfunction}~~
\begin{tz}[zx,scale=-1,xscale=-1]
\clip (-3.05,-0.2) rectangle (1.8,4.2);
\draw[arrow data={0.1}{<},arrow data={0.5}{<}, arrow data={0.95}{<}] (1.75,0) to [out=up,in=-45] (1,1) to (-1,3) to [out=135, in=down] (-1.75,4);
\draw (0.25,0) to [out=up, in=-135] (1,1) to [in looseness=2.5,out=45, in=65] node[pos=0.72](c){} (-1,3) to [out=-135, in=right] (-2,2) to [out=left, in=down] (-3,4) ;
\node[zxnode=\zxwhite] at (1,1) {$P$};
\node[zxnode=\zxwhite] at (-1,3) {$P$};
\node[zxvertex=\zxwhite] at (c.center){};
\node[zxvertex=\zxwhite] at (-2,2){};
\end{tz}
~~\superequalseq{eq:quantumfunction}~~
\begin{tz}[zx,scale=-1,xscale=-1]
\draw  (1.75,0) to (1.75,1) to[out=up, in=-45] (1,2) to [out=-135, in=up] (0.25,1) to [looseness=1.5,out=down,  in=down] node[pos=0.5] (b){}(-1.25,1) to (-1.25,4);
\draw (1,2) to [looseness=0.4,out=up, in=down] (1.75,3.25);
\draw[arrow data={0.4}{<},arrow data={0.9}{<}] (3.5,0) to [looseness=0.5,out=up,in=down]node[zxnode=\zxwhite, pos=0.64] {$P$} (0.5,4);
\node[zxvertex=\zxwhite] at (b.center){};
\node[zxvertex=\zxwhite,zxup] at (1,2){};
\node[zxvertex=\zxwhite] at (1.75,3.25){};
\end{tz}
~~\superequalseq{eq:monadmap}~~
\begin{tz}[zx,scale=-1,xscale=-1]
\draw (0,0) to (0, 2) to [looseness=1.5,out=up, in=up] node[zxvertex=\zxwhite,pos=0.5]{} (-1.5,2) to [looseness=1.5,out=down, in=down]node[zxvertex=\zxwhite,pos=0.5]{} (-3,2) to (-3,4);
\draw[string,arrow data={0.5}{<}] (1.5,0) to + (0,4);
\end{tz}
~~=~~
\begin{tz}[zx]
\draw (0,0) to + (0,4);
\draw[string,arrow data={0.5}{>}] (1.5,0) to + (0,4);
\end{tz}$$ $3. \Rightarrow 1.$ Suppose that $P:H \otimes A \to B \otimes H$ is unitary. Then, the following linear map is a quantum function: $$\begin{tz}[zx,every to/.style={out=up, in=down},xscale=0.8,scale=0.8]
\draw [arrow data={0.2}{<},arrow data={0.8}{<}]  (0,0) to (2.25,3);
\draw (2.25,0) to node[zxnode=\zxwhite, pos=0.5] {$Q$} (0,3);
\end{tz}
~:=~
\begin{tz}[zx,xscale=0.6,yscale=1,scale=0.8]
\draw(0.25,-0.5) to (0.25,0)     to [out=up, in=-135] (1,1);
\draw [arrow data={0.34}{>}]  (1,1) to [out=135, in=right]  (-0.3, 1.7) to [out=left, in=up] (-1.25,1) to (-1.25,-0.5);
\draw(1.75,2.5) to (1.75,2) to [out=down, in=45] (1,1);
\draw[arrow data={0.32}{<}] (1,1) to [out= -45, in= left]   (2.3,0.3) to [out=right, in=down] (3.25,1) to (3.25,2.5);
\node [zxnode=\zxwhite] at (1,1) {$P^{\dagger}$};
\end{tz}
~=~
\begin{tz}[zx,xscale=0.6,xscale=1,scale=0.8]
\draw[arrow data={0.68}{>}]  (4.75,2.5) to (4.75, 0.5) to [out=down, in=right] (2.65,-0.6) to [out=left, in=down] (0.55,0.5);
\draw (0.55,0.5) to [out=up, in=-135] (1,1);
\draw  (1,1) to [out=135, in=right]  (-0.3, 1.7) to [out=left, in=up]  node[zxvertex=\zxwhite, pos=0] {}(-1.25,1) to (-1.25,-0.5);
\draw[string, arrow data={0.68}{<}] (-2.75, -0.5) to (-2.75,1.5) to [out=up, in=left] (-0.65, 2.6) to [out=right, in=up] (1.45,1.5);
\draw  (1.45,1.5) to [out=down, in=45] (1,1);
\draw (1,1) to [out= -45, in= left]  node[zxvertex=\zxwhite, pos=1] {}  (2.3,0.3) to [out=right, in=down] (3.25,1) to (3.25,2.5);
\node [zxnode=\zxwhite] at (1,1) {$P$};
\end{tz}$$ For example, the counit condition of $Q$ follows from precomposing the counit condition of the quantum function $P$ with $P^\dagger$: $$\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,2.25);
\draw[arrow data={0.2}{>}, arrow data={0.8}{>}] (1,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5] {$P$} (-1,2.5) to (-1,3);
\node[zxvertex=\zxwhite] at (0,2.25){};
\end{tz}
~~\superequalseq{eq:quantumfunction}~~
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,0.75);
\draw[arrow data={0.2}{>}, arrow data={0.9}{>}] (1.,0) to (1.,0.75) to   (-1,3);
\node[zxvertex=\zxwhite, zxup] at (0,0.75){};
\end{tz}
\hspace{0.75cm}\super{\text{$P$ unitary}}{\Leftrightarrow} \hspace{0.75cm}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=1]
\draw (0,0) to (0,0.75);
\draw[arrow data={0.2}{>}, arrow data={0.9}{>}] (1.,0) to (1.,3) ;
\node[zxvertex=\zxwhite, zxup] at (0,0.75){};
\end{tz}
~~=~~
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw[arrow data ={0.15}{>}, arrow data={0.8}{>}] (0,0) to (1,2) to (1,3);
\draw (1,0) to (0,2);
\node[zxnode=\zxwhite] at (0.5,1) {$P^\dagger$};
\node[zxvertex=\zxwhite] at (0,2){};
\end{tz}
\hspace{0.75cm}\Leftrightarrow \hspace{0.75cm}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,0.75);
\draw[arrow data={0.2}{<}, arrow data={0.9}{<}] (1.,0) to (1.,0.75) to   (-1,3);
\node[zxvertex=\zxwhite, zxup] at (0,0.75){};
\end{tz}
~~=~~
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,2.25);
\draw[arrow data={0.2}{<}, arrow data={0.8}{<}] (1,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5] {$Q$} (-1,2.5) to (-1,3);
\node[zxvertex=\zxwhite] at (0,2.25){};
\end{tz}$$ The comultiplication condition of $Q$ can be proven similarly. The last equation in  follows from a direct graphical argument, proving that $Q$ is indeed a quantum function.

Moreover, unitarity of $P$ implies that $P$ and $Q$ fulfill equations . We note that equation  is the dagger of equation  and therefore redundant. This follows directly from the fact that $P$ and $Q$ are quantum functions and $\QSet$ is a dagger 2-category (see equation ). Therefore, $Q$ is a dagger dual of $P$ in $\QSet$.

\[rem:lemma42fromlemma46\] Proposition \[prop:Frobeniusinvertible\] follows as the one-dimensional case of Theorem \[thm:dual2\]. In fact, following our philosophy outlined in Section \[sec:quantumset\], several of the steps of the proof of Theorem \[thm:dual2\] were first devised for the simpler case of Proposition \[prop:Frobeniusinvertible\]. The oriented wire was added in later, in an essentially unique way.

It is a direct consequence of Theorem \[thm:dual2\] that a quantum function $(H,P)$ is dagger-dualisable (or equivalently bi-invertible) if and only if it is biunitary as defined in [@Reutter2016].

We denote the 2-category of quantum sets, quantum bijections and intertwiners by $\QBij$.=-2

\[rem:monoidalsubcats\] Composition of quantum functions makes the category $\QBij(B,B)$ of *quantum permutations* on a quantum set $B$ into a monoidal dagger category with dualisable objects

(see Theorem \[thm:dual2\]). In particular, the categories of quantum permutations $\QBij([n], [n])$ on an $n$-element set $[n]$ can be thought of as a quantum version of the symmetric group $S_n$.

Quantum bijections in noncommutative topology {#sec:Wang}
---------------------------------------------

The monoidal categories $\QBij(B,B)$ of quantum bijections on a quantum set $B$ have been considered in finite noncommutative topology.

In [@Wang1998], Wang introduced ‘quantum symmetry groups of finite quantum spaces’ as non-commutative variants of the symmetric groups $S_n$. We now show that our category of quantum permutations on a quantum set is precisely the category of finite-dimensional representations of the Hopf $C^*$-algebra corresponding to Wang’s quantum symmetry group. In other words, our quantum permutations are quantum elements of this quantum group (cf. Theorem \[thm:universalprop\]).

\[prop:Wang\] For a quantum set $B$, $\QBij(B,B)$ is the category of finite-dimensional representations of Wang’s ‘quantum symmetry group’ algebra $A_{aut}(B)$.

We only prove the proposition for classical sets $[n]$; the proof for general quantum sets is completely analogous, only involving more indices.

In [@Wang1998 Theorem 3.1], Wang defines quantum permutation groups of classical finite sets $[n]$ as $C^*$-algebras $A_{aut}([n])$ with generators $a_{i,j}$ $(i,j=1,\ldots n)$ and relations:

\[eq:Wangcondition\] a\_[i,j]{}\^2=a\_[i,j]{} = a\_[i,j]{}\^\* & \_[i=1]{}\^n a\_[i,j]{} = 1,   1jn & \_[j=1]{}\^n a\_[i,j]{} =1,   1in

Noting that projectors summing to the identity are mutually orthogonal and comparing the relations  with Theorem \[thm:quantumfunctionsinprojectors\] shows that our categories $\QBij([n], [n])$ are the categories of finite-dimensional representations of $A_{aut}([n])$.

Proposition \[prop:Wang\] is not surprising: In Section \[sec:universal\], we showed that $\QSet(B,B)$ is the category of finite-dimensional representations of the internal hom $[B,B]$ and in Section \[sec:quantumbijection\] we prove that $\QBij(B,B)$ is the full subcategory of dagger-dualisable objects in $\QSet(B,B)$. We therefore expect $\QBij(B,B)$ to arise as the category of finite-dimensional representations of some internal ‘automorphism Hopf $C^*$-algebra’, which is exactly how Wang defines his compact quantum group algebra $A_{aut}(B)$.

\[rem:Wangnotdiscrete\] As in Remark \[rem:problemTannaka\], we cannot recover $A_{aut}(B)$ from the fibre functor $\QBij(B,B) \to \Hilb$. Indeed, from the perspective of locally compact quantum groups (see e.g. [@Maes1998; @Neshveyev2013]), we can think of $\QBij(B,B)$ as the category of finite-dimensional representations

of the discrete quantum group dual to Wang’s compact quantum symmetry group. Similarly to the case of ordinary discrete groups this discrete quantum group cannot generally be recovered from its (naive) representation category.

Quantum bijections between classical sets {#sec:quantumperm}
-----------------------------------------

We now focus on quantum functions and quantum bijections between classical sets and show that we recover the *magic unitaries* of Banica et al. [@Banica2007] and the *projective permutation matrices* of Atserias et al. [@Atserias2016]. We first show that we can express quantum functions between classical sets as families of projectors satisfying certain =-2

\[thm:quantumfunctionsinprojectors\] A quantum function $X\to Y$ between classical sets $X$ and $Y$ is exactly a family of projectors $\{P_{x,y}\}_{x\in X, y \in Y}$ on a Hilbert space $H$ such that the following holds, for all $x\in X$ and $y_1,y_2\in Y$:

\[eq:PPM1\]P\_[x,y\_1]{} P\_[x,y\_2]{} = \_[y\_1,y\_2]{} P\_[x,y\_1]{} & \_[yY]{} P\_[x,y]{} = \_H

A quantum bijection $X\to Y$ between classical sets $X$ and $Y$ is exactly a family of projectors $\{P_{x,y}\}_{x\in X, y \in Y}$ satisfying and the following additional conditions, for all $x_1,x_2\in X$ and $y\in Y$:

\[eq:PPM2\] P\_[x\_1,y]{} P\_[x\_2,y]{} = \_[x\_1,x\_2]{} P\_[x\_1,y]{} & \_[xX]{} P\_[x,y]{} = \_H

Every classical set $X$ corresponds to a commutative Frobenius algebra defined in Example \[exm:Frob\], the elements of $X$ form a basis of copyable elements of this algebra. The linear map $P:H\otimes X \to Y \otimes H$ may therefore be expressed in this basis: :$$\begin{tz}[zx]
\draw[arrow data={0.2}{>}, arrow data={0.8}{>}] (0,0) to (0,3);
\node[zxnode=\zxwhite] at (0,1.5) {$P_{x,y}$};
\end{tz}
~~:=
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=0.8]
\draw [arrow data={0.2}{>},arrow data={0.8}{>}]  (0,0) to (2.25,3);
\draw (1.75,0.5) to node[zxnode=\zxwhite, pos=0.5] {$P$} (0.5,2.5);
\node[zxnode=\zxwhite] at (1.75,0.5){$x$};
\node[zxnode=\zxwhite] at (0.5,2.5){$y$};
\end{tz}$$ As an example, the first equation of , expanded in the classical basis, becomes $$\delta_{y,y'}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,2.5);
\draw[arrow data={0.2}{>}, arrow data={0.8}{>}] (1.75,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5] {$P$} (-1.75,2.5) to (-1.75,3);
\node[zxnode=\zxwhite] at (0,2.5){$y$};
\node[zxnode=\zxwhite] at (0,0) {$x$};
\end{tz}
=
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,2) to [out=45] (0.75,3);
\draw (0,2) to [out=135] (-0.75,3);
\draw[arrow data={0.2}{>}, arrow data={0.8}{>}] (1.75,0) to [looseness=0.9] node[zxnode=\zxwhite, pos=0.5] {$P$} (-1.75,2.5) to (-1.75,3);
\node[zxvertex=\zxwhite, zxup] at (0,2){};
\node[zxnode=\zxwhite] at (-0.75,3) {$y$};
\node[zxnode=\zxwhite] at (0.75,3) {$y'$};
\node[zxnode=\zxwhite] at (0,0) {$x$};
\end{tz}
\superequalseq{eq:quantumfunction}
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (0,0.75) to [out=45] (0.75,1.75) to (0.75,3);
\draw (0,0.75) to [out=135] (-0.75,1.75) to (-0.75,3);
\draw[arrow data={0.2}{>}, arrow data={0.9}{>}] (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9] node[zxnode=\zxwhite, pos=0.36] {$P$} node[zxnode=\zxwhite, pos=0.64] {$P$}(-1.75,3);
\node[zxvertex=\zxwhite, zxup] at (0,0.75){};
\node[zxnode=\zxwhite] at (-0.75,3) {$y$};
\node[zxnode=\zxwhite] at (0.75,3) {$y'$};
\node[zxnode=\zxwhite] at (0,0) {$x$};
\end{tz}
=
\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw  (0.75,0.85) to (0.75,3);
\draw (-0.75,0.85) to (-0.75,3);
\draw[arrow data={0.2}{>}, arrow data={0.9}{>}] (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9] node[zxnode=\zxwhite, pos=0.36] {$P$} node[zxnode=\zxwhite, pos=0.64] {$P$}(-1.75,3);
\node[zxnode=\zxwhite] at (-0.75,3) {$y$};
\node[zxnode=\zxwhite] at (0.75,3) {$y'$};
\node[zxnode=\zxwhite] at (0.75,0.85) {$x$};
\node[zxnode=\zxwhite] at (-0.75,0.85) {$x$};
\end{tz}$$ All other expressions are similar translations of and .

It is natural to arrange these projectors in an $|X| \times |Y|$ matrix. From this perspective, equation states that the projectors along each row form a complete orthogonal family, while equation requires this for each column. In the work of Banica et al, matrices of projectors obeying both the row and the column equations are called *magic unitaries* [@Banica2007], while in the work of Atserias et al they are called *projective permutation matrices* [@Atserias2016]. In this paper, we adopt the latter terminology.

Theorem \[thm:quantumfunctionsinprojectors\] has the following immediate corollary.

\[cor:quantumelementmeasurement\]A quantum function between sets $X\to Y$ is a family of projective measurements with outcomes in $Y$, controlled by the set $X$. In particular, a quantum element of a set $X$ is a projective measurement with outcomes in $X$.

\[rem:ppmcomposition\] At the level of matrices of projectors, the composition of quantum functions $P:X\to Y$ and $Q:Y \to Z$ (see equation ) takes the following form:

(QP)\_[x,z]{} =\_[y Y]{} Q\_[y,z]{}P\_[x,y]{}

This coincides with composition of quantum functions in the Kleisli category of Abramsky et al [@Abramsky2017].

Examples of projective permutation matrices are provided by the first author’s *quantum Latin squares* [@Musto2015; @Musto2016]; more examples are given in Section \[sec:semisimple\].

We now show that quantum bijections only exist between classical sets of the

If there is a quantum bijection from a classical set $X$ to a classical set $Y$, then $|X| = |Y|$. In other words, every projective permutation matrix is square.

By Theorem \[thm:dual2\], a quantum bijection $P: H\otimes X \to Y \otimes H$ is unitary. In particular, $|X|\dim(H) = \dim(X\otimes H) =  \dim(H\otimes Y) =  |Y| \dim(H)$.

\[rem:teleportation\] We remark that there are quantum functions and quantum bijections between noncommutative algebras. We suggest that these structures might also play a role in quantum information theory. For example, unitary error bases[^13] — providing the basic data for quantum teleportation and dense coding schemes [@Werner2001] — give rise to quantum bijections from the matrix algebra $\mathrm{Mat}_n$ to the set $[n^2]$ with $n^2$ elements. Similar correspondences have been noted in the work of Stahlke [@Stahlke2016].

Quantum graph theory {#sec:qgt}
====================

In the first sections of this paper, we have presented a quantisation of the theory of finite sets and functions. In the following, we continue this general approach and quantise the theory of finite undirected graphs, unifying and extending the work of various authors on nonlocal games [@Cameron2007; @Mancinska2016; @Atserias2016], noncommutative topology [@Banica2005; @Banica2009; @Banica2007_2; @Bichon2003], operator algebras [@Weaver2010; @Kuperberg2012; @Weaver2015] and quantum information [@Duan2013; @Stahlke2016].

By analogy with classical graphs, we define a quantum graph as a quantum set of vertices together with a quantum adjacency matrix.[^14] We define a quantum graph homomorphism as a quantum function preserving the quantum adjacency matrix, and show that quantum graphs and quantum graph homomorphisms naturally form a concrete dagger $2$-category $\QGraph$. We then define quantum graph isomorphisms, and show that these are precisely the dagger-dualisable $1$-morphisms in $\QGraph$.

For a classical graph $G$, we denote its set of vertices by $V_G$; for vertices $v,w\in V_G$ we write $v\sim_G w$ if $v$ and $w$ are connected in $G$. We consider only undirected graphs.

Quantum graphs via adjacency matrices {#sec:qgraphsbyadjmats}
-------------------------------------

A classical graph $G$ can be described by its vertex set $V_G$ and its *adjacency matrix*, which is a linear map $G:V_G\to V_G$ (see Terminology \[not:setalgebra\]) with coefficients $G_{v,w}=1$ if $v\sim_G w$ and $G_{v,w} = 0$ otherwise.

This suggests the following definition of a quantum graph as a quantum set equipped with a quantum adjacency matrix.

\[def:quantumgraphsbyadjmats\] A *quantum graph* is a pair $(A,G)$ of a quantum set $A$ (the *quantum set of vertices*) and a self-adjoint linear map $G:A \to A$ (the *quantum adjacency matrix*) satisfying the following equations:

\[eq:propadjacency\]

(0,0) to (0,0.5) to \[out=135, in=-135,looseness=1.5\] node\[zxnode=, pos=0.5\] [$G$]{} (0,2.5) to (0,3); (0,0.5) to \[out=45, in=-45,looseness=1.5\] node\[zxnode=, pos=0.5\] [$G$]{} (0,2.5); at (0,0.5); at (0,2.5);

=

(0,0) to node\[zxnode=, pos=0.5\] [$G$]{} (0,3);

&

(1,0) to (1,1.5) to \[out=up, in=up, looseness=2.5\]node\[zxvertex=, pos=0.5\] (0,1.5) to \[out=down, in=down, looseness=2.5\]node\[zxvertex=, pos=0.5\] (-1,1.5) to (-1,3); at (0,1.5) [$G$]{};

=

(0,0) to (0,3); at (0,1.5) [$G$]{};

For a classical set $A=V_G$, this reduces to the definition of an adjacency matrix $\{G_{v,w}\}_{v,w\in V_G}$; from left to right, the conditions state that $G_{v,w}^2 = G_{v,w}$, and that $G_{v,w} = G_{w,v}$.

A quantum graph is *reflexive* or *irreflexive* if one of the following additional equations holds: $$\includegraphics[trim={1cm 0 1cm .35cm},valign=c]{reflexivity.pdf}$$ For classical graphs this corresponds to $G_{v,v}=1$ or $G_{v,v}=0$, respectively. For a classical set, the definition of an irreflexive quantum graph therefore reduces to the standard definition of an adjacency matrix of a simple graph.

\[rem:literatureqgraph\]There are many related definitions of noncommutative or quantum graphs in the literature [@Kuperberg2012; @Weaver2010; @Weaver2015; @Duan2013], with applications in quantum error correction [@Weaver2015] and zero-error communication [@Duan2013]. In Section \[app:quantumrelation\], we comment on how our quantum graphs correspond to these previous definitions. In particular, we prove the following:=-2

-   Our reflexive quantum graphs coincide with Weaver’s finite-dimensional quantum graphs [@Weaver2015], defined in terms of symmetric and reflexive quantum relations [@Kuperberg2012; @Weaver2010].

-   Our reflexive quantum graphs $(\mathrm{Mat}_n, G)$ on matrix algebras coincide with Duan, Severini and Winter’s noncommutative graphs [@Duan2013].

Quantum graph homomorphisms {#sec:quantumgraphhomandiso}
---------------------------

Having defined quantum graphs, we now quantise graph homomorphisms. As with quantum functions and quantum sets, we have classical homomorphisms between quantum graphs, quantum homomorphisms between classical graphs and quantum homomorphisms between quantum graphs. We show that our quantum homomorphisms and quantum isomorphisms between classical graphs coincide with the quantum graph homomorphisms of Mančinska et al [@Mancinska2016] and the quantum graph isomorphisms of Atserias et al [@Atserias2016]. We also show that our classical and quantum homomorphisms between quantum graphs are ‘pure’ versions of Stahlke’s quantum graph homomorphisms [@Stahlke2016].

To quantise graph homomorphisms, we first express them via Gelfand duality in terms of string diagrams in the category of finite-dimensional Hilbert spaces and linear maps. For a quantum graph — a quantum set $A$ with quantum adjacency matrix $G:A\to A$ — we introduce the following notation: $$\label{eq:graphprojector1}\begin{tz}[zx]
\draw[string] (0, 0) to (0,3);
\draw (2.5,0) to (2.5, 3);
\draw (0, 1.5) to (2.5, 1.5) ;
\node[zxvertex=\zxwhite] at (0,1.5){};
\node[zxvertex=\zxwhite] at (2.5,1.5){};
\node[zxnode=\zxwhite] at (1.25, 1.5 ) {$G$};
\end{tz}
~~~:=~~~
\begin{tz}[zx,xscale=2.5/3]
\draw (-1.5,0) to (-1.5,1.5) to [out=up, in=-135] (-0.75, 2.5) to (-0.75,3);
\draw (-0.75, 2.5) to [out=-45, in=up] (0, 1.5) to [out=down, in=135] (0.75,0.5) to (0.75,0);
\draw (0.75,0.5) to [out=45, in=down] (1.5,1.5) to (1.5,3);
\node[zxnode=\zxwhite] at (0, 1.5) {$G$};
\node[zxvertex=\zxwhite, zxdown] at (-0.75, 2.5) {};
\node[zxvertex=\zxwhite, zxup] at (0.75, 0.5) {};
\end{tz}
~~~\superequalseq{eq:propadjacency}~~~
\begin{tz}[zx,xscale=-2.5/3]
\draw (-1.5,0) to (-1.5,1.5) to [out=up, in=-135] (-0.75, 2.5) to (-0.75,3);
\draw (-0.75, 2.5) to [out=-45, in=up] (0, 1.5) to [out=down, in=135] (0.75,0.5) to (0.75,0);
\draw (0.75,0.5) to [out=45, in=down] (1.5,1.5) to (1.5,3);
\node[zxnode=\zxwhite] at (0, 1.5) {$G$};
\node[zxvertex=\zxwhite, zxdown] at (-0.75, 2.5) {};
\node[zxvertex=\zxwhite, zxup] at (0.75, 0.5) {};
\end{tz}$$ If $(V_G,G)$ is a classical graph, it can easily be verified that this map  is a projector onto the following subset (or equivalently onto the commutative subalgebra corresponding to this subset): $$\label{eq:projectorsubset1}\left\{ (v,w) ~|~ v \sim_G w \right\} \subseteq V_G \times V_G$$ We can use these projectors to express the notion of a classical graph homomorphism diagrammatically:

Let $(V_G,G)$ and $(V_H,H)$ be classical graphs. Under Gelfand duality, a graph homomorphism $G\to H$ corresponds to a $*$-cohomomorphism $f:V_G\to V_H$ fulfilling the following equation: $$\label{eq:classicalgraphhomomorphism}\begin{tz}[zx,yscale=0.8]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.5] {$f$} (0,5);\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.5] {$f$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G$};
\end{tz}
~~~=~~~
\begin{tz}[zx,yscale=0.8]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.5] {$f$} (0,5);\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.5] {$f$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G$};
\draw[string] (0, 4) to (\d,4);
\node[zxvertex=\zxwhite] at (0,4){};
\node[zxvertex=\zxwhite] at (\d,4){};
\node[zxnode=\zxwhite] at (\d/2, 4 ) {$H$};
\end{tz}
~~
\begin{tz}[zx]
\end{tz}$$

Since  is a projector onto the subset , equation  is simply expressing that if $v\sim_G w$, then $f(v) \sim_H f(w)$.

We quantise this notion following our usual philosophy.

\[def:quantumgraphhom\] Let $(A,G)$ and $(B,H)$ be quantum graphs. A *quantum homomorphism* $(H,P) : (A,G) \to (B,H)$ is a quantum function $(H,P): A \to B$ fulfilling the following additional equation: $$\label{eq:quantumgraphhomomorphism}\begin{tz}[zx,yscale=0.8,xscale=-1]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.57] {$P$} (0,5);\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.43] {$P$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G$};
\draw[string, arrow data={0.08}{>},arrow data={0.5}{>}, arrow data ={0.95}{>}] (3, -0.5)  to (3,0.5) to [out=up, in=down] (-1.,4) to (-1.,5);
\end{tz}
~=~
\begin{tz}[zx,yscale=0.8,xscale=-1]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.57] {$P$} (0,5);\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.43] {$P$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G$};
\draw[string] (0, 4) to (\d,4);
\node[zxvertex=\zxwhite] at (0,4){};
\node[zxvertex=\zxwhite] at (\d,4){};
\node[zxnode=\zxwhite] at (\d/2, 4 ) {$H$};
\draw[string, arrow data={0.08}{>}, arrow data ={0.5}{>},arrow data ={0.95}{>}] (3, -0.5)  to (3,0.5) to [out=up, in=down] (-1.,4) to (-1.,5);
\end{tz}$$

It is possible to have ordinary homomorphisms between quantum graphs (that is, [$*$-cohomomorphisms]{} obeying or equivalently one-dimensional quantum homomorphisms), quantum homomorphisms between classical graphs and quantum homomorphisms between quantum graphs.

Expressing a quantum homomorphism between classical graphs in terms of its family of projectors $\{P_{v,w}\!\}_{v\in V_G, w\in V_H}$, fulfilling , this condition becomes:=-2 $$\label{eq:qgraphhomprojcond} v\sim_G v' \text{ and }w\not\sim_H w'\hspace{0.75cm} \Rightarrow \hspace{0.75cm} P_{v',w'} P_{v,w} = 0$$

\[rem:quantumhomMancinska\]Mančinska and Roberson [@Mancinska2016] define quantum graph homomorphisms between classical graphs $G$ and $H$ as perfect quantum strategies — strategies involving measurements on a shared entangled resource — for a certain bipartite nonlocal *graph homomorphism game*. This work generalises the earlier quantum graph colouring game [@Avis2006] and the corresponding notion of the quantum chromatic number of a graph [@Cameron2007].[^15]

In [@Mancinska2016], the existence of such a perfect strategy is expressed in terms of a family of projectors $\{P_{v,w}\}_{v\in V_G, w\in V_H}$ which form a quantum homomorphism in the sense of Definition \[def:quantumgraphhom\].

\[prop:mancinskagraphhom\] Given graphs $G$ and $H$, there is a perfect quantum strategy for the graph homomorphism game defined in [@Mancinska2016], if and only if there is a nonzero family of projectors $\{P_{v,w}\}_{v\in V_G, w\in V_H}$ fulfilling equation  and  — or equivalently, if and only if there is a nonzero quantum homomorphism $ (H, P): (V_G,G)\to (V_H,H)$.

Quantum functions are themselves perfect quantum strategies for a *function game*, whose deterministic classical strategies correspond to classical functions between finite sets. In this game, a verifier sends an element of a finite set $X$ to Alice and Bob, who in turn return an element of another set $Y$. A strategy is perfect if Alice and Bob return the same element $y\in Y $ whenever they receive the same element $x\in X$. Of course, every such game admits a classical strategy.

\[rem:stahlkegraphhoms\] Stahlke [@Stahlke2016] defines homomorphisms [@Stahlke2016 Definition 7] and quantum homomorphisms [@Stahlke2016 Definition 15] (there called entanglement assisted homomorphisms) between quantum graphs on endomorphism algebras (cf. Definition \[def:operatorsystem\] and Proposition \[prop:quantumgraphDuanthesame\]), and relates them to zero-error strategies for quantum source-channel coding in various scenarios.

Stahlke’s notions of homomorphism and quantum homomorphism are defined in terms of ‘mixed’ completely positive trace preserving (CPTP) maps which, if restricted to the ‘pure’ setting of $*$-homomorphisms, agree with our definitions.[^16]

Quantum graph isomorphisms {#sec:qisosofgraphs}
--------------------------

Recall that a classical *graph isomorphism* is an invertible graph homomorphism whose inverse is also a graph homomorphism. This condition can be more concisely expressed as follows.

Let $G$ and $H$ be classical graphs. Under Gelfand duality, a graph isomorphism $G\to H$ corresponds to a $*$-isomorphism $f:V_G \to V_H$ fulfilling the $$\label{eq:classicalgraphiso}
\begin{tz}[zx,every to/.style={out=up, in=down},scale=1]
\draw (0,0) to (0,3);
\path (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9]  node[zxnode=\zxwhite, pos=0.5] {$f$}(-1.75,3);
\node[zxnode=\zxwhite] at (0,0.9){$G$};
\end{tz}
~~~= ~~~
\begin{tz}[zx,every to/.style={out=up, in=down},scale=1]
\draw (0,0) to (0,3);
\path (1.75,0) to (1.75,0.75) to  [looseness=1.1, in looseness=0.9]  node[zxnode=\zxwhite, pos=0.5] {$H$}(-1.75,3);
\node[zxnode=\zxwhite] at (0,0.9){$f$};
\end{tz}$$

This is well-known, but will also follow as a corollary of Theorem \[thm:dualisablequantumgraph\].

As in Section \[sec:twocharacterisations\], we can define a quantum graph isomorphism either as a quantum bijection fulfilling a quantised version of , or as a dualisable quantum graph homomorphism in the 2-category  of quantum graphs, quantum graph homomomorphisms and intertwiners, which we will shortly define. In fact, we will show in Theorem \[thm:dualisablequantumgraph\] that, as with quantum bijections, both these approaches lead to the same notion of quantum graph isomorphism.

\[def:quantumgraphiso\] Let $(A,G)$ and $(A',G')$ be quantum graphs. A *quantum isomorphism* $(H,P): (A,G)\to (A',G')$ is a quantum bijection $(H,P): A \to A'$ fulfilling the following additional equation:

\[eq:quantumgraphisomorphism\]

(0,0) to (0,3); (1.75,0) to (1.75,0.75) to \[looseness=1.1, in looseness=0.9\] node\[zxnode=, pos=0.5\] [$P$]{}(-1.75,3); at (0,0.9)[$G$]{};

=

(0,0) to (0,3); (1.75,0) to \[looseness=0.9\] node\[zxnode=, pos=0.5\] [$P$]{} (-1.75,2.5) to (-1.75,3); at (0,2.35) [$G'$]{};

Expressing quantum isomorphisms between classical graphs in terms of their underlying projective permutation matrix $\{P_{v,w}\}_{v\in V_G, w\in V_{G'}}$, which fulfils  and , the quantum isomorphism condition becomes: $$\label{eq:ppmquantumgraphcondition1}
\forall~a\in V_{G},~b \in V_{G'}:\hspace{1cm}\sum_{i \in \mathrm{nbh}_{G}(a)} P_{i,b} = \sum_{j \in \mathrm{nbh}_{G'}(b)} P_{a,j}$$ Here, $\mathrm{nbh}_{G}(a)$ and $\mathrm{nbh}_{G'}(b)$ denote the set of neighboring vertices of $a$ and $b$ in $G$ and $G'$, respectively. Equivalently, this condition can be expressed as follows: $$\label{eq:ppmquantumgraphcondition2}\text{If }\left(v\sim_{G}v'\text{ and }w\not\sim_{G'}w'\right)\text{ or }\left(v\not\sim_{G} v'\text{ and }w\sim_{G'} w'\right)\hspace{0.5cm} \Rightarrow\hspace{0.5cm} P_{v',w'} P_{v,w} = 0$$

The equivalence between  and  was proven by Atserias et al. [@Atserias2016 Theorem 5.8], but will also follow from Theorem \[thm:dualisablequantumgraph\] and the fact that a quantum isomorphism is a dualisable quantum homomorphism whose dual $\overline{P}$ is also a quantum homomorphism.

\[rem:Atseriasquantumiso\] Atserias et al [@Atserias2016] define quantum graph isomorphisms between classical graphs as perfect quantum strategies for the *graph isomorphism game*, which is a symmetric version of the graph homomorphism game of Mančinska and Roberson (see Remark \[rem:quantumhomMancinska\]).

As with quantum graph homomorphisms, Atserias et al. show that such perfect quantum strategies exist if and only if there is a projective permutation matrix forming a quantum isomorphism in the sense of Definition \[def:quantumgraphiso\].

\[prop:Atserias\]Given classical graphs $G$ and $G'$, there is a perfect quantum strategy for the graph isomorphism game defined in [@Atserias2016], if and only if there is a nonzero family of projectors $\{P_{v,w}\}_{v\in V_G, w\in V_{G'}}$ fulfilling equations ,  and  — or equivalently, if and only if there is a nonzero quantum isomorphism $(H,P):(V_G,G) \to (V_{G'},G')$.=-2

The 2-category $\QGraph$ {#sec:qgraph}
------------------------

We now show that these new structures again form a 2-category under composition, which we call $\QGraph$.

\[def:2catqgraph\] The 2-category $\QGraph$ is built from the following structures:

-   **objects** are quantum graphs $(A,G),(A',G')$, ...;

-   **1-morphisms** $(A,G)\!\begin{tikzpicture}\node at (0,0){};\draw[->](0,0)--(0.25,0);\end{tikzpicture}\, (\!A',G')$ are quantum homomorphisms $(H,P)\!:\!\!(A,G)\!\begin{tikzpicture}\node at (0,0){};\draw[->](0,0)--(0.25,0);\end{tikzpicture}(\!A',G')$;=-5

-   **2-morphisms** $(H,P)\!\begin{tikzpicture}\node at (0,0){};\draw[->](0,0)--(0.25,0);\end{tikzpicture}\, (\!H', P')$ are intertwiners of the underlying quantum functions (see Definition \[def:intertwiner\]).

As with $\QBij \subset \QSet$, we may define a subcategory $\QIso \subset \QGraph $ of quantum graphs, quantum graph isomorphisms and their intertwiners.

As with $\QSet$, there is a forgetful dagger $2$-functor $F:\QGraph \to \BHilb$ mapping each quantum homomorphism to its underlying Hilbert space and each intertwiner to its corresponding linear map. This $2$-functor makes $\QGraph$ a concrete dagger $2$-category $(\QGraph, F)$ (see Definition \[def:Hilb2category\]).

\[rem:last\] Every quantum homomorphism between quantum graphs $(A,G)$ and $(B,H)$ is a quantum function between the underlying quantum sets of vertices $A$ and $B$. Since an intertwiner of quantum homomorphisms is exactly an intertwiner of the underlying quantum functions, it follows that the category $\QGraph((A,G),(B,H))$ is a full subcategory of the category $\QSet(A,B)$. In other words, there is a forgetful $2$-functor $\QGraph \to \QSet$ which is locally fully faithful.

Dualisable morphisms in 
------------------------

We now show that a quantum isomorphism is nothing other than a dagger-dualisable (see Definition \[def:daggerdualisable\]) quantum homomorphism.

\[thm:dualisablequantumgraph\] A quantum homomorphism is dagger-dualisable in $\QGraph$ if and only if it is a quantum isomorphism.

Let $(A,G)$ and $(A',G')$ be quantum graphs and let $(H,P)$ be a dagger-dualisable quantum homomorphism between them. In particular, $(H,P)$ is a dagger-dualisable quantum function — and therefore by Theorem \[thm:dual2\] a quantum bijection. Moreover, the dual $(H^*,\conj{P})$, defined in , is a quantum homomorphism from $(A',G')$ to $(A,G)$, i.e. it fulfills the following equation: $$\label{eq:dualisquantumhom}
\begin{tz}[zx,yscale=0.8,xscale=-1]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.57] {$\conj{P}$} (0,5);
\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.43] {$\conj{P}$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G'$};
\draw[string, arrow data={0.08}{<}, arrow data ={0.5}{<},arrow data ={0.95}{<}] (3, -0.5)  to (3,0.5) to [out=up, in=down] (-1.,4) to (-1.,5);
\end{tz}
~~~=~~~
\begin{tz}[zx,yscale=0.8,xscale=-1]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.57] {$\conj{P}$} (0,5);
\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.43] {$\conj{P}$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G'$};
\draw[string] (0, 4) to (\d,4);
\node[zxvertex=\zxwhite] at (0,4){};
\node[zxvertex=\zxwhite] at (\d,4){};
\node[zxnode=\zxwhite] at (\d/2, 4 ) {$G$};
\draw[string, arrow data={0.08}{<}, arrow data ={0.5}{<},arrow data ={0.95}{<}] (3, -0.5)  to (3,0.5) to [out=up, in=down] (-1.,4) to (-1.,5);
\end{tz}$$ Recalling  and using , we rotate this equation by 180 degree to the left and obtain: $$\begin{tz}[zx,yscale=0.8,xscale=-1]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.57] {$P$} (0,5);\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.43] {$P$} (\d,5);
\draw[string] (0, 4) to (\d,4);
\node[zxvertex=\zxwhite] at (0,4){};
\node[zxvertex=\zxwhite] at (\d,4){};
\node[zxnode=\zxwhite] at (\d/2, 4 ) {$G'$};
\draw[string, arrow data={0.08}{>}, arrow data ={0.5}{>},arrow data ={0.95}{>}] (3, -0.5)  to (3,0.5) to [out=up, in=down] (-1.,4) to (-1.,5);
\end{tz}
~~~=~~~
\begin{tz}[zx,yscale=0.8,xscale=-1]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.57] {$P$} (0,5);\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.43] {$P$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G$};
\draw[string] (0, 4) to (\d,4);
\node[zxvertex=\zxwhite] at (0,4){};
\node[zxvertex=\zxwhite] at (\d,4){};
\node[zxnode=\zxwhite] at (\d/2, 4 ) {$G'$};
\draw[string, arrow data={0.08}{>}, arrow data ={0.5}{>},arrow data ={0.95}{>}] (3, -0.5)  to (3,0.5) to [out=up, in=down] (-1.,4) to (-1.,5);
\end{tz}
~~~\superequalseq{eq:quantumgraphhomomorphism}~~~
\begin{tz}[zx,yscale=0.8,xscale=-1]
\draw[string] (0,-0.5) to node[front,zxnode=\zxwhite,pos=0.57] {$P$} (0,5);\draw[string] (\d,-0.5) to node[front,zxnode=\zxwhite, pos=0.43] {$P$} (\d,5);
\draw[string] (0, 0.5) to (\d,0.5);
\node[zxvertex=\zxwhite] at (0,0.5){};
\node[zxvertex=\zxwhite] at (\d,0.5){};
\node[zxnode=\zxwhite] at (\d/2, 0.5 ) {$G$};
\draw[string, arrow data={0.08}{>},arrow data={0.5}{>}, arrow data ={0.95}{>}] (3, -0.5)  to (3,0.5) to [out=up, in=down] (-1.,4) to (-1.,5);
\end{tz}$$ Contracting with the unit on the bottom left and the counit on the top right recovers condition .

For the converse, we note that a quantum isomorphism in the sense of Definition \[def:quantumgraphiso\] is in particular a quantum bijection and therefore commutes both with comultiplication , multiplication  and the graphs . Therefore, it is clearly a quantum homomorphism  whose dual is also a quantum homomorphism .

Following Remark \[rem:monoidalsubcats\], we can think of the monoidal categories\
$\QIso((A,G),(A,G))$ of quantum automorphisms of a quantum graph $(A,G)$ as a noncommutative or quantum version of the automorphism group of this quantum graph.=-2

\[rem:Banicagraph\] Based on Wang’s ‘quantum symmetry groups’ [@Wang1998] (see Section \[sec:Wang\]), Banica [@Banica2005] introduced[^17] ‘quantum automorphism groups’ of finite classical graphs as noncommutative variants of their automorphism groups.

We now show that our quantum graph automorphism categories are the categories of finite-dimensional representations of the Hopf $C^*$-algebras corresponding to these quantum automorphism groups. This can again be understood as asserting that our quantum graph automorphisms are quantum elements of these quantum groups (cf. Section \[sec:Wang\] and Theorem \[thm:universalprop\]).

\[prop:Banica\] Let $(V_G,G)$ be a classical graph. The category $\QIso((V_G,G), (V_G,G))$ is the category of finite-dimensional representations of Banica’s ‘quantum automorphism group’ algebra $A_{aut}(G)$ of the graph $G$ (see e.g. [@Banica2007_2 Definition 2.1]).

The algebra $A_{aut}(G)$ is defined as the $C^*$-algebra with generators $a_{i,j}~(i,j=1,\ldots,n)$ and relations (cf. Theorem 2.1 and Example 2.2 in [@Banica2005]):

a\_[i,j]{}\^2=a\_[i,j]{} = a\_[i,j]{}\^\* & \_[i=1]{}\^n a\_[i,j]{} = 1,   1jn & \_[j=1]{}\^n a\_[i,j]{} =1,   1in

\_[k=1]{}\^n G\_[i,k]{}  a\_[k,j]{}  =  \_[k=1]{}\^n a\_[i,k]{}  G\_[k,j]{}

Here $n$ is the number of vertices of the graph $G$ and $\{G_{i,j}\}_{1\leq i,j \leq n}$ is the adjacency matrix of $G$.=-2

Similar to the proof of Proposition \[prop:Wang\], comparing these relations with equations ,  and  shows that $\QIso((V_G,G),(V_G,G))$ is the category of finite-dimensional representations of $A_{aut}(G)$.

The semisimple structure of quantum functions {#sec:semisimple}
=============================================

In this section, we investigate more closely the categories of quantum functions $\QSet(A,B)$ between quantum sets $A$ and $B$ and show that they are *semisimple*. This sheds light on the role played by the intertwiners and is crucial to our understanding of the structure of quantum functions, particularly with a view towards distinguishing genuinely quantum functions from essentially classical ones.

Semisimplicity is a categorical structure which commonly arises in representation theory. The paradigmatic example of a semisimple category is the category of finite-dimensional representations of a finite group; in this category there are a number of *irreducible* representations and every representation splits as a direct sum of these ‘simple objects’. As we will now show, categories of quantum functions are similar; every quantum function from $A$ to $B$ may be decomposed into a direct sum of irreducible quantum functions.

The direct sum of quantum functions {#sec:dirsumqfcts}
-----------------------------------

The *direct sum* of two quantum functions $(H,Q)$ and $(H',P)$ is defined as $(H\oplus H', Q\oplus P)$, where $Q\oplus P$ is the following direct sum of the underlying linear maps:=-2

\[eq:directsum\]

(0,1) to (2,3); (2,1) to node\[zxnode=, pos=0.5\][$Q\oplus P$]{} (0,3); at (0,1) [$A$]{}; at (0,3) [$H\oplus H'$]{}; at (2,3) [$B$]{}; at (2,1) [$H\oplus H'$]{};

=

(0,1) to (2,3); (2,1) to node\[zxnode=, pos=0.5\][$Q$]{} (0,3); at (0,1) [$A$]{}; at (0,3) [$H$]{}; at (2,3) [$B$]{}; at (2,1) [$H$]{};

(0,1) to (2,3); (2,1) to node\[zxnode=, pos=0.5\][$P$]{} (0,3); at (0,1) [$A$]{}; at (0,3) [$H'$]{}; at (2,3) [$B$]{}; at (2,1) [$H'$]{};

In particular, if $A$ and $B$ are sets, and $(H,P)$ and $(H',Q)$ are quantum functions from $A$ to $B$, then the direct sum of the corresponding matrices of projectors has underlying Hilbert space $H\oplus H'$ and projectors: $$\left(P \oplus Q\right)_{a,b} = P_{a,b} \oplus Q_{a,b}$$ We now remark on the operational interpretation of the direct sum of quantum =-2

\[rem:opintofdirsum\] In Remark \[rem:opintofquantumfunctions\], we observed that a quantum function between classical sets is a projective measurement controlled by an input element, whose result determines an output element. Operationally, a quantum function is a direct sum precisely when the following procedures coincide:

-   Perform the quantum measurement $(H \oplus H'\!, [P \oplus Q]_{a,-})$ depending on a received input $a$.=-2

-   Before receiving any input, perform a projective measurement onto $H$ and $H'$, and then, depending on the outcome, perform the quantum measurement $(H,P_{a,-})$ or $(H',Q_{a,-})$ upon receiving the input $a$.

In the setting of nonlocal games [@Mancinska2016; @Atserias2016], this can be understood as corresponding to a probabilistic mixture of quantum strategies.

On the other hand, a quantum function $P$ is simple if it cannot be decomposed in this way; or equivalently, if there are no non-trivial intertwiners $P \to P$.

\[def:simpleobject\] A quantum function $P$ is *simple* if $\QSet(P,P) \cong \mathbb{C}$.

For a quantum function $P$ between classical sets, simplicity translates into the following condition on the corresponding matrix of projectors:

\[eq:simplePPM\]X (H): P\_[a,b]{}X = XP\_[a,b]{}   aA, bB X\_[H]{}

The category of quantum functions $\QSet(A,B)$ is completely determined by the simple quantum functions, as the following theorem shows.

\[thm:semisimple\] For quantum sets $A$ and $B$, $\QSet(A,B)$ is a semisimple dagger category.

We defer the proof of this theorem to Section \[app:semisimplicity\]. It is completely independent of the following Sections \[sec:dirsumqfcts\] and \[sec:fusionstructure\].

The definition of semisimplicity is given in Section \[app:semisimplicity\]; it implies that every quantum function is a finite direct sum of simple quantum functions, which cannot be decomposed any further.

In particular, every classical function is a simple quantum function (cf. Remark \[rem:setsubset\]).

In contrast to many semisimple categories considered in the , most of the semisimple categories we consider have an infinite number of =-2

The only exceptions are the categories of quantum elements (and of course the categories of quantum functions to a one-element set which have a unique simple object).

Every quantum set has a finite number of simple quantum elements.

The category $\QEl(A) = \QSet(*,A)$ is the category of comodules of $A$ and as such the opposite of the category of modules of $A$. Since every symmetric special Frobenius algebra is semisimple (in the algebraic sense) there is only a finite number of inequivalent irreducible representations — these are the simple quantum elements.

\[prop:simpleelsofclasssetareordinaryels\] Simple quantum elements of a classical set are ordinary elements.

A classical set is a commutative $C^*$-algebra. In particular, all its irreducible representations are one-dimensional, i.e. classical elements.

There is a close connection between semisimplicity and classicality of quantum functions, which we capture by the following definition.

\[def:classical\] A quantum function $Q:X\to Y$ between classical sets $X$ and $Y$ is *essentially classical* if it is a direct sum of classical functions, i.e. of one-dimensional quantum functions. A quantum element of a classical set is *essentially classical* if it is essentially classical as a quantum function from the one-element set.

In other words, an essentially classical quantum function is of the following form, where $\{\ket{i}\}$ is an orthonormal basis corresponding to the decomposition of the Hilbert space $H$ into one-dimensional subspaces $H\cong \bigoplus_{i} \mathbb{C} \ket{i}$ and $f_i:X\to Y$ are classical functions:$$\label{eq:classicalquantumfunction}\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (2,3);
\draw[arrow data ={0.2}{>}, arrow data={0.8}{>}] (2,0) to (0,3);
\node[zxnode=\zxwhite] at (1,1.5) {$P$};
\node[dimension,left] at (0,0) {$X$};
\node[dimension,right] at (2,3) {$Y$};
\node[dimension,right] at (2,0) {$H$};
\node[dimension,left] at (0,3){$H$};
\end{tz}
~=~\sum_i~\begin{tz}[zx,every to/.style={out=up, in=down},xscale=-1]
\draw (0,0) to (2,3);
\draw[arrow data ={0.8}{>}] (0,2.) to (0,3);
\draw[arrow data ={0.4}{>}] (2,0) to (2,1);
\node[zxnode=\zxwhite] at (1,1.5) {$f_i$};
\node[zxnode=\zxwhite] at (0,2.) {$i$};
\node[zxnode=\zxwhite] at (2,1) {$i^\dagger$};
\end{tz}$$ The following proposition justifies Definition \[def:classical\].

\[prop:classicalcommute\]A quantum function $P:X\to Y$ between classical sets $X$ and $Y$ is essentially classical if and only if all corresponding projectors $P_{xy}$ commute with each other.

Commuting projectors are simultaneously diagonalizable; all the projectors therefore split as a direct sum over the shared eigenspaces. Conversely, every essentially classical quantum function decomposes into a direct sum of classical functions; all projectors $P_{xy}$ are therefore sums of projectors onto the orthonormal basis vectors corresponding to this decomposition.

In the terminology of Definition \[def:classical\], every projective measurement — thought of as a quantum function from the one-element set to its outcome set — is essentially classical. Indeed, non-classical behaviour only becomes apparent if there are at least two projective measurements; that is, when the quantum function goes from a set with two or more elements to an outcome set. Only in these cases does it make sense to distinguish between essentially classical quantum functions, which correspond to measurements of commuting observables, and non-classical quantum functions. From the nonlocal game perspective [@Mancinska2016], essentially classical quantum graph homomorphisms are mixtures of classical homomorphisms that only use the available quantum ressource as a generator of shared classical randomness.

In this terminology, every Latin square and all quantum elements of a classical set are essentially classical, while the quantum Latin square in  and the quantum elements of certain quantum sets are not. In fact, we can prove the following simple lemma.

Quantum sets whose quantum elements are all essentially classical are classical sets.

All simple quantum elements of such a quantum set are one-dimensional; it follows that the corresponding algebra is commutative, i.e. an ordinary set.

The categories of quantum graph homomorphisms $\QGraph((A,G),(A',G'))$ are also semisimple (see Corollary \[cor:semisimplegraph\]). The following proposition shows that a quantum graph homomorphism is simple precisely when its underlying quantum function is.

\[prop:graphhomsimpleifffunctionsimple\] A quantum graph homomorphism $Q:(A,G)\to (A',G')$ is simple in $\QGraph((A,G),(A',G'))$ if and only if its underlying quantum function $Q:A\to A'$ is simple in $\QSet(A,A')$. Moreover, suppose that $Q:(A,G)\to (A',G')$ is a quantum homomorphism and that $Q$ has a decomposition $Q\cong \bigoplus_i f_i$ into simple quantum functions $f_i$ in $\QSet(A,A')$. Then, each $f_i$ is a quantum graph homomorphism $(A,G)\to (A,G')$ and the decomposition is a decomposition in $\QGraph((A,G),(A',G'))$.

The proposition follows from the fact that $\QGraph((A,G),(A',G')) \subseteq \QSet(A,A')$ is a full inclusion of semisimple categories (see Remark \[rem:last\]).

Therefore, the question of semisimplicity of a quantum graph homomorphism is simply a question of semisimplicity of the underlying quantum function and does not depend on the graphs. Despite this result, finding the simple objects in the category of quantum homomorphisms between two quantum graphs is quite involved.

The fusion structure of quantum bijections {#sec:fusionstructure}
------------------------------------------

The category $\QSet(A,A)$ of quantum functions from a quantum set $A$ to itself possesses various other structures which interact with the semisimple structure. In particular, under composition of quantum functions, it becomes a *monoidal* semisimple dagger category. If we restrict further to quantum bijections $\QBij(A,A)$, then by the results of Section \[sec:quantumbijection\] we obtain a monoidal semisimple dagger category with dualisable objects[^18] (see Theorem \[thm:dual2\]). For a finite number of simple objects such a structure is known as a *unitary fusion category*; such structures generalise finite groups, and have been the subject of considerable research in recent years [@Etingof2015].

As noted in Section \[sec:Wang\], these quantum permutation categories have been considered in finite noncommutative topology. We restate some of the results of this work now.=-2

All quantum bijections on an $n$-element classical sets with $n\leq 3$ are essentially classical.

By Proposition \[prop:classicalcommute\], we need to show that all projectors in a projective permutation matrix of size $1,2$ and $3$ commute. For $n=1$, this is trivial. For $n=2$, this follows from the fact that every projective permutation matrix is of the form $$\left(\begin{array}{cc} p& 1-p\\ 1-p & p \end{array} \right)$$ for some projector $p$. The proof for $n=3$ is rather involved and can be found in [@Banica2007].

Note that there are quantum bijections between 4-element classical sets that are not essentially classical; these include the quantum Latin square  of dimension 4 in Example \[ex:latinsquaresexample\], and the following projective permutation matrix where $p$ and $q$ are non-commuting projectors on a 2-dimensional Hilbert space: $$\begin{pmatrix}p&1-p&0&0\\1-p&p&0&0\\0&0&q&1-q\\0&0&1-q&q\end{pmatrix}$$ In fact, the general structure of the category of quantum bijections between 4-element sets has been investigated by Banica and Bichon [@Banica2009], leading in particular to the following surprising result regarding the dimension of quantum bijections (recall Definition \[def:qfctdimension\]).

Every simple quantum bijection between 4-element sets must have dimension 1,2 or 4.

Similarly, the monoidal semisimple dagger categories of quantum graph automorphisms $\QIso(G,G)$ have been studied [@Banica2005; @Banica2007_2; @Banica2007_3; @Bichon2003], and several graphs with only essentially classical quantum automorphisms have been identified.

Essentially classical quantum bijections (in the sense of Definition \[def:classical\]) on the $n$-element set $[n]$ form a full fusion subcategory of $\QBij([n], [n])$ equivalent to the category of $S_n$-graded vector spaces [@Etingof2015], where $S_n$ is the symmetric group (also cf. Remark \[rem:setsubset\]). Similarly, essentially classical quantum graph automorphisms on a classical graph $G$ form a full fusion subcategory of $\QIso(G,G)$ equivalent to the category of $\Aut(G)$-graded vector spaces, where $\Aut(G)$ is the automorphism group of $G$.

Proof of semisimplicity {#app:semisimplicity}
-----------------------

In the following section, we show that the hom-categories $\QSet(A,B)$ for quantum sets $A$ and $B$ are semisimple. Recall that a linear category (that is, a category enriched in vector spaces over some field) is semisimple [@Mueger2003], if it has direct sums, if all idempotents split and if there are objects $X_i$ (called *simple objects*) labeled by an indexing set $I$ such that $\Hom(X_i,X_j) \cong \delta_{i,j} \mathbb{C}$ and such that every object $V$ is isomorphic to a finite direct sum of simple objects. For dagger categories such as those in this paper, this notion of semisimplicity is subsumed by more fundamental properties.

A *linear dagger category* is a dagger category enriched in finite-dimensional complex vector spaces such that for objects $X$ and $Y$ the induced function $\dagger: \Hom(X,Y) \to \Hom(Y,X)$ is antilinear. A linear dagger category is *positive*, if for every morphism $A\to[r]B$:$$r^\dagger r= 0 \hspace{1cm}\Rightarrow \hspace{1cm}r=0$$

\[thm:daggerpositive\]For two quantum sets $A$ and $B$, the category $\QSet(A,B)$ is a positive linear dagger category.

By Theorem \[thm:QSetdagger2category\], $\QSet(A,B)$ is a dagger category. Linearity and positivity follow from the existence of the forgetful dagger functor

Following Müger, Roberts and Tuset, we define semisimplicity of such a dagger category as follows [@Mueger2004 Definition 2.2].

A *semisimple dagger category* is a linear dagger category for which the following hold:

1.  It is positive.

2.  It has a zero object; that is an object such that every object has a unique morphism into and out of it.

3.  It has binary direct sums (cf. [@Vicary2011], there called dagger biproducts): For objects $X_1$ and $X_2$, there is an object $X_1\oplus X_2$ and morphisms $s_i:X_i \to X_1\oplus X_2$ ($i=1,2$) such that the following hold:

    s\_i\^s\_i = \_[X\_i]{} i=1,2& s\_1s\_1\^+s\_2s\_2\^=\_[X\_1X\_2]{}

4.  All dagger idempotents split (cf. [@Selinger2008]): A dagger idempotent is an endomorphism $p\in \End(X)$ on some object $X$ such that $p^2=p =p^\dagger$. It splits if there is a morphism $i: A\to X$ out of some object $A$ such that the following hold:

    i\^i = \_A & i i\^= p

An object $X$ in a semisimple dagger category is *simple*, if $\Hom(X,X)\cong \mathbb{C}$.

It is well known that semisimple dagger categories are semisimple in the usual sense (for a proof for monoidal semisimple dagger categories, see e.g. [@Mueger2007 Lemma 1.35]). For completeness, we sketch a version of this argument.

In a semisimple dagger category, non-isomorphic simple objects $X$ and $Y$ are disjoint ($\Hom(X,Y) = \{0\}$) and every object is isomorphic to a finite direct sum of simple objects.

It is a straightforward consequence of positivity that non-isomorphic simple objects are disjoint. Moreover, given an object $X$, then the dagger makes $\Hom(X,X)$ into a positive $*$-algebra. Since every positive $*$-algebra is semisimple, it follows that if $X$ is not simple, there is a non-trivial dagger idempotent in $\Hom(X,X)$ which we can split to obtain an isometry $i:A\to X$ and use this to decompose $X\cong A \oplus A^\bot$. Continuing inductively, every non-simple object can be decomposed into a finite sum of simple objects.

We are now ready to restate and prove Theorem \[thm:semisimple\].

**Theorem \[thm:semisimple\].** *For quantum sets $A$ and $B$, $\QSet(A,B)$ is a semisimple dagger category.*

1\. Positivity of $\QSet(A,B)$ is proven in Proposition \[thm:daggerpositive\].

2\. The zero object is the quantum function $(\mathbf{0}, 0)$, where $\mathbf{0}$ is the zero-dimensional Hilbert space and $0$ is the unique morphism $0:  \mathbf{0} \otimes A \to B \otimes \mathbf{0}$.

3\. The direct sum of two quantum functions is defined in and inherits all its structural properties from $\Hilb$.

4\. A dagger idempotent in $\QSet(A,B)$ is a self-adjoint idempotent endomorphism $r: H \to H$ on a quantum function $Q:H\otimes A \to B \otimes H$:

\[eq:idempotentsplit\]

(0,0) to (2,2); (2,0) to node\[zxnode=,pos=0.5\] [$Q$]{} node\[zxnode=, pos=0.2\] [$r$]{} (0,2);

=

(0,0) to (2,2); (2,0) to node\[zxnode=,pos=0.5\] [$Q$]{} node\[zxnode=, pos=0.8\] [$r$]{} (0,2);

In particular, we can split this idempotent in , obtaining an isometry $i:V\to H$ such that $ii^\dagger = r$. It then follows from that

(0,0) to (2,2); (2,0) to node\[zxnode=,pos=0.5\] [$Q'$]{} (0,2); at (2,0) [$V$]{}; at (0,2) [$V$]{};

:=

(0,0) to (2,2); (2,0) to node\[zxnode=,pos=0.5\] [$Q$]{} node\[zxnode=, pos=0.2\] [$i$]{}node\[zxnode=, pos=0.8\] [$i^\dagger$]{} (0,2); at (2,0) [$V$]{}; at (0,2) [$V$]{};

is itself a quantum function and the isometry $i:V\to H$ is an intertwiner of quantum functions $ Q' \to Q$. Therefore, $r$ splits as an idempotent in $\QSet(A,B)$.

Essentially the same proof works for the 2-category $\QGraph$.

\[cor:semisimplegraph\]For quantum graphs $(A,G)$ and $(B,H)$, the category $\QGraph((A,G),(B,H))$ is semisimple.

Quantum graphs and quantum relations {#app:quantumrelation}
====================================

In this final section, we discuss the relational approach to quantum graphs taken by Kuperberg, Weaver, Duan, Severini, Winter, and others [@Kuperberg2012; @Weaver2010; @Weaver2015; @Duan2013; @Ortiz2016] and compare it to our Definition \[def:quantumgraphsbyadjmats\]. We show that our quantum graphs can indeed be understood as symmetric and reflexive quantum relations as defined by Kuperberg and Weaver [@Kuperberg2012; @Weaver2015] and therefore generalise the noncommutative graphs of Duan, Severini and Winter [@Duan2013].

In this section, to fit with the work of other authors, all graphs and quantum graphs will be reflexive (see Definition \[def:quantumgraphsbyadjmats\]); wherever ‘graph’ is written it should be taken to mean ‘reflexive graph’.

The relational approach starts from the observation that a classical graph $G$ may be described as a reflexive and symmetric relation on its vertex set $V_{G}$; that is, a subset $S\subseteq V_G \times V_{G}$ containing both the diagonal $\Delta=\{(x,x)~|~x\in V_G\}$ and such that $(x,y)\in S\Leftrightarrow (y,x) \in S$ for all $x,y\in V_{G}$.

Quantising this description leads to a notion of quantum graph equivalent to Definition \[def:quantumgraphsbyadjmats\] which is closer in spirit to previous definitions [@Duan2013; @Weaver2010; @Weaver2015]. We first quantise relations, recovering the finite-dimensional quantum relations of Kuperberg and Weaver [@Weaver2010; @Kuperberg2012].

Under Gelfand duality, a binary relation between two finite sets $X$ and $Y$ can be expressed as a projector $\!P\!:X\! \otimes Y \!\!\to \!X \otimes Y$ satisfying the following equation:=-2 $$\label{eq:bimodulerelation}
\def\scl{1.25}
\begin{tz}[zx,every to/.style={out=up, in=down},scale=\scl]
\draw (0,0) to (0,2);
\draw (1,0) to (1,2);
\draw (-0.5,0) to[in=-135] (0,0.6);
\draw (1.5,0) to [in=-45] (1,0.6);
\boxwidth{1.25}
\node[widebox] at (0.5,1.25) {$P$};
\node[zxvertex=\zxwhite] at (0,0.6){};
\node[zxvertex=\zxwhite] at (1,0.6){};
\node[dimension,left] at (0,-0.1) {$X$};
\node[dimension, left] at (-0.5,-0.1) {$X$};
\node[dimension,right] at (1.5,-0.1) {$Y$};
\node[dimension, right] at (1,-0.1) {$Y$};
\node[dimension, left] at (0., 2) {$X$};
\node[dimension, right] at (1, 2) {$Y$};
\end{tz} 
~~=~~
\begin{tz}[zx,every to/.style={out=up, in=down},scale=\scl]
\draw (0,0) to (0,2);
\draw (1,0) to (1,2);
\draw (-0.5,0) to[in=-150] (0,1.4);
\draw (1.5,0) to [in=-30] (1,1.4);
\boxwidth{1.25}
\node[widebox] at (0.5,0.75) {$P$};
\node[zxvertex=\zxwhite] at (0,1.4){};
\node[zxvertex=\zxwhite] at (1,1.4){};
\node[dimension,left] at (0,-0.1) {$X$};
\node[dimension, left] at (-0.5,-0.1) {$X$};
\node[dimension,right] at (1.5,-0.1) {$Y$};
\node[dimension, right] at (1,-0.1) {$Y$};
\node[dimension, left] at (0., 2) {$X$};
\node[dimension, right] at (1, 2) {$Y$};
\end{tz}$$

Projectors on $X\otimes Y$ encode subspaces of $X\otimes Y$; the bimodule condition  guarantees that the corresponding subspace is the linear span of a *subset* of $X\times Y$.

We define quantum relations analogously.

\[def:quantumrelations\] A *quantum relation* between quantum sets $A$ and $B$ is a projector\
${P: A \otimes B \to A \otimes B}$ satisfying equation . A *quantum relation on a quantum set $A$* is a quantum relation between $A$ and itself.

\[rem:quantumrelationprojection\]Let $A$ and $B$ be finite-dimensional $C^*$-algebras. Given a projector\
$P\in \End(A\otimes B)$ fulfilling equation , we obtain a projection[^19] $p:=P(e_A\otimes e_B)\in A^{op}\otimes B$; conversely, any projection $p\in A^{op}\otimes B$ gives rise to a projector $P:=L_p \in \End(A\otimes B)$ fulfilling . (Here, $A^{op}$ denotes the opposite algebra of $A$, $e_A\in A,~e_B\in B$ denote the units of $A$ and $B$, and $L_p$ denotes left multiplication with $p$ in the algebra $A^{op}\otimes B$.) A quantum relation between $A$ and $B$ may therefore be equivalently defined as a projection in the algebra $A^{op} \otimes B$. Plugging units into the second and third slot of equation  gives a simple diagrammatic proof of this fact.

Kuperberg and Weaver [@Weaver2010; @Kuperberg2012] define a quantum relation on a von Neumann algebra $\mathcal{M}\subseteq \mathcal{B}(H)$ to be a weak$^*$-closed operator bimodule over the commutant $\mathcal{M}'$ (see Definition 2.1 in [@Weaver2010]). In the finite-dimensional case (see Definition 5.1 in [@Weaver2015]), this definition reduces to the following:

\[KuperbergWeaverQreldef\]Let $A$ be a finite-dimensional $C^*$-algebra, let $H$ be some finite-dimensional Hilbert space such that $A\subseteq \End(H)$ and let $A'=\{b \in \End(H)~|~ ba=ab~\forall a\in A\}$ be the commutant with respect to this embedding. A *quantum relation in the sense of Kuperberg and Weaver* is a subspace $V\subseteq \End(H)$ which fulfills $A' V A'\subseteq V$.

It is shown in Theorem 2.7 of [@Weaver2010] that this definition is independent[^20] of the embedding $A\subseteq \End(H)$. We now show that, in the finite-dimensional case, this definition is equivalent to our own.

\[prop:WeaverKuperberg\] Given a finite-dimensional $C^*$-algebra $A$, there is a Hilbert space $H$ and an embedding $A\subseteq \End(H)$ such that our notion of quantum relation on $A$ (Definition \[def:quantumrelations\]) coincides with that of Kuperberg and Weaver (Definition \[KuperbergWeaverQreldef\]).

As noted in Remark \[rem:quantumrelationprojection\], our quantum relations on a finite-dimensional $C^*$-algebra $A$ can be expressed as projections in $A^{op}\otimes A$; Weaver proves in [@Weaver2010 Proposition 2.23] that quantum relations in the sense of Kuperberg-Weaver on finite-dimensional $C^*$-algebras correspond precisely to such projections.

For concreteness, we will now provide an alternative proof using the Frobenius structure on the $C^*$-algebra. We have seen in Section \[sec:diagramsforC\*\] that a finite-dimensional $C^*$-algebra $A$ admits the structure of a symmetric special dagger Frobenius algebra. In particular, $A$ admits the structure of a Hilbert space, and there is an embedding of $C^*$-algebras $A\subseteq \End(A)$ given as follows:

A(A) & aL\_a (:bA ab)

We now show that the corresponding commutant $A'$ is $*$-isomorphic to the opposite algebra $A^{op}$, defined on the vector space $A$ with multiplication $a\star b:= ba$. The following linear map is clearly a faithful $*$-homomorphism:

A\^[op]{} A’ & aR\_a(:bA ba)

We now show that it is also surjective and therefore a $*$-isomorphism. Let $X:A\to A$ be an element of $A'$, and denote the unit of $A$ by $e\in A$. Then $X(e)\in A$ and we will show that $R_{X(e)}=X$. For all $b\in A$ the following holds: $$R_{X(e)} (b) = b X(e) = L_b X(e) ~~\superequals{$X\in A'$}~~ X L_b(e) = X(b)$$ A quantum relation in the sense of Kuperberg and Weaver is therefore a subspace $\mathcal{V} \subseteq \End(A)$ such that $R_a\mathcal{V} R_b \subseteq \mathcal{V}$ for all $a,b\in A$. Since $A$ is a symmetric Frobenius algebra, there is a canonical isomorphism $A\cong A^*$ which induces an isomorphism $\End(A) \cong A \otimes A$. Under this isomorphism, left and right composition with $R_a$ in $\End(A)$ can be identified with left and right multiplication with $(a\otimes e) $ and $(e\otimes a)$ in $A\otimes A$, respectively:

R\_a - : (A) (A) & -R\_b: (A) (A)\
(ae) - : AAAA & -(eb) : AA AA

Therefore, a quantum relation in the sense of Kuperberg and Weaver can be understood as a subspace $\mathcal{V} \subseteq A\otimes A $ such that $(a\otimes e)\mathcal{V}(e\otimes b)\subseteq \mathcal{V}$ for all $a,b\in A$.

This coincides with our Definition \[def:quantumrelations\].

Following Weaver [@Weaver2015], we now consider additional properties of quantum relations, such as symmetry and reflexivity.

\[def:quantumgraphsbyrelations\] A quantum relation $P:A\otimes A\to A \otimes A$ is *symmetric* or *reflexive* if one of the following additional equations holds:

\[eq:symrefrelation\]

(0,0.5) to (0,1.) to \[out=up, in=up,looseness=1.75\] node\[zxvertex=, pos=0.5\] (2.5,1.) to (2.5,-1); (1,0.5) to (1,1.) to \[out=up, in=up,looseness=3\] node\[zxvertex=, pos=0.5\](1.5,1.) to (1.5,-1); (-0.5,2.5) to (-0.5,0.5) to \[out=down, in=down, looseness=3\] node\[zxvertex=, pos=0.5\] (0,0.5); (-1.5,2.5) to (-1.5,0.5) to \[out=down, in=down, looseness=1.75\]node\[zxvertex=, pos=0.5\] (1,0.5); at (0.5,0.75) [$P$]{};

   =   

(0,0) to (0, 3); (1,0) to (1,3); at (0.5, 1.5)[$P$]{};

&

(-0.3,0) rectangle (1.3,3); (0,3) to (0,1) to \[out=down, in=down\] node\[zxvertex=, pos=0.5\] (1,1) to (1,3); at (0.5,2)[$P$]{};

   =   

(-0.2,0) rectangle (1.2,3); (0,3) to (0,2) to \[out=down, in=down\]node\[zxvertex=, pos=0.5\] (1,2) to (1,3);

\
&

We now show that quantum graphs as in Definition \[def:quantumgraphsbyadjmats\] are indeed symmetric and reflexive quantum relations. For a quantum graph $(A,G)$ as in Definition \[def:quantumgraphsbyadjmats\], we introduce the following linear map $P_G:A\otimes A \to A \otimes A$: $$\label{eq:graphprojector}
\begin{tz}[zx]
\draw[string] (0, 0) to (0,3);
\draw (1.5,0) to (1.5, 3);
\boxwidth{1.5}
\node[widebox] at (0.75, 1.5 ) {$P_G$};
\end{tz}
~~~=~~~
\begin{tz}[zx]
\draw[string] (0, 0) to (0,3);
\draw (2.5,0) to (2.5, 3);
\draw (0, 1.5) to (2.5, 1.5) ;
\node[zxvertex=\zxwhite] at (0,1.5){};
\node[zxvertex=\zxwhite] at (2.5,1.5){};
\node[zxnode=\zxwhite] at (1.25, 1.5 ) {$G$};
\end{tz}
~~~:=~~~
\begin{tz}[zx,xscale=2.5/3]
\draw (-1.5,0) to (-1.5,1.5) to [out=up, in=-135] (-0.75, 2.5) to (-0.75,3);
\draw (-0.75, 2.5) to [out=-45, in=up] (0, 1.5) to [out=down, in=135] (0.75,0.5) to (0.75,0);
\draw (0.75,0.5) to [out=45, in=down] (1.5,1.5) to (1.5,3);
\node[zxnode=\zxwhite] at (0, 1.5) {$G$};
\node[zxvertex=\zxwhite, zxdown] at (-0.75, 2.5) {};
\node[zxvertex=\zxwhite, zxup] at (0.75, 0.5) {};
\end{tz}
~~~\superequalseq{eq:propadjacency}~~~
\begin{tz}[zx,xscale=-2.5/3]
\draw (-1.5,0) to (-1.5,1.5) to [out=up, in=-135] (-0.75, 2.5) to (-0.75,3);
\draw (-0.75, 2.5) to [out=-45, in=up] (0, 1.5) to [out=down, in=135] (0.75,0.5) to (0.75,0);
\draw (0.75,0.5) to [out=45, in=down] (1.5,1.5) to (1.5,3);
\node[zxnode=\zxwhite] at (0, 1.5) {$G$};
\node[zxvertex=\zxwhite, zxdown] at (-0.75, 2.5) {};
\node[zxvertex=\zxwhite, zxup] at (0.75, 0.5) {};
\end{tz}$$ For a classical graph $(V_G,G)$, it is easily verified that this map  is the projector onto the subspace of the symmetric and reflexive relation defining the graph: $$\label{eq:projectorsubset}\left\{ (v,w) ~|~ v \sim_G w \right\} \subseteq V_G \times V_G$$ Conversely, the adjacency matrix $G$ can be recovered from this projector as follows: $$\label{eq:recoveradjacency}
\begin{tz}[zx,scale=\scl]
\draw (0,0) to (0,2);
\node[zxnode=\zxwhite] at (0,1) {$G$};
\end{tz}
~~~:=~~~
\begin{tz}[zx,scale=\scl]
\draw (0,0) to (0,1) to [out=up, in=up,looseness=2.5] node[zxvertex=\zxwhite, pos=0.5] {} (-0.5,1) to (-0.5,-0.25);
\draw (0.75,0) to (0.75,1.75);
\boxwidth{1}
\node[widebox] at (0.375,0.65){$P_G$};
\node[zxvertex=\zxwhite] at (0,0){};
\node[zxvertex=\zxwhite] at (0.75,0){};
\end{tz}
~~~\superequalseq{eq:bimodulerelation}~~~
\begin{tz}[zx,scale=\scl]
\draw (0,-0.25) to (0,1.3);
\draw (0.75,0) to (0.75,1.75);
\boxwidth{1}
\node[widebox] at (0.375,0.65){$P_G$};
\node[zxvertex=\zxwhite] at (0,1.3){};
\node[zxvertex=\zxwhite] at (0.75,0){};
\end{tz}
~~~\superequals{$(-)^\dagger$}~~~
\begin{tz}[zx,xscale=-1,scale=\scl]
\draw (0,-0.25) to (0,1.3);
\draw (0.75,0) to (0.75,1.75);
\boxwidth{1}
\node[widebox] at (0.375,0.65){$P_G$};
\node[zxvertex=\zxwhite] at (0,1.3){};
\node[zxvertex=\zxwhite] at (0.75,0){};
\end{tz}
~~~\superequalseq{eq:bimodulerelation}~~~
\begin{tz}[zx,xscale=-1,scale=\scl]
\draw (0,0) to (0,1) to [out=up, in=up,looseness=2.5] node[zxvertex=\zxwhite, pos=0.5] {} (-0.5,1) to (-0.5,-0.25);
\draw (0.75,0) to (0.75,1.75);
\boxwidth{1}
\node[widebox] at (0.375,0.65){$P_G$};
\node[zxvertex=\zxwhite] at (0,0){};
\node[zxvertex=\zxwhite] at (0.75,0){};
\end{tz}$$ The same correspondence holds for general quantum graphs.

\[thm:relationadjacency\]Given a quantum graph $(A,G)$ as in Definition \[def:quantumgraphsbyadjmats\], the projector\
[$P_G:A\otimes A\to A \otimes A$]{} defined in equation  is a symmetric and reflexive quantum relation as in Definition \[def:quantumrelations\]. Conversely, given a symmetric and reflexive quantum relation $P$ on $A$, the map  defines a quantum adjacency matrix. These two constructions are mutually inverse.

Given an arbitrary linear map $G:A\to A$, we define the following linear map $P_G:A\otimes A\to A \otimes A$ fulfilling :$$\begin{tz}[zx]
\draw[string] (0, 0) to (0,3);
\draw (1.5,0) to (1.5, 3);
\boxwidth{1.5}
\node[widebox] at (0.75, 1.5 ) {$P_G$};
\end{tz}
~~~:=~~~
\begin{tz}[zx,xscale=2.5/3]
\draw (-1.5,0) to (-1.5,1.5) to [out=up, in=-135] (-0.75, 2.5) to (-0.75,3);
\draw (-0.75, 2.5) to [out=-45, in=up] (0, 1.5) to [out=down, in=135] (0.75,0.5) to (0.75,0);
\draw (0.75,0.5) to [out=45, in=down] (1.5,1.5) to (1.5,3);
\node[zxnode=\zxwhite] at (0, 1.5) {$G$};
\node[zxvertex=\zxwhite, zxdown] at (-0.75, 2.5) {};
\node[zxvertex=\zxwhite, zxup] at (0.75, 0.5) {};
\end{tz}$$ Conversely, given a linear map $P_G:A\otimes A \to A\otimes A$ fulfilling , we define $$\begin{tz}[zx,scale=\scl]
\draw (0,0) to (0,2);
\node[zxnode=\zxwhite] at (0,1) {$G$};
\end{tz}
~~~:=~~~
\begin{tz}[zx,xscale=-1,scale=\scl]
\draw (0,-0.25) to (0,1.3);
\draw (0.75,0) to (0.75,1.75);
\boxwidth{1}
\node[widebox] at (0.375,0.65){$P_G$};
\node[zxvertex=\zxwhite] at (0,1.3){};
\node[zxvertex=\zxwhite] at (0.75,0){};
\end{tz}$$ It follows easily from equation  that these two constructions are mutually inverse. In the following, we say that $G$ is *real* if the following holds: $$\begin{tz}[zx]
\draw (0,0) to (0,3);
\node[zxnode=\zxwhite] at (0,1.5) {$G^\dagger$};
\end{tz}
~~~=~~~
\begin{tz}[zx,xscale=-1]
\draw (1,0) to (1,1.5) to [out=up, in=up, looseness=2.5]node[zxvertex=\zxwhite, pos=0.5] {} (0,1.5) to [out=down, in=down, looseness=2.5]node[zxvertex=\zxwhite, pos=0.5] {} (-1,1.5) to (-1,3);
\node[zxnode=\zxwhite] at (0,1.5) {$G$};
\end{tz}$$ Simple graphical arguments then establish the following:

-   $G$ is real if and only if $P_G$ is self-adjoint.

-   $G$ fulfills the first equation of  if and only if $P_G^2=P_G$.

-   $G$ fulfills the second equation of  if and only if $P_G$ is symmetric.

-   $G$ fulfills the last equation of  if and only if $P_G$ is reflexive.

We observed in Remark \[rem:quantumrelationprojection\] that a quantum relation on $A$ can be understood as a projection $p$ in $A^{op}\otimes A $. In terms of the adjacency matrix $G$, the projection corresponding to a quantum graph $(A,G)$ is the following element $p$ of $A\otimes A$: $$\begin{tz}[zx]
\clip (-0.2, -0.8) rectangle (1.2,1.5);
\draw (0,0) to (0,1.5);
\draw (1,0) to (1,1.5);
\boxwidth{1}
\node[widebox] at (0.5,0){$p$};
\end{tz}
~~~=~~~
\begin{tz}[zx]
\clip (-0.2, -0.8) rectangle (1.2,1.5);
\draw (1,1.5) to (1,0) to [out=down, in=down, looseness=2] node[zxvertex=\zxwhite, pos=0.5]{} (0,0) to (0,1.5);
\boxwidth{1}
\node[zxnode=\zxwhite] at (1,0.5){$G$};
\end{tz}$$ In particular, a quantum relation on $A$ given by a projection $p\in A^{op}\otimes A$ is symmetric if $\sigma(p) = p$, where $\sigma:A\otimes A \to A\otimes A$ is the swap map, and reflexive if $m(p)=e_A$, where $m:A\otimes A \to A$ is the multiplication of $A$ and $e_A$ is the unit of $A$.

A related notion of quantum graph was introduced and studied by Duan, Severini and Winter [@Duan2013] as a noncommutative quantum version of the *confusability graphs* in classical zero-error communication. These noncommutative graphs are defined as operator systems on finite-dimensional Hilbert spaces. We now show that such quantum graphs correspond to our quantum graphs on matrix algebras.

\[def:operatorsystem\] Let $H$ be a finite-dimensional Hilbert space. An *operator system* on $H$ is a subspace $\mathcal{V} \subseteq \End(H)$ such that the following hold:

X     X\^ & \_H

We prove that every operator system on $H$ gives rise to a quantum graph $(\End(H), G)$ on the endomorphism algebra $\End(H)$ and vice versa.

\[prop:quantumgraphDuanthesame\]Let $H$ be a finite-dimensional Hilbert space. There is a canonical correspondence between quantum graphs $(\End(H),G)$ on the endomorphism algebra of $H$ and operator systems on $H$.

It is shown in [@Weaver2015] that symmetric and reflexive quantum relations (in the sense of Kuperberg and Weaver) on $\End(H)$ coincide with operator systems on $H$. The proposition therefore follows from Proposition \[prop:WeaverKuperberg\] and Theorem \[thm:relationadjacency\], in which we prove that our notion of quantum graph coincides with Kuperberg and Weaver’s symmetric and reflexive quantum relations. For concreteness, we explicitly construct the correspondence between quantum graphs on endomorphism algebras and operator systems.

An operator system $\mathcal{V}\subseteq \End(H)$ can be described in terms of the projector $P_{\mathcal{V}}:H^*\otimes H \to H^*\otimes H$ onto the subspace $\mathcal{V}\subseteq \End(H)\cong H^* \otimes H$. This projector fulfills the following equations:

\[eq:operatorsystemgraphics\]

(0,0.25) to (0,1.25) to \[out=up, in=up,looseness=1.75\] (2.5,1.25) to (2.5,-1); (1,0.25) to (1,1.25) to \[out=up, in=up,looseness=3\] (1.5,1.25) to (1.5,-1); (-0.5,2.5) to (-0.5,0.25) to \[out=down, in=down, looseness=3\] (0,0.25); (-1.5,2.5) to (-1.5,0.25) to \[out=down, in=down, looseness=1.75\] (1,0.25); at (0.5,0.75) [$P_{\mathcal{V}}$]{};

   =   

(0,0) to (0, 3); (1,0) to (1,3); at (0.5, 1.5)[$P_{\mathcal{V}}$]{};

&

(-0.3,0) rectangle (1.3,3); (0,3) to (0,1) to \[out=down, in=down\] (1,1) to (1,3); at (0.5,2)[$P_{\mathcal{V}}$]{};

   =   

(-0.2,0) rectangle (1.2,3); (0,3) to (0,2) to \[out=down, in=down\] (1,2) to (1,3);

The first equation corresponds to the property that $X\in \mathcal{V}\Rightarrow X^\dagger \in \mathcal{V}$, the second equation encodes that $\mathbbm{1}_H \in \mathcal{V}$.

Let $(\End(H), G)$ be a quantum graph, expressed as a symmetric, reflexive quantum relation $P_G: \End(H) \otimes \End(H) \to \End(H) \otimes \End(H)$ (see Theorem \[thm:relationadjacency\] and Definition \[def:quantumgraphsbyrelations\]). The bimodule equation  can now be expressed as the following first equation; the second equation is obtained from contracting the second wire at the bottom with the third and the sixth with the seventh (here we identify $\End(H) \cong H \otimes H^*$):$$\label{eq:bimodulematrix}
\begin{tz}[zx]
\draw[arrow data={0.15}{<}, arrow data={0.9}{<}] (0,-1.5) to +(0,3);
\draw[arrow data={0.16}{>}, arrow data={0.91}{>}] (1,-1.5) to +(0,3);
\draw[arrow data={0.15}{>}, arrow data={0.91}{>}] (-1.2,-1.5) to [out=up, in=down] (-0.4,0) to (-0.4,1.5);
\draw[arrow data={0.8}{<}] (-0.8, -1.5) to [out=up, in=up, looseness=3] (-0.4,-1.5);
\draw [arrow data={0.15}{<}, arrow data={0.91}{<}](2.2, -1.5) to[out=up, in=down] (1.4,0) to (1.4,1.5);
\draw[arrow data={0.8}{<}] (1.4, -1.5) to [out=up, in=up, looseness=3]  (1.8,-1.5);
\boxwidth{1.8}
\node[widebox] at (0.5, 0.5) {$P_G$};
\end{tz}
~~~=~~~
\begin{tz}[zx]
\draw[arrow data={0.15}{<}, arrow data={0.9}{<}] (0,-1.5) to +(0,3);
\draw[arrow data={0.16}{>}, arrow data={0.91}{>}]  (1,-1.5) to +(0,3);
\draw[arrow data={0.15}{>}, arrow data={0.91}{>}] (-1.2,-1.5) to (-1.2,0) to [out=up, in=down] (-0.4,1.5);
\draw[arrow data={0.12}{<}, arrow data={0.62}{<}, arrow data={0.91}{<}] (-0.8, -1.5) to (-0.8, 0) to  [out=up, in=up, looseness=3] (-0.4,0) to (-0.4, -1.5);
\draw[arrow data={0.15}{<}, arrow data={0.91}{<}] (2.2, -1.5) to (2.2,0) to [out=up, in=down] (1.4,1.5);
\draw[arrow data={0.12}{<}, arrow data={0.41}{<}, arrow data={0.91}{<}]  (1.4, -1.5) to (1.4, 0) to  [out=up, in=up, looseness=3] (1.8, 0) to (1.8, -1.5);
\boxwidth{1.8}
\node[widebox] at (0.5, -0.5) {$P_G$};
\end{tz}
\hspace{1.25cm} \Rightarrow \hspace{1.25cm}
\dim(H)^2~~
\begin{tz}[zx]
\draw[arrow data={0.15}{<}, arrow data={0.85}{<}] (0,-1.5) to (0,1.5);
\draw[arrow data={0.15}{>}, arrow data={0.85}{>}] (1,-1.5) to +(0,3);
\draw[arrow data={0.15}{>}, arrow data={0.85}{>}] (-0.4,-1.5) to + (0,3);
\draw[arrow data={0.15}{<}, arrow data={0.85}{<}] (1.4,-1.5) to + (0,3);
\boxwidth{1.8}
\node[widebox] at (0.5, 0){$P_G$};
\end{tz}
~~~=~~~
\begin{tz}[zx]
\draw[arrow data={0.15}{>}, arrow data={0.85}{>}] (-1.4, -1.5) to + (0,3);
\draw[arrow data={0.15}{<}, arrow data={0.85}{<}] (2.4,-1.5) to + (0,3);
\draw[arrow data={0.15}{<}, arrow data={0.85}{<}] (0,-1.5) to (0,1.5);
\draw[arrow data={0.15}{>}, arrow data={0.85}{>}] (1,-1.5) to +(0,3);
\draw[arrow data={0.18}{>}, arrow data={0.88}{>}] (-0.4,0) to [out=up, in=up, looseness=5] (-1,0) to [out=down, in=down, looseness=5]  (-0.4,0);
\draw[arrow data={0.18}{<}, arrow data={0.88}{<}] (1.4,0) to [out=up, in=up, looseness=5] (2,0) to [out=down, in=down, looseness=5]  (1.4,0);
\boxwidth{1.8}
\node[widebox] at (0.5, 0){$P_G$};
\end{tz}$$ Therefore, quantum relations $P_G: \End(H)\otimes \End(H) \to \End(H) \otimes \End(H)$ can be interconverted into projectors $P_\mathcal{V}:H^*\otimes H \to H^*\otimes H$ as follows:

(0,-1.5) to (0,1.5); (1,-1.5) to +(0,3); at (0.5, 0)[$P_{\mathcal{V}}$]{};

   =    

(0,-1.5) to (0,1.5); (1,-1.5) to +(0,3); (-0.4,0) to \[out=up, in=up, looseness=5\] (-1,0) to \[out=down, in=down, looseness=5\] (-0.4,0); (1.4,0) to \[out=up, in=up, looseness=5\] (2,0) to \[out=down, in=down, looseness=5\] (1.4,0); at (0.5, 0)[$P_G$]{};

&

(0,-1.5) to (0,1.5); (1,-1.5) to +(0,3); (-0.4,-1.5) to + (0,3); (1.4,-1.5) to + (0,3); at (0.5, 0)[$P_G$]{};

   =   

(0,-1.5) to (0,1.5); (1,-1.5) to +(0,3); (-0.4,-1.5) to + (0,3); (1.4,-1.5) to + (0,3); at (0.5, 0)[$P_{\mathcal{V}}$]{};

It follows from equation  that these constructions are mutually inverse. Under this correspondence, the map $P_G$ is a projector if and only if $P_{\mathcal{V}}$ is a projector, $P_G$ is a symmetric quantum relation if and only if $P_\mathcal{V}$ fulfills the first equation of , and $P_G$ is reflexive if and only if $P_{\mathcal{V}}$ fulfills the second equation of .

[^1]: An extensive discussion of related work can be found in Section \[sec:relatedwork\].

[^2]: Here, noncommutative topology refers to the study of $C^*$-algebras in light of Gelfand duality. The term noncommutative geometry is usually reserved for the study of spectral triples (see e.g. [@Connes2000]), a noncommutative version of the theory of Riemannian manifolds.

[^3]: This observation is a version of the famous *Eckmann-Hilton argument* [@Eckmann1962] playing a central role in algebraic topology and higher category theory.

[^4]: The two equations in  express nothing more than the fact that the algebra $\mathbb{C}$ is commutative, while the algebra $\End(H)$ of endomorphisms of a finite-dimensional Hilbert space $H$ is not.

[^5]: Weak dagger 2-categories are the obvious generalisation, with unitary associators and unitors.

[^6]: In , the last equation on the right is redundant, as it follows from the other equations; we include it for completeness.

[^7]: Here, we use $*$-cohomomorphisms instead of the more conventional $*$-homomorphisms of Corollary \[cor:finiteGelfandduality\] to obtain an equivalence with the category of finite sets and not with its opposite. This is a recurring theme throughout this work; we use copyable elements instead of the equivalent characters and comodules instead of modules.

[^8]: If we use a strict version of the monoidal category $\Hilb$, then $\QSet$ is a strict 2-category.

[^9]: All finite-dimensional $C^*$-algebras $A$ are *nuclear*; that is for all $C^*$-algebras $C$, there is a unique norm on the algebraic tensor product; the $C^*$-tensor product $C\otimes A$ is defined as its completion.

[^10]: A $C^*$-representation of $A$ is a $*$-homomorphism $A\to \mathcal{B}(H)$, where $\mathcal{B}(H)$ is the $C^*$-algebra of bounded operators on a Hilbert space $H$.

[^11]: It is straightforward to show directly that a $*$-homomorphism which is also a $*$-cohomomorphism is invertible. However, it is harder to show that an invertible $*$-cohomomorphism is a $*$-homomorphism; this may be a new result.

[^12]: The triangle equations given here are strict but can straightforwardly be weakened to apply to weak 2-categories.

[^13]: A *unitary error basis* is a basis of unitary operators on a finite-dimensional Hilbert space, orthogonal with respect to the trace inner product.

[^14]: In Section \[app:quantumrelation\], we show that these quantum graphs also arise from quantising the edge relation on the vertex set of a graph. This relational approach is closer to the work of previous authors, whereas the adjacency matrix approach has a stronger resemblance to classical graph theory.

[^15]: The quantum chromatic number of a graph $G$ is the smallest $n$ for which there exists a quantum graph homomorphism $G$ to $K_n$, the complete graph on $n$ vertices.

[^16]: More precisely, the pure $*$-homomorphism version of Stahlke’s entanglement assisted homomorphisms agrees with our quantum homomorphisms if the entangled resource is a maximally entangled state; or, in other words, if the positive operator $\Lambda$ used to define entanglement assisted homomorphisms (see [@Stahlke2016 Definition 15]) is the identity on some finite-dimensional Hilbert space $V$.

[^17]: An earlier, related but different definition is due to Bichon [@Bichon2003].

[^18]: It is clear that the tensor unit of $\QBij(A,A)$, i.e. the quantum bijection $\mathrm{id}_A:A\otimes \mathbb{C} \to \mathbb{C} \otimes A$, is simple. Therefore, $\QBij(A,A)$ is a tensor $*$-category as defined in [@Mueger2007 Definition 1.33].

[^19]: A projection $p$ in a $C^*$-algebra $A$ is an element $p\in A$ such that $p^*=p=p^2$.

[^20]: More precisely, it can be shown that if $H$ and $H'$ are finite-dimensional Hilbert spaces such that there are embeddings $A\subseteq \End(H)$ and $A\subseteq \End(H')$, then there is a canonical correspondence between the correspondingly defined quantum relations.
