overview.tex

\chapter{Overview}

Despite almost two decades of research, we still seek new and useful quantum algorithms.  This is of interest where the meaning of useful ranges from ``able to generate experimental evidence against the extended Church-Turing thesis" to ``commercially viable". Better languages, frameworks, and techniques for analyzing the structure of quantum algorithms will aid in these attempts.  One such  programme initiated by Abramsky, Coecke, et. al de-emphasizes the role of Hilbert spaces and linear maps and instead focuses on topological flows of information within quantum-like systems
\cite{abramsky2008categorical,coecke2011interacting,coecke2013new}. This approach captures all the familiar structure of quantum computation - from teleportation  to quantum secret-sharing - and locates the particular setting of Hilbert spaces as an instance of more general
\textbf{process theories}~\cite{coecke2015generalised,qcs-notes,coecke2011categories}. 

This thesis develops a process theoretic approach to the structure of quantum algorithms and protocols, furthering the ``search for structure" in both the foundations and applications of quantum information. We briefly clarify the relationship of this approach to these two domains.
 
\subsubsection*{Foundations}

We consider quantum computation (quantum theory on finite dimensional Hilbert spaces) as an instance of a larger class of process theories. These theories start from a process based axiomatic structure that emphasizes the information processing that occurs in quantum systems. This work thus contributes to existing literature that presents an information theoretic foundation for quantum theory, such as Hardy~\cite{hardy2001quantum}, Chiribella et al.~\cite{chiribella2011informational}, and work in generalized probabilistic theories by Barrett~\cite{barrett2007information}.  Process theoretic generalization focuses on the information processing features of quantum mechanics that generate properties like the quantum Fourier transform (Section ~\ref{sec:strcomplFT}), unitary oracles (Section~\ref{sec:blackbox}), and Mermin non-locality (Chapter~\ref{chap:mermin}). Further, it allows us to consider analogs of complex quantum protocols in alternative physical theories that inhabit new mathematical settings (Section~\ref{sec:qalgrel}).

\begin{figure}[t]
\begin{align*}
\input{tikz/0_outline.tikz}
\end{align*}
\caption[Schematic of process theories and categorical diagrams.]{Schematic of the approach taken in this thesis. Viewing quantum information as a process theories provides a more powerful and diagrammatic approach to presenting quantum protocols.}
\label{fig:overview}
\end{figure}


\subsubsection*{Applications} While there already exist many intriguing applications for quantum information - as quantum computers or quantum communications networks - our knowledge of these applications is often based on isolated techniques. As it has become necessary to consider more advanced applications, the language we have used to describe quantum mechanics has similarly advanced. Differential equations led to matrix mechanics and then to quantum circuits, which have formed the basis for most known quantum algorithms as well as the basis for the current generation of quantum programming languages, e.g. LIQUi$|\rangle$~\cite{wecker2014liqui} and Quipper~\cite{green2013quipper}. Still, these languages are, by a structural standard, more akin to quantum assembly language than high-level programming languages. 

By generalizing from quantum information to process theories (Figure~\ref{fig:overview}), we are able to lift quantum circuit diagrams into a more powerful notation for specifying and verifying algorithms (Chapters~\ref{chap:qalg} and \ref{chap:qDisCo}). This approach handles algorithm analysis with high-level abstractions that are appropriate for advanced applications. As we will show, it allows the function of large classes of blackbox algorithms to be verified with a few diagrammatic arguments. As such, these techniques have an important role to play as we seek to best exploit the structure of quantum theory. 

\subsection*{Outline}

The first two chapters introduce background material. Chapter~\ref{chap:cats} covers the basic categorical diagrams for process theories and connects them to examples, including quantum circuits. Chapter~\ref{chap:cqm} adds known structures to define a \textbf{quantum-like process theory} (QPT). Diagrams for QPTs have additional power on top of quantum circuits that allows direct reasoning about observables, phases, complementarity and measurements. Examples for quantum teleportation and the controlled-not gate are provided.

Chapter~\ref{chap:qalg} contains the first of the main results of this thesis as it applies QPTs to the study of quantum algorithms in three ways.  In Section~\ref{sec:strcomplFT}, we develop a connection between the Fourier transform and strongly complementary observables in a QPT.  This connection is of interest in quantum information where the Fourier transform plays a key role in many algorithms.  The role of strongly complementary observables pinpoints exactly where this particular transformation appears in the structure of quantum theory.  The connection is also of independent mathematical interest, as we give new categorical proofs of Pontryagin duality, the convolution theorem, and the Fourier inversion theorem in arbitrary dagger symmetric monoidal categories. This construction allows us to investigate other mathematical settings where Fourier-like transforms occur, such as in the category of sets and relations.

In Section~\ref{sec:blackbox}, we use the QPT framework and its connection to the Fourier transform to analyze quantum blackbox algorithms.  We begin with a purely abstract construction and proof of unitarity for oracles in arbitrary QPTs. This construction directly connects these unitary oracles with complementary observables. Then, as warmup, we overview Vicary's process theoretic verifications and generalizations  of the Deutsch-Jozsa, single-shot Grover's, and hidden subgroup algorithms from~\cite{vicary-tqa}.  This allows us to introduce a new blackbox quantum algorithm for the group homomorphism identification problem (GROUPHOMID) which, in many cases, offers a large speedup over the optimal classical algorithm. These algorithms are specified and verified using the tools of process theories.

Section~\ref{sec:qalgrel} leverages the QPT presentation of these algorithms to construct a toy model of the Deutsch-Jozsa algorithm, the single-shot Grover's algorithm, and the GROUPHOMID algorithm in the category of sets and relations: a QPT we call QCRel. In a particular sense, these provide non-deterministic classical models for the structure of these quantum algorithms. This section also includes some new mathematical results on self-conjugate comonoid homomorphisms in sets and relations.

Chapter~\ref{chap:mermin} investigates the connection between Mermin non-locality and strongly complementary observables that was first introduced by Kissinger et al.~\cite{coecke2012strong}. We extend this work to cover all arbitrary QPTs by developing the connection between locality and phase groups from Coecke et al.~\cite{coecke2011phase}. This leads us to an easy to check algebraic condition on the phase groups of an QPT that acts as an indicator for Mermin non-locality or locality. In particular, this allows us to show that QCRel (the QPT in sets and relations) is Mermin local despite much of its quantum-like structure. In terms of quantum theory, these results show how to construct a large class of Mermin non-locality experiments for any number of parties, that have access to any number of measurements, on systems of arbitrary dimension.  This is a powerful generalization over the restricted cases that are currently known and we use it further suggest a large class of new quantum secret sharing protocols.

Chapter~\ref{chap:qDisCo} uses recent work in a process theoretic framework from computational linguistics, called distributional compositional (DisCo) linguistics~\cite{clark2008compositional}, to investigate quantum algorithms for computational linguistic tasks. The shared QPT structure of quantum theory and DisCo linguistics makes quantum algorithms particularly apt for this domain, and allows to us improve on the naive application of such algorithms. As an example, we use classical preprocessing to adapt a quantum algorithm for clustering into a sentence classification algorithm with an improved speedup.

We then conclude in Chapter~\ref{chap:outlook} with a brief outlook on future work on blackbox algorithms, the computational complexity of process theories in general, and applications to quantum programming languages.
 
\subsection*{Related Papers}

Material presented in this thesis has developed out of several publications and working papers over the last few years. Much of the material in this thesis has appeared in print in these original sources and specific citations are included in the abstracts of each chapter. Some of this work was completed jointly with other researchers and these sections are also highlighted throughout the next.  Selections from these joint papers are only those that this author contributed significantly towards. We provide a list of these papers in chronological order for convenience:

\begin{enumerate}
\item Zeng, William. Diagramming Quantum Algorithms: The Fourier transform. In \emph{Proceedings of The XXIX International Colloquium on Group-Theoretical Methods in Physics
: Posters}, Tianjin, China, August 2012.
\item Zeng, William and Vicary, Jamie. Abstract structure of unitary oracles for quantum algorithms. \emph{Electronic Proceedings in Theoretical Computer Science} 172, 2014, pp. 270-284.
\item Zeng, William. Models of Quantum Algorithms in Sets and Relations. In preparation.
\item Gogioso, Stefano and Zeng, William. Mermin Non-locality in Abstract Process Theories. \emph{Proceedings of the 12th Intl. Workshop on Quantum Physics and Logic}, Oxford, July 2015.
\item Gogioso, Stefano and Zeng, William. Fourier transforms from strongly complementary observables. In preparation.
\item Zeng, William and Coecke, Bob. Quantum algorithms for compositional natural language processing. In preparation.
\end{enumerate}