Introduction.tex

\chapter{Categories and Diagrams}
\label{chap:cats}
\chapabstract{This chapter introduces basic background material.  We introduce the relevant categorical definitions and show how symmetric monoidal categories can be interpreted as process theories, using quantum circuits as a motivating example.  We then review several other examples of process theories from the literature.}

\section{Monoidal categories}
Monoidal categories (sometimes called tensor categories) provide an abstract structure for processes that are equipped with both sequential and parallel composition. One might be tempted to think of sequential composition as time-like and parallel composition as space-like, but we should be careful to examine this notion in cases like, for example, quantum theory (See Example~\ref{ex:teleport}).  We call a process $f:A\to B$ a \textbf{morphism} from some input $A$ to output $B$. The $A$ and $B$ are called \textbf{objects} and we sometimes say that $f$ is a morphism \textbf{between} them. For morphisms $f:A\to B$ and $g:B\to C$, their \textbf{composite} is a morphism $g\circ f:A\to C$. This data can be structured into a category, which then embodies the notion of sequential composition.\footnote{As a foundational comment, categories in the broadest mathematical literature do not in general require their objects and morphism to be sets. Categories where they do, as defined and used in this thesis, are \emph{small} categories. These details relate to the role categories can play in mathematical foundations \cite{mac1969one}.} We will sometimes leave the objects of morphisms implicit when they can be inferred from context.

\begin{defn}
A \textbf{category} \cat{C} is a set of objects $\objs{C}$ and a set of morphisms $\arrs{C}$ between them, such that for all $A,C,B,D\in \objs{C}$ and all $f:A\to B$, $g:B\to C$, and $h:C\to D$ in $\arrs{C}$:
\begin{itemize}
\item for every pair of morphisms $f,g$, their composite $g\circ f:A\to C$ is also in $\arrs{C}$;
\item composition is associative:
\begin{align}
h\circ(g\circ f) = (h\circ g)\circ f
\end{align}
\item for every object $A$ there is an $\idm{A}:A\to A$ in $\arrs{C}$ called the \textbf{identity morphism} such that for all $f$:
\begin{align}
\idm{B}\circ f = f = f\circ\idm{A}.
\end{align}
\end{itemize}
\end{defn}

A category can thus be thought of as encoding processes where sequences can be associatively composed  and where we always have access to a ``do-nothing`` process, which is the identity morphism. Note that the objects of a category are somewhat superfluous, as they are in one-to-one correspondence with the identity morphisms. Due to this correspondence, we refer interchangeably to an object and its identity morphism. It is because categories are focused on morphisms that we see them as encoding a process theory.

Morphisms and their compositions can be represented in string diagrams:
\begin{equation}
\label{eq:composition}
\input{tikz/1_compositionGraphical.tikz}
\end{equation}
\noindent Here, vertical connectivity (read from bottom to top) represents the flow of morphism composition.

\begin{defn}
A (strict)\footnote{Throughout this thesis we take monoidal categories to be strict, i.e. those associators and unitors are identities.  In fact, every monoidal category is monoidally equivalent to a strict monoidal one~\cite{joyal1993braided}.} \textbf{monoidal category} is a category $\cat{C}$ equipped with a \textbf{categorical tensor} $(-\otimes-):\cat{C}\times\cat{C}\to\cat{C}$ and a \textbf{unit object} $I\in\objs{C}$ that obey:
\begin{equation}
(A\otimes B)\otimes C = A\otimes(B\otimes C),
\end{equation}
\begin{equation}
I\otimes A = A = A\otimes I.
\end{equation}
\end{defn}

Tensor composition is represented by side-by-side placement, and the unit object is the ``empty" diagram:
\begin{equation}
\label{eq:tensor}
\input{tikz/1_tensorGraphical.tikz}
\end{equation}

To interpret this, we consider the objects $A,B$ as \textbf{systems}, so that morphisms $f:A\to B$ are \textbf{processes} from one system to another. Thus $A\otimes C$ is thought of as a composite system with composite morphism $f \tensor g$ that acts independently on its parts. The identity object is interpreted as the empty system, which matches its diagram. We can also define states of systems.

\begin{defn}
\label{defn:state}
A \textbf{state} of $A\in\objs{C}$ is a morphism $\ket{\psi}:I\to A$ drawn as
\begin{equation}
\label{eq:state}
\input{tikz/1_stateDef.tikz}
\end{equation}
\end{defn}

\noindent The state morphism can be thought of as a \emph{preparation} process to create that state: it is a process that starts with nothing and has output of type system. The tensor product of two states, $\ket{\psi}\otimes\ket{\phi}$, corresponds to the usual notion of product state from quantum theory (Example \ref{ex:bellduals}).

\begin{defn}
\label{def:effect}
In a monoidal category, \textbf{effects} on an object $A$ are morphisms $E:A\to I$.
\end{defn}

Similarly to the way states act as preparations, an effect can be thought of as a \emph{test} process. It takes as input some system and outputs the outcome of that test on the system. Thus, the preparation of a system in a certain state $\ket{\psi}$, which is then tested against effect $E,$ has representation:
\begin{equation}
E\circ|\psi\rangle = 
\begin{aligned}
\begin{tikzpicture}[xscale=\tikzxscale, yscale=\tikzyscale]
\node (1) [state] at (0, -0.75) {$\psi$};
\node (2) [state, hflip] at (0, 0.75) {$E$};
\draw (1.center) to (2.center);
\end{tikzpicture}
\end{aligned},
\end{equation}
which is intended to look suggestively like an inner product. Said another way, effects turn systems into outcomes of tests on that system. Coecke and Paquette~\cite{coecke2011categories} provide an instructive example of this interpretation using a monoidal category model of cooking. After introducing additional structure, we will return to the details of effects in quantum-like theories in Section~\ref{sec:dag}.

\section{Symmetric monoidal categories}

\begin{defn}
\label{def:smc}
A monoidal category is \textbf{symmetric} (is an SMC) when it has  isomorphisms
$\sigma_{A,B}:A\otimes B\to B\otimes A$ that satisfy the following graphical equations:
\begin{equation}
\label{eq:symmetry}
\input{tikz/1_symmetryDef.tikz}
\end{equation}
\begin{equation}
\label{eq:symmetry2}
\input{tikz/1_symmetryDef2.tikz}
\end{equation}
\begin{equation}
\label{eq:symmetry3}
\input{tikz/1_symmetryDef3.tikz}
\end{equation}
\end{defn}
\noindent where Equation \ref{eq:symmetry3} for all $f,g$ is the naturality of $\sigma$.

\begin{examples}
\label{ex:smcs}
The following are some explicit examples of SMC's:
\begin{itemize}
\item \cat{Hilb} and \cat{FHilb}, the category where objects are (finite dimensional) Hilbert spaces; morphisms are linear maps; the categorical tensor is the tensor product; the unit object $I=\mathbb{C}$.

\item \cat{Vect} and \cat{FVect}, the category where objects are (finite dimensional) vector spaces; morphisms are linear maps; the categorical tensor is the tensor product; the unit object $I=\mathbb{C}$.

\item \cat{Rel} and \cat{FRel}, the category where objects are (finite) sets; morphisms are relations; the categorical tensor is the cartesian product; the unit object is the singleton set, i.e. $I=\{\bullet\}$.

\item \cat{Set} and \cat{FSet}, the category where objects are (finite) sets; morphisms are functions; the categorical tensor is the cartesian product; the unit object is the singleton set, i.e. $I=\{\bullet\}$.

\item Given a finite group $G$, its representations form an SMC \cat{Rep(G)}, where objects are finite dimensional representations of $G$; morphisms are intertwiners for the group action;\footnote{Linear maps that commute with the action of $G$.} the categorical tensor is the tensor product of representations; the unit object is the trivial action of $G$ on the 1-dimensional vector space.
\end{itemize}
\end{examples}

Some of these examples have customary process theoretic interpretations, such as $\cat{Rel}$ as a setting for nondeterministic classical processes and \cat{FHilb} for quantum computation. We'll elaborate on these interpretations in Section~\ref{sec:PTs}.

It is important to note that the graphical notation we have introduced to describe morphisms in SMCs is not merely a notational convenience. We can reduce all the structural rules for SMCs down to simple diagrammatic equivalence, as the following theorem of Joyal and Street shows.

\begin{theorem}{\cite[Thm 2.3]{joyal1991geometry}}
A well-formed equation between morphisms in a symmetric monoidal category follows from the axioms if and only if it holds in the graphical language up to isomorphism of diagrams.
\end{theorem}

\noindent This emphasizes the power of the diagrammatic presentation.  Rather than needing to check the many different rewrite rules that form the diagrammatic axioms, we need only check that the diagrams are isomorphic.  This will become especially important as we introduce more structure in Chapter~\ref{chap:cqm}.

\subsection{Symmetric monoidal categories \&\ quantum circuits}
\label{sec:smcqc}
\begin{figure}[t]
\input{figures/1_QCDSMC.tex}
\caption[Comparison of quantum circuits and symmetric monoidal diagrams]{On the left we have a quantum circuit (read left to right) and its corresponding categorical diagram in \cat{FHilb} on the right (read bottom to top). In both depictions, the boxes are linear maps and the wires are Hilbert spaces. In quantum circuits these are implicitly qubits, with a slash used to denote products of qubits. In the categorical diagram we explicitly write spaces or leave them generic.}
\label{fig:QCDSMC}
\end{figure}

This thesis applies the structure and graphical calculi for SMCs to the study of protocols and algorithms for and inspired by quantum theory. For this purpose, it can be useful to think of the SMC graphical calculus as mathematical scaffolding that underlies quantum circuit diagrams. See Figure~\ref{fig:QCDSMC} for a concrete example. Note that state preparation is included as a part of the categorical diagram while it is external labeling in the quantum circuit. In $\cat{FHilb}$ we have $I=\mathbb{C}$, and so the states, by Definition \ref{defn:state}, of some Hilbert space $\Hsp$ are exactly maps $\ket{\psi}:\mathbb{C}\to\Hsp$. These are recognized as the usual quantum state vectors $\ket{\psi}\in\Hsp$. This allows states to be manipulated graphically as well, to advantages discussed later. In uncovering the SMC scaffolding of quantum circuits, we can improve it, introducing techniques to reason graphically about more advanced structures that better capture salient features of these processes. We cover these new features in Chapter \ref{chap:cqm}.

\subsection{Other categorical definitions}

We make use of several other standard categorical concepts, whose definitions are reproduced here.

\begin{defn}
From any category \cat{C} we can construct a dual category $\cat{C^{op}}$ where \objs{C^{op}} = \objs{C} and for every morphism $f:A\to B$ in \arrs{C} there is a morphism $g:B\to A$ in \arrs{C^{op}} and vice versa.
\end{defn}

Loosely speaking, we can think of $\cat{C^{op}}$ as a version of \cat{C} where we have turned all the morphisms around so that inputs become outputs. In general this will be a different kind of category than \cat{C}.

\begin{defn}
Given a category $\cat{C}$ and $A,B\in\objs{C}$, the \textbf{homset} Hom$(A,B)$ is the set of morphisms in the category of type $f:A\to B$.
\end{defn}

We can think of Hom$(A,B)$ as all the processes that input system $A$ and output $B$. Sometimes, to specify the category, we write $\cat{C}(A,B)$ for the homset Hom$(A,B)$ in $\cat{C}$.

As we often consider the relationship between categories, we recall the notion of a structure preserving map between categories. In our context they can be thought of as homomorphisms between process theories.

\begin{defn}
Given two categories \cat{C} and \cat{D}, a \textbf{functor} $F:\cat{C}\to\cat{D}$ consists of
\begin{enumerate}
\item A mapping on objects $F:\objs{C}\to\objs{D}::A\mapsto F(A)$
\item A mapping on arrows $F:\cat{C}(A,B)\to\cat{D}(F(A),F(B))::f\mapsto F(f)$ that preserves composition and identities, i.e. 
\begin{enumerate}
\item For $f:A\to B$ and $g:B\to C$ then $F(g\circ f) = F(g)\circ F(f)$
\item $F(1_A)=1_{F(A)}$
\end{enumerate}
\end{enumerate}
\end{defn}

\noindent Monoidal and symmetric monoidal functors also preserve their respective additional structures. For further details, see Coecke and Paquette's introductory ``Categories for the practising physicist"~\cite{coecke2011categories}.

\section{Process theories}
\label{sec:PTs}

We have seen that strict symmetric monoidal categories capture the structure of  diagrammatic languages like quantum circuit diagrams.\footnote{While this thesis chooses to use strict SMC's as process theories, it may be reasonable in other settings to consider non-strict monoidal categories.  These kinds of process theories are certainly still well-formed, but do not have as clean a diagrammatic representation.  We would, for example, need to keep track of how many copies of ``white space" (the monoidal unit) are introduced around a diagram.} For this reason we introduce the following definition:

\begin{defn}
A \textbf{process theory} is a strict symmetric monoidal category where objects are interpreted as systems, morphisms are interpreted as processes, morphism composition is interpreted as sequential process composition, and the monoidal product is interpreted as parallel process composition.
\end{defn}

\noindent Process theories and associated structures on them form the mathematical setting of this thesis.

Monoidal and symmetric monoidal categories were introduced as ``categories with multiplication" by MacLane in \cite{maclane1963natural} and later formalized as string diagrams by~\cite{joyal1991geometry}. There are other examples, besides quantum information, where diagrammatic concepts in computer science and physics have been formalized using SMCs, and these can all be considered as examples of the process theory considered here.  In general, this approach is most useful when processes have both a natural diagrammatic (\emph{geometric}) presentation, but also have an \emph{algebraic} interpretation.

In physics, Penrose's tensor notation \cite{penrose1971applications} is, in modern language, precisely the diagrammatic representation of the symmetric monoidal category $\cat{FVect}$ of finite dimensional vector spaces and linear maps. Feynman diagrams are representations of morphisms in the symmetric monoidal category of positive energy representations of the Poincar\'{e} group \cite{baez2009prehistory}. The symmetric (and braided) monoidal category framework is an important foundation for $n$-dimensional topological quantum field theories. Atiyah~\cite{atiyah1988topological} introduces the idea that one can think of a TQFT as a symmetric monoidal functor between the category of n-cobordisms and finite dimensional vector spaces: $T:\cat{nCob}\to \cat{FVect}$. In fact, Abrams~\cite{abrams1996two} and Kock~\cite{kock2004frobenius} show two-dimensional TQFT's are equivalent to commutative Frobenius algebras, which we introduce later in Definition~\ref{def:frobenius}. Reshetikhin, Turaev, Baez, and Lauda discuss how this perspective also plays an important role in the study of generalized knot invariants~\cite{reshetikhin1990ribbon} and quantum groups~\cite{baez2009prehistory}. 

We also find examples in computer science and control theory. Petri nets, which present naturally in diagrams, have been connected to linear logic through their connection with monoidal categories by several authors \cite{abramsky2008petri,marti1989petri,sassone1998axiomatization}. In particular Marti and Meseguer show how each Petri net, by closure under sequential and parallel composition, makes a suitable kind of symmetric monoidal category \cite{marti1989petri,meseguer1990petri}. Baez and Erbele~\cite{baez2014categories} and Bonchi et al.~\cite{bonchi2014interacting} show that signal-flow diagrams from control theory can be seen as morphisms in the category $\cat{FinRel_k}$ whose objects are finite dimensional vector spaces of the field $k$, whose arrows are linear relations, and whose monoidal product is the direct sum.  In fact the internal monoids, comonoids, and bialgebras that are described in Chapter \ref{chap:cqm} also have a natural interpretation in this setting as investigated by Baez, Erbele~\cite{baez2014categories} and Bonchi et al.~\cite{bonchi2015full}. Bonchi et al. have further used these structures to axiomatize generalized linear algebra using diagrams~\cite{bonchi2014interacting}.
 
In recent work, Baez and Fong have formalized passive linear networks (electrical circuits consisting of inductors, capacitors, and resistors) using symmetric monoidal categories~\cite{baez2015compositional}. Here the relationship between a category of circuits and the Lagrangian representing them is presented as a dagger functor between dagger compact categories. These dagger compact categories are symmetric monoidal categories with additional structure covered Chapter~\ref{chap:cqm}. SMC based string diagrammatic theories also appear in interactive theorem proving~\cite{grov2014tinker}, parallel programming~\cite{michaelson2012reasoning}, programming language semantics \cite{mellies2014local}, and natural language processing \cite{coecke2010mathematical}. This final connection is elaborated on and leveraged in Chapter~\ref{chap:qDisCo}.

The planar diagrams presented in this chapter can be understood as part of a larger $n$-categorical hierarchy. Joyal and Street's~\cite{joyal1991geometry} original work describe monoidal categories as coherent under planar isotopy, and the coherence of higher classes of these graphical languages can be regarded as geometric isotopies in higher dimensions, e.g. coherence for SMCs is up to a 4-dimensional isotopy. Selinger's monoidal category survey provide many examples~\cite{selinger2011survey}. A general reference for the connections between computation, topology, and physics that emerge from symmetric monoidal categories is the Rosetta Stone by Baez and Stay~\cite{baez2011physics}.