QAlgRel.tex

\section{Models of quantum algorithms in sets and relations}
\label{sec:qalgrel}

        In this section, we construct abstract models of blackbox quantum algorithms using a model of quantum computation in sets and relations, a setting that is usually considered for nondeterministic classical computation.  This alternative model of quantum computation (QCRel), though unphysical, nevertheless faithfully models its computational structure.  Our main results are models of the Deutsch-Jozsa, single-shot Grover's, and GroupHomID algorithms in QCRel. These results provide new tools to analyze the protocols from quantum computation and improve our understanding of the relationship between computational speedups and the structure of physical theories. They also exemplify a method of extending physical/computational intuition into new mathematical settings.

\subsection{Introduction}

Having grasped the abstract structure at play in the protocols and algorithms of quantum computation, we can conceive of modelling quantum computation in QPTs other than Hilbert spaces and linear maps.  There are two main thrusts that make this investigation interesting.  The first is to further analyze the structure of quantum computation, focusing on the relationship between computational speedups and the structure of physical theories. We use the QCRel model defined here to analyze some example quantum algorithms as non-deterministic classical algorithms while preserving their query-complexity (and, in fact, all their abstract structure). The second thrust regards the insights that become available by extending physical/computational intuition into new areas of mathematics. While other toy models of a relational flavor for quantum mechanics have been proposed by several authors~\cite{ellermanModelQM,discreteQT,modalQT,spekk}, and some even discuss protocols~\cite{QCFF_James}, these works have not developed the structures necessary to model quantum algorithms.

First we construct our chosen model of quantum information.  This is the QPT in \cat{FRel}, rather than \cat{FHilb}, and it is introduced by rephrasing the axioms of quantum mechanics. Next we present our novel contributions: relational models of unitary oracles, the Deutsch-Jozsa algorithm, the single-shot Grover's algorithm, and the group homomorphism identification algorithm.

\subsection{The model of quantum computation in relations}
\label{sec:modelqcrel}
We begin with definitions of the key components of quantum computation in this new setting, e.g. systems, states, bases, observables, etc.  The following definitions are motivated by Chapter~\ref{chap:cqm}, whose general theorems prove useful. To avoid distracting repetition of notation, we use generic terminology to refer to the relational setting within this section.  For example \textbf{system} is intended to mean \textbf{relational system}, i.e. a set.  When we wish to refer to the quantum setting we explicitly denote this e.g. \textbf{quantum system} refers to a finite dimensional Hilbert space.

\begin{axiom}
A \textbf{system} is a set $H$ with \textbf{states} $|\psi\rangle$ given by subsets $\psi\subseteq H$.
\end{axiom}


\noindent Each state in our notation is a boolean column vector written as a labelled ket, to follow the convention in quantum mechanics where states are complex valued column vectors as in the following example. 
\begin{example}
\label{ex:columnvect}
Consider a three element system $\{0,1,2\}$, the relation $R=\{(0,0),(0,2),(1,1)\}$ and the state $\ket{\psi}=\{0\}$. In terms of boolean matrices and vectors the composition $R\circ\ket{\psi}$ is written as:
\begin{equation}
\left(\begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
\end{array}\right)
\left(\begin{array}{c}
1 \\
0 \\
0 \\
\end{array}\right)
=
\left(\begin{array}{c}
1 \\
0 \\
1 \\
\end{array}\right).
\end{equation}
\end{example}
The state $|\psi\vee\phi\rangle$ has elements in the union of sets $\psi$ and $\phi$. We often use $\ket{\psi}$ to mean the relation $\{\star\}\to H$ that relates the singleton set to all the elements in $\psi$.

\begin{axiom}
A \textbf{composite system} $H$ of $n$ subsystems is given by the Cartesian product so that $H = H_1\times...\times H_n$. \textbf{Composite states} are any subset of $H$.
\end{axiom}

\begin{defn}
For a relation $R:A\to B$ from set $A$ to $B$, the \textbf{converse relation} is denoted $R^{-1}:B\to A$ where for $x\in A$ and $y\in B$, $xRy$ if and only if $yR^{-1}x$.
\end{defn}

\noindent The converse replaces the $\dagger$-adjoint in quantum mechanics. This leads to:

\begin{defn}
A relation $R:H_1\to H_2$ is \textbf{unitary} if and only if $R\circ R^{-1} = \mbox{id}_{H_1}$ and $R^{-1}\circ R = \mbox{id}_{H_2}$, where $Q\circ R$ means $Q$ after $R$.
\end{defn}

\noindent This is the relational analog to the usual unitarity of linear maps in quantum mechanics and has an obvious interpretation:

\begin{theorem}
\label{cor:bijections}
Relations are unitary if and only if they are bijections.
\end{theorem}

\begin{axiom}
\textbf{Evolution} of systems is given by unitary relations.
\end{axiom}

\noindent This means that states of system $A$ can evolve to states of system $B$ if and only if there is a bijection between them. Note that this implies that there do not exist physical evolutions between systems of different cardinality. %This is analogous to the quantum setting where there do not exist unitary %maps between Hilbert spaces of differing dimensions.

\begin{defn}
For a state $\ket{\psi}:\{\star\}\to H$, denote its relational converse as $\bra{\psi}:H\to\{\star\}$ called its \textbf{effect}.
\end{defn}

\noindent A state preparation followed by an effect amounts to an experiment with a post-selected outcome. Effects are maps to $\{\star\}$ that return whether the outcome state $\ket{\psi}$ is possible.
 We give an example to illustrate:
\begin{example}
The preparation of the state $\ket{\phi}$ followed by a post-selected measurement of the effect $\bra{\psi}$ is given by the relation
\begin{align*}
\langle\psi|\phi\rangle:=\bra{\psi}\circ\ket{\phi}:\{\star\}\to H\to \{\star\}
\end{align*}
This is either the identity relation that we interpret to mean a measurement outcome of $\bra{\psi}$ is \emph{possible}, or it is the empty relation that we interpret to mean the measurement outcome $\bra{\psi}$ is \emph{impossible}. It is clear that the outcome $\bra{\psi}$ is possible if there exists some element of $H$ in both $\psi$ and $\phi$. Otherwise it is impossible.
In this sense our relational quantum computation is a deterministic model of quantum computation.
\end{example}

This interpretation allows us to define a generalized version of the Born rule\footnote{In quantum theory, the Born rule gives the probability of measuring the outcome state $\ket{\psi}$ following preparation in state $\ket{\phi}$ as $|\langle\psi|\phi\rangle|^2$ where $\langle\psi|\phi\rangle:\mathbb{C}\to\mathbb{C}$ is the inner product of the two state vectors \cite{nielsen2010quantum}. The QPT generalization is given in\ Definition~\ref{def:bornrule}.} to describe measurement in our model.
\begin{axiom}[Relational Born Rule]
\label{ax:relborn}
The possibility of measuring the state $\ket{\psi}$, having prepared state $\ket{\phi}$, is given by the image of:
\begin{align}
\langle\psi|\phi\rangle:\{\star\}\to\{\star\}
\end{align}
\end{axiom}

In the relational model, bases are characterized as particular generalizations of groups known as \textit{groupoids} \cite{cqm-notes,pavlovic2009quantum}.  Groupoids can be viewed as groups where multiplication is relaxed to be a partial function.

\begin{defn}
\label{def:basis}
For a system $H$, a \textbf{basis} $Z$ is a direct sum (disjoint union) of abelian groups $Z = G_0\oplus G_1\oplus...$ where $|Z| = |H|$.
Multiplication with respect to this list of groups will be written as $\bullet_Z$ and is defined in the following way. For elements $x,y\in Z$ such that $x\in G_i$ and $y\in G_j$ we have the partial function:
\begin{equation}
\label{eq:groupoidmult}
x\bullet_Zy = \begin{cases}
x +_{G_i} y & i=j \\
\mbox{undefined} & \mbox{otherwise}
\end{cases}
\end{equation}
This makes $Z$ an \textbf{abelian groupoid} with groupoid multiplication $\bullet_Z$.
\end{defn}
We will sometimes take a categorical perspective on groupoids. A groupoid $Z=\bigoplus^NG_i$ made up $N$ groups is a category whose set of objects is isomorphic to the set of groups $\{G_i\}$ and whose morphisms are elements of $Z$, e.g. $x\in Z$ such that $x\in G_1$ is a morphism $x:G_1\to G_1$.

At first guess, one might be motivated by the intuition that a basis for a system breaks it up into parts, and so a basis would be a partition of $H$.  This is not a bad start, however, bases have additional structure: namely that we can copy, delete and combine them at will.  This idea is used to motivate Definition \ref{def:basis} by abstracting bases to called classical structures (Definition \ref{def:classicalstruct}).

Recall that classical structures' properties, allowing the copying, deleting, and combining that accompany classical (as opposed to quantum) information, give them this name. We interpret them in the relational model of quantum computation through the following theorem:

\begin{lemma}[\cite{evans2009classifying,pavlovic2009quantum}]
\label{lem:sdfa-rel}
The classical structures in the category of sets and relations are exactly the abelian groupoids.\footnote{In \cite{heunen-relFrob} this connection is extended to the non-abelian case where it is shown that all relative Frobenius algebras are groupoids.}
\end{lemma}

\subsubsection*{Complementarity}
Complementary bases are important features of quantum theory. In the general setting, complementary bases are understood as mutually unbiased bases in a certain sense (Definition~\ref{def:complementarity}).  In relations Evans et al. gives a more direct characterization:\footnote{Theorem \ref{thm:compl} holds as long as we consider bases to be the same if their lists of groups are isomorphic.}
\begin{theorem}[\cite{evans2009classifying}]
\label{thm:compl}
Two bases $Z$ and $X$ are complementary if and only if they are of the following form. Basis $Z = \bigoplus^{|H|}G$ and basis $X = \bigoplus^{|G|}H$ given by copies of abelian groups $G$ and $H$ respectively.
\end{theorem}

This theorem follows from the requirement that the classical states of one basis must be isomorphic to the unbiased states of its complement. We will return to this idea in the Section \ref{sec:FT} when we address the quantum Fourier transform in relations. Classical and unbiased states of bases in the relational model are specified by Evans et al.~\cite{evans2009classifying} in the following corollaries that again correspond to abstract definitions from Chapter~\ref{chap:cqm}. An example on the six element system is illustrated with Figure \ref{complEx}.

\begin{figure}[tb]
\begin{center}
\includegraphics[height=10em,natwidth=1091,natheight=468,scale=1]{images/complexample.png}
\end{center}
\vspace{-14pt}
\caption[An example of two complementary bases on the system of six elements.]{An example of two complementary bases on the system of six elements. Here $Z=\mathbb{Z}_3\oplus\mathbb{Z}_3$ and $X = \mathbb{Z}_2\oplus\mathbb{Z}_2\oplus \mathbb{Z}_2$.  The two classical states of $Z$ are each three element subsets and are colored in pink and blue. The unbiased states of $X$ to which they correspond are colored to match.
}
\label{complEx}
\end{figure}

\begin{corollary}[\cite{evans2009classifying}]
The \textbf{classical states} of a basis $Z = \bigoplus^{N}G$ are the subsets corresponding to the groups $G_0, G_1,...$ where we forget the group structure. They will often be denoted $\ket{Z_i}$.
\end{corollary}

\begin{corollary}[\cite{evans2009classifying}]
The \textbf{unbiased states} for a basis $Z = \bigoplus^{N}G$ are subsets $U$ such that for a fixed $g\in G$, $\ket{U} = \bigoplus^{N}\{g\}$.
Thus there is exactly one element in each unbiased $U$ from each component $G_i$ of $Z$.
\end{corollary}

\begin{example}
Take $Z = \mathbb{Z}_2\oplus\mathbb{Z}_2=\{0_a,1_a,0_b,1_b\}$. The classical states of $Z$ are $\ket{G_a}=\ket{0_a\vee1_a}$ and $\ket{G_b}=\ket{0_b\vee1_b}$.  The unbiased states of $Z$ are $\ket{U_0}=\ket{0_a\vee0_b}$ and $\ket{U_1}=\ket{1_a\vee1_b}$.
\end{example}

It is easy to check that bases as specified by Theorem \ref{thm:compl} have the property that each classical state $\ket{Z_i}$ of the basis $Z$ corresponds to one unbiased state of $X$ and vice versa.
This allows us to call these bases mutually unbiased, i.e. complementary~\cite{evans2009classifying}.
\subsubsection*{Phases}

Phases are also defined in this relational setting.  In Hilbert space quantum mechanics a quantum phase for an n-dimensional system is given by the vector
\begin{align*}
\left(\begin{array}{c}
e^{i\phi_1} \\
\vdots \\
e^{i\phi_n}
\end{array}
\right).
\end{align*}
These quantum phases form an abelian group and can be applied as phase gates.
Their relational counterparts are described by the following lemma from \cite{cqm-notes}:
\begin{lemma}
For a basis $Z=\bigoplus_i^NG_i$, the \textbf{phase group} $B(Z)$ is given by $\prod_i^NG_i$.
\end{lemma}

\begin{example}
Consider the basis $\mathbb{Z}_2\oplus\mathbb{Z}_2$ for the four element system $\{00,01,10,11\}$.  Let $|\psi\rangle$ be the state $|00\vee10\rangle$. Application of the phase $11$ results in
\[ 11|00\vee10\rangle = |11\vee01\rangle . \]
\end{example}

We are also able to interpret GHZ states and density matrices in sets and relations.

\begin{defn}
For a basis $Z=\bigoplus_i^NG_i$, a \textbf{GHZ} state is given by
\[ GHZ_Z \; := \{\;(a,b,c)\;|\;\ \forall \;a,b,c \in Z,\;a\bullet_Zb\bullet_Zc = \mbox{id}_{G_i}\mbox{ for some } i\;\}.  \]
\end{defn}

\begin{defn}
For a state $|\psi\rangle$, the \textbf{density matrix} $|\psi\rangle\langle\psi|$ is given by the relation $xRy$ s.t. $x,y\in \psi$.
\end{defn}

\subsubsection*{The Model QCRel}

\begin{defn}
\label{def:qcrel}
Axioms 1-4, and subsequent definitions, specify the quantum-like process theory for \textbf{quantum computation in relations: QCRel}.
\end{defn}

By the QPT construction, this clearly makes QCRel a model of quantum computation in sets and unitary relations. It is worth noting that QCRel can be simply viewed as a local hidden variable theory. Consider the set $H$ to be the set of ontic states such that for $\phi\subseteq H$ the state $\ket{\phi}$ is non-deterministically in any of the ontic states in the subset $\phi$.  This perspective on \cat{Rel}, discussed further by Abramsky and Heunen~ \cite{abramsky2012operational}, shows that QCRel provides a non-deterministic local hidden variable model for computational aspects of quantum mechanics. This means that protocols exist for entanglement, teleportation, and, as we show in this section, some familiar blackbox algorithms.

\subsection{Unitary Oracles}

In order to model blackbox quantum algorithms in this setting, we must define the oracles themselves.
We do this by building up from an abstract definition of the controlled-not gate. Let the gray classical structure on a system $A$ be given by a basis $Z=\bigoplus^{|H|}G$ and the white classical structure be a basis $X=\bigoplus^{|G|}H$. The comonoid for the gray dot is then the relation $\tinycomult[graydot]:A\to A\times A$ that for $x,a,b\in H$ is given by
\[ \{(x,(a,b))~|~a\bullet_Zb=x\}. \]

\begin{defn}
\label{eq:generalizedcnotrel}
The abstract controlled-not is given by a composition of the comonoid for Z and the monoid for X:
\begin{equation}
\label{eq:cnot_rel}
\,\,
\begin{aligned}
\begin{tikzpicture}[yscale=0.6, xscale=0.6,string]
\node (b) [graydot] at (0,0) {};
\node (w) [whitedot] at (1,1) {};
\draw (-0.75,2) to [out=down, in=left] (b.center);
\draw (b.center) to [out=right, in=left] (w.center);
\draw (w.center) to (1,2);
\draw (b.center) to (0,-1);
\draw (w.center) to [out=right, in=up] (1.75,-1);
\end{tikzpicture}
\end{aligned}
\qquad \qquad\qquad
\begin{tabular}{l}
\mbox{CNOT:} $H\times H\to H\times H ::$ \\
$\{((x,y),(a,b\circ_Xy))~|~a\bullet_Zb=x\}.$ \\
\end{tabular} 
\end{equation}
\end{defn}
Example~\ref{ex:cnot} showed that in the traditional quantum setting of Hilbert spaces and linear maps, this exactly corresponds to the usual controlled-not. Recall that Theorem~\ref{thm:complementarityunitary} showed that two classical structures are complementary if and only if their corresponding controlled-not is unitary. This leads to the following corollary for complementary bases in QCRel:
\begin{corollary}
Two bases (Z and X) in QCRel are complementary, in the sense of Theorem~\ref{thm:compl}, if and only if the relation in \eqref{eq:cnot_rel} is a bijection.
\end{corollary}
\begin{proof}
The relevant relation can clearly be seen to be the composite in Definition~\ref{eq:generalizedcnotrel} as:
\begin{align}
\{((a,b,y),(a,b\circ_Xy))\} \circ \{((x,y),(a,b,y))~|~a\bullet_Zb=x\}.
\end{align}
Thus the abstract proof of\ Theorem \ref{thm:complementarityunitary} goes through unchanged.
\end{proof}

An oracle is then introduced as a controlled-not where we have embedded a particular kind of relation that abstractly must be a self-conjugate comonoid homomorphism. We construct such relations in the following lemmas.

\begin{defn}
Let $G$ and $H$ be groupoids with with groupoid multiplications $\bullet_G$ and $\bullet_H$ respectively. Let $\mbox{id}_{G}=\bigcup_{X\in\mbox{Ob}(G)}\mbox{id}_X$ and similarly define $\mbox{id}_{H}$. A \textbf{groupoid homomorphism relation} $R:G\to H$ obeys the following condition for $g_1,g_2\in G$:
%two conditions for $g_1,g_2\in G$ and $h_1,h_2\in H$:
\begin{align}
R(g_1\bullet_Gg_2) &= R(g_1)\bullet_HR(g_2) %\\
%R(\mbox{id}_G) &= \mbox{id}_H
\end{align}
\end{defn}
\noindent Note that while this in many ways resembles a groupoid homomorphism, it is actually a weakening of this notion, in that groupoid homomorphism relations are not required to be total functions and have no explicit requirement on their identity morphisms. From another perspective, this definition is the groupoid generalization of many-to-many group homomorphisms~\cite{wedderburn1941homomorphism}.

\begin{defn}
A \textbf{monoid homomorphism relation} is a monoid homomorphism in \cat{Rel}. Specifically, let $A$ and $B$ be sets equipped with monoids $(A,\tinymult[whitedot],\tinyunit[whitedot])$ and $(B,\tinymult[blackdot],\tinyunit[blackdot])$ respectively. A relation $r:A\to B$ is a monoid homomorphism when is obeys the following two conditions:
\begin{align}
\label{eq:monone}
r\circ\tinymult[whitedot] &= \tinymult[blackdot]\circ(r\times r) 
\end{align}
\begin{align}
\label{eq:monunit}
r\circ\tinyunit[whitedot] &= \tinyunit[blackdot]
\end{align}
A \textbf{comonoid homomorphism relation} is defined similarly, using duals of the above conditions.
\end{defn}

\begin{lemma}
\label{lem:mongrphom}
A groupoid homomorphism relation that is surjective on objects is a monoid homomorphism relation.
\end{lemma}
\begin{proof}
Throughout this proof we refer to a groupoid as a category where the elements of the groupoid are the morphisms.  From this perspective a group is a groupoid with a single object. Consider a groupoid homomorphism relation $R:G\to H$ on objects $X,A,B$ of $G$ and morphisms $f$ of $G$.
In order to show that $R$ is a monoid homomorphism relation we first show that it preserves the unit~\eqref{eq:monunit}. We have $R(\bigcup_{X\in\mbox{Ob}(G)} \mbox{id}_X) = \bigcup_{Y\in\mbox{Ob}(H)} \mbox{id}_Y$. Recall that for a set $A$,  $R(A)=\bigcup_{a\in A} R(a)$. It is that case that
\begin{align}
R(\bigcup\nolimits_{X\in\mbox{Ob}(G)} \mbox{id}_X) &= \bigcup\nolimits_{X\in\mbox{Ob}(G)}R(\mbox{id}_X) = \bigcup\nolimits_{X\in\mbox{Ob}(G)}\mbox{id}_{R(X)} \quad \mbox{def. of group hom. rel.} \\
&= \bigcup\nolimits_{R(X)\in\mbox{Ob}(G)}\mbox{id}_{R(X)} = \bigcup\nolimits_{{Y\in\mbox{Ob}(H)}}\mbox{id}_{Y} \qquad \mbox{surjective on objects}
\end{align}
where we have used the fact that $R$ is surjective on the groupoid objects, which implies that every object of $H$ is in the image of $R$ and that $|\mbox{Ob}(G)|\ge|\mbox{Ob}(H)|$.

The second monoid homomorphism condition~\eqref{eq:monone} is to preserve multiplication, i.e. that for subsets $K$ and $J$ of $G$ we have
\begin{align}
R(K+_GJ)=R(K)+_HR(J).
\end{align}

\noindent Here we recall that for two sets $A$ and $B$, $A+B=\{a + b | a \in A\mbox{ and } b \in B\}$. Thus,
\begin{align}
R(K+_GJ) &= R(\bigcup\nolimits_{k\in K,j\in J}k+_Gj) = \bigcup\nolimits_{k\in K,j\in J}R(k+_Gj) \\
&= \bigcup\nolimits_{k\in K,j\in J}R(k)+_HR(j) \qquad \mbox{def. of group hom. rel.}\\
&= R(K)+_HR(J).
\end{align}
This completes the proof.
\end{proof}

We then dualize the proof of Lemma \ref{lem:mongrphom} to conclude that:
\begin{lemma}
\label{lem:classicalRelation}
Let $F:H\to G$ be a functor such that $F^{\mbox{\tiny op}}$ is a groupoid homomorphism relation that is surjective on objects. $F$ is a comonoid homomorphism relation.
\end{lemma}
\noindent We call these comonoid homomorphism relations \textbf{classical relations}. These are relations that properly preserve the structure of the bases where classical data is embedded.  In the quantum case they take basis elements to basis elements. Some examples in QCRel are listed in Appendix \ref{app:clRel}. In order to define unitary oracles, we also need these relations to be self-conjugate (Definition~\ref{def:selfconj}). Luckily, this is always the case in relations:
\begin{lemma}
All classical relations $f:Z^A\to Z^B$ between groupoids $Z^A=\bigoplus^NG$ and $Z^B=\bigoplus^{N'}H$ are self-conjugate.
\end{lemma}
\begin{proof}
In QCRel, our dagger-Frobenius structures are groupoids and, if they are complementary to some other groupoid, then they are of the form $Z^A=\bigoplus^NG$ and $Z^B=\bigoplus^{N'}H$. We annotate the definition of self-conjugacy for some arbitrary element $(g,n)$, the element $g$ from the $n$-th group. Recall that $f^{\dagger}=f^{-1}$ in QCRel.
\begin{equation}
\begin{aligned}
\begin{tikzpicture}[yscale=0.9, xscale=1.3, thick]
\node [morphism] (f) at (2,1) {$f$};
\draw (0,-1) to [out=up, in=left, in looseness=0.9] (1,2) node [graydot] {} to (1,3.3) node [graydot] {};
\draw (1,2) to [out=right, in=up] (f.north);
\draw (f.south) to [out=down, in=left] (3,-0.7) node [blackdot] {} to [out=right, in=down, out looseness=0.9] (4,3);
\draw (3,-0.7) to (3,-2) node [blackdot] {};
\node [graydot] at (1,2) {};
\node at (0,-1.25) {\small $(g,n)$};
\node at (-0.25,1.5) {\small $(g,n)$};
\node at (0.9,2.65) {\small $\{(id_G,j) | 1 \leq j \leq N\}$};
\node at (2.5,1.7) {\small $(g^{-1},n)$};
\node at (2.1,-0.15) {\small $f^{-1}(g^{-1},n)$};
\node at (4.3,0) {\small $\left[f^{-1}(g^{-1},n)\right]^{-1}$};
\node at (2.95,-1.4) {\small $\{(id_H,k) | 1 \leq k \leq N'\}$};
\end{tikzpicture}
\end{aligned}
\quad=\quad
\begin{aligned}
\begin{tikzpicture}[yscale=1.2, xscale=1.3, thick]
\node (f) at (0,0) [morphism] {$f^{-1}$};
\draw (0,-1.5) to (f.south);
\draw (f.north) to (0,1.5);
\node at (0,-2) {\small $(g,n)$};
\node at (0,2) {\small $f^{-1}(g,n)$};
\end{tikzpicture}
\end{aligned}
\end{equation}
Thus, a relation $f$ is self-conjugate if and only if for all elements $(g,n)$ it is the case that $[f^{-1}(g^{-1},n)]^{-1}=f^{-1}(g,n)$. From Lemma \ref{lem:classicalRelation} the converse of the classical relation $f$ is a monoid homomorphism relation whose multiplication is the groupoid operation, so this condition will hold.
\end{proof}

Classical relations, as self-conjugate comonoid homomorphisms, lead to unitary oracles.

\begin{defn}[Relational Oracle]
\label{oracle}
Given a groupoid $Z^A:\blackmonoid{A}$, a pair of complementary groupoids $Z^B:\graymonoid{B}$ and $X^B:\whitemonoid{B}$, and a classical relation $R : \blackmonoid{A} \to \graymonoid{B}$, an \textbf{oracle} is defined to be the following endomorphism of~$A \times B$:
\begin{equation}
\label{eq:oraclerel}
\begin{aligned}
\begin{tikzpicture}[string,xscale=0.9, yscale=0.7]
    \node (dot) [blackdot] at (0,1) {};
    \node (f) [morphism] at (0.7,2) {$R$};
    \node (m) [whitedot] at (1.4,3) {};
\draw (0,0.25)
        node [below] {$A$}
    to (0,1)
    to [out=left, in=south] (-0.7,2)
    to (-0.7,3.75)
        node [above] {$A$};
\draw (0,1)
    to [out=right, in=south] (f.south);
\draw  (f.north)
    to [out=up, in=left] (1.4,3)
    to [out=right, in=up] +(0.7,-1)
    to (2.1,0.25)
        node [below] {$B$};;
\draw (m.center) to +(0,0.75) node [above] {$B$};
\end{tikzpicture}
\end{aligned}
\qquad \qquad
\begin{align*}
&\mbox{OracleRel(R)}:A\times B\to A\times B  ::\\
&\{((x,y),(a,c\circ_Xy))~|~ \\ &\hspace{50pt}\exists b\in A, s.t.~a\bullet_{Z^A}b=x\mbox{\emph{ and }} bRc\}. \\
\end{align*}
\end{equation}
\end{defn}
\begin{theorem}
\label{thm:familyofunitaries}
Oracles are unitary.
\end{theorem}
\begin{proof}
Proved in the abstract setting by Theorem~\ref{thm:complementarityunitary}, when $R$ is a self-conjugate comonoid homomorphism.  Though there are others, classical relations $R$ are necessary and sufficient in our cases as the algorithms that follow additionally require that the comonoids be part of classical structures.
\end{proof}

\begin{corollary}
OracleRel is a bijection.
\end{corollary}
\begin{proof}
This follows directly from Theorem \ref{thm:familyofunitaries} and Theoremm~\ref{cor:bijections}.
\end{proof}

\subsection{The Fourier transform in relations}
\label{sec:RelFT}

In Section~\ref{section_RelFT}, we saw that there are several perspectives on the Fourier transform in \cat{FRel}, only some of which are nontrivial. In this section we take the operational perspective on the generalized quantum Fourier transform whose definition is motivated through the relationship between classical and unbiased states of two bases.  For abelian groups $G$ and $H$, consider two groupoids $Z=\bigoplus^{|H|}G$ and $X=\bigoplus^{|G|}H$ to be complementary bases of the same system.

\begin{defn}
\label{def:FTRel}
The \textbf{quantum Fourier transform in relations} corresponds to preparing classical states of $Z$ and measuring them against classical states of $X$.
is an isomorphism from the classical states of $Z$ to the unbiased states of $X$, i.e.
\begin{align*}
\{G_h\}\mapsto \{h_g|\forall g\in G\}
\end{align*}
\end{defn}

\begin{example}
Take $G=\mathbb{Z}_2=\{0,1\}$, $H=\mathbb{Z}_1=\{\star\}$, $Z = G$ and $X=H\oplus H = \{ (\star,0),(\star,1) \}$. The computational basis is the family $\ket{H_g}_{g\in G}$ of classical states for $X$, i.e. $H_0 = \{(\star,0)\}$ and $H_1 = \{(\star,1)\}$. The quantum Fourier basis is a single classical state $G_\star = \{(\star,0), (\star,1)\}$ for $Z$. In this case all states can be prepared in the computational basis, but  measurement in the quantum Fourier basis is trivial.
\end{example}

\begin{example}
Take $G=\mathbb{Z}_2=\{0,1\}$, $H=\mathbb{Z}_2=\{a,b\}$, $Z = G \oplus G = \{ (0,0),(1,0),(0,1),(1,0)\}$ and $X= H \oplus H = \{ (a,a), (b,a), (a,b), (b,b) \}$. The computational basis is the family $\ket{H_g}_{g \in G}$ of classical states for $X$, i.e. $H_0 = \{(a,a),(b,a)\}$ and $H_1 = \{(a,b),(b,b)\}$. The quantum Fourier basis is the family $\ket{G_h}_{h\in H}$ of classical states for $Z$, i.e. $G_a = \{(0,0),(0,1)\}$ and $G_b = \{(1,0),(1,1)\}$.
\end{example}

See Section~\ref{sec:strcomplFT} and~\cite{gogioso2015fourier} to fully motivate this definition of the Fourier transform in QCRel and for its relationship to the usual Hadamard and Fourier transforms for Hilbert spaces and linear maps.

\subsection{The Deutsch-Jozsa algorithm in QCRel}
\label{sec:qcreldj}
The well known Deutsch-Jozsa algorithm is an early quantum algorithm that demonstrates a speedup over exact classical computation~\cite{deutsch1992rapid}. It takes as input a function promised to be either constant or balanced and returns which, deterministically using only a single oracle query. In this section, we model the algorithm's steps in QCRel just as it is implemented with Hilbert spaces and linear maps. This approach is somewhat dual to the usual one where different algorithms are compared on the same problem. Here we run the abstract protocol from Section~\ref{sec:abstractDJ} (implemented in a different model) with the same query complexity and compare the different problems that it solves.

To run this algorithm in QCRel we use two systems.  System $A$ has cardinality $n$ and system $B$ has cardinality $\ge 2$. Take $Z^A=\bigoplus^{|H^{A}|}G^A$ and $X^A=\bigoplus^{|G^{A}|}H^A$ to be complementary bases of $A$. Take $Z^B=\bigoplus^{|H^{B}|}G^B$ and $X^B=\bigoplus^{|G^{B}|}H^B$ to be complementary bases of $B$, such that $X^B$ has at least two classical states. In analogy with the usual specification, the algorithm proceeds with the following steps.
\begin{enumerate}
\item Prepare $A$ in the zero state $|Z^{A}_0\rangle$. Prepare $B$ in the state given by the second classical state of $Z^B$, i.e. $|Z^B_1\rangle$.

\item Apply the Fourier transform, as given by Definition \ref{def:FTRel}, to each system, resulting in states $\ket{X_0^A}$ and $\ket{X_1^B}$ respectively.

\item Apply an oracle \eqref{eq:oraclerel}, built from a classical relation $f:Z^A\to Z^B$.

\item Again apply the Fourier transform to system $A$ and then measure it in the $Z$ basis.
\end{enumerate}

\noindent This sequence of steps is an instance in sets and relations of the abstract Deutsch-Jozsa algorithm from \cite{vicary-tqa}, which translates to the following relation, where we have already applied the Fourier map  to the input and output. See~\eqref{eq:postFT}.

\begin{equation}
\label{eq:reldj}
\begin{aligned}
\begin{tikzpicture}[string, yscale=1, xscale=1]
    \node (dot) [blackdot] at (0,1) {};
    \node (f) [morphism] at (0.7,2) {$f$};
    \node (m) [whitedot] at (1.4,3) {};
\draw (0,0.25)
        node [blackdot] {}
    to (0,1)
    to [out=left, in=south] (-0.7,2)
    to (-0.7,3.75)
        node [blackdot] {};
\draw (0,1)
    to [out=right, in=south] (f.south);
\draw  (f.north)
    to [out=up, in=left] (1.4,3)
    to [out=right, in=up] +(0.7,-1)
    to (2.1,0.25)
        node [graydot] {};
\node at (2.15,0.25) [anchor=west] {$|H^B_1\rangle$};
\node at (0.05,0.25) [anchor=west] {$|H^A_0\rangle$};
\node at (-0.65,3.75) [anchor=west] {$\langle H^A_0|$};
\draw (m.center) to +(0,0.75)
        node [above] {};
\draw [thin, dashed] (-1.25,0.7) to (7.5,0.7);
\draw [thin, dashed] (-1.25,3.3) to (7.5,3.3);
\node at (3.5,0) [anchor=west] {\small Prepare initial states and apply Fourier};
\node at (3.5,2) [anchor=west] {\small Apply a unitary map};
\node at (3.5,4) [anchor=west] {\small Apply Fourier and measure the first system};
\end{tikzpicture}
\end{aligned}
\end{equation}
that is explicitly written as:
\begin{align*}
\mbox{DJAlg}(f)&::\{\star\}\times \{\star\} \to \{\star\}\times B \\
&=
\bra{H_0^A}\times{\mbox{id}_B}\circ\mbox{OracleRel}(f)\circ\ket{H^A_0}\times\ket{H^B_1}
\\ &=
\{((\star,\star),(\star,z))\;|\; 
  z\in H_1^B \mbox{ and } \exists y\in H_0^A, \mbox{ s.t. }yfz\},
\end{align*}
Note the correspondence between~\eqref{eq:reldj} and~\eqref{eq:postFT}. Thus by the derivation in Section~\ref{sec:abstractDJ} we have:

\begin{theorem}
\label{def:bc}
In any dagger compact category with complementary bases, the algorithm in Equation \ref{eq:reldj} will, with a single oracle query, distinguish \textbf{constant} and \textbf{balanced} classical relations $f:Z^A\to Z^B$ according to the following abstract definitions. Here $\ket{x}$ is a classical state of $Z^A$ and the zero scalar $0$ is, in \cat{Rel}, the empty relation:
\begin{equation}
\label{eq:bc}
\mbox{\\ constant}:\quad
\begin{aligned}
\begin{tikzpicture}[scale=1]
\node (f) [morphism] at (0,0) {$f$};
\draw (0,-1) to (f.south);
\draw (f.north) to (0,1);
\end{tikzpicture}
\end{aligned}
\;=\;
\begin{aligned}
\begin{tikzpicture}[scale=1]
\draw (0,-1) to (0,-.4)
    node [blackdot] {};
\draw (0,0.5) node [state] {$x$} to (0,1);
\end{tikzpicture}
\end{aligned}
=\ket{x}\circ\tinycounit[blackdot]
\qquad\qquad \mbox{balanced:\quad}
\begin{aligned}
\begin{tikzpicture}[string, scale=1]
\node [morphism] (f) at (0,0) {$f$};
\draw (0,-0.85) node [blackdot] {} to (f.south);
\draw (f.north) to (0,0.75) node [graydot, hflip] {};
\node at (0.05,0.75) [anchor=west] {$2$};
\end{tikzpicture}
\end{aligned}
\quad=\quad
0, \vspace{-5pt}
\end{equation}
where 
\begin{tikzpicture}[string, yscale=1]
\draw (f.north) to (0,0.75) node [graydot, hflip] {};
\node at (0.05,0.75) [anchor=west] {$2$};
\end{tikzpicture} is the dagger adjoint of the second classical state of $X^B$.
\end{theorem}
That these definitions coincide with the usual ones for constant and balanced functions is shown in Section~\ref{sec:abstractDJ}. In fact, it is easy to check that any constant relation will be a classical relation. In QCRel, the effect 
\begin{tikzpicture}[string,scale=0.75]
\draw (f.north) to (0,0.75) node [blackdot, hflip] {};
%\node at (0.05,0.75) [anchor=west] {$2$};
\end{tikzpicture} is $\langle H^A_1|$, which acts as a measurement of system $A$ after applying the oracle.
We illustrate the details of the QCRel model of this algorithm by example and then with general definitions.

\begin{example}
\label{ex:djrel}
Take $A=\{0,1,2,3\}$ and $B=\{a,b,c,d\}$ to be four element systems. We define complementary bases on these systems as the following:
\begin{align*}
\begin{tabular}{|c|c|}\hline
System $A$ & System $B$ \\\hline
$Z^A = \mathbb{Z}_2\oplus\mathbb{Z}_2 \mbox{~~s.t.}$ & $Z^B = \mathbb{Z}_2\oplus\mathbb{Z}_2\mbox{~~s.t.}$ \\
$Z_0^A=\{0,1\},Z_1^A=\{2,3\}$ & $Z_0^B=\{a,b\},Z_1^B=\{c,d\}$ \\ \hline
$X^A = \mathbb{Z}_2\oplus\mathbb{Z}_2 \mbox{~~s.t.}$ & $X^B = \mathbb{Z}_2\oplus\mathbb{Z}_2\mbox{~~s.t.}$ \\
$X_0^A=\{0,2\},X_1^A=\{1,3\}$ & $X_0^B=\{a,c\},X_1^B=\{b,d\}$ \\ \hline
\end{tabular}
\end{align*}


From Equation \ref{eq:bc}, we then define constant and balanced classical relations using the following dictionary:
\begin{align}
\begin{aligned}
\begin{tikzpicture}[string]
\draw (0,0.2) to (0,0.75) node [blackdot, hflip] {};
\node at (0.05,0.75) [anchor=west] {};
\end{tikzpicture}
\end{aligned}
&\quad= \{(0,\star),(2, \star)\},  \quad \mbox{the classical state adjoint } \bra{X_0^A} \\
\begin{aligned}
\begin{tikzpicture}[string]
\node (x) [state, xscale=0.75] at (0,0) {$x$};
\draw (0,0) to (0,0.5) {};
\end{tikzpicture}
\end{aligned}
&\quad= \{(\star,a),(\star,b)\}\mbox{ OR }\{(\star,c),(\star,d)\},  \quad \mbox{a classical state of }Z^B \\
\begin{aligned}
\begin{tikzpicture}[string]
\draw (0,0.2) to (0,0.75) node [graydot, hflip] {};
\node at (0.05,0.75) [anchor=west] {$2$};
\end{tikzpicture}
\end{aligned}
&\quad=\{(b,\star),(d, \star)\},  \quad \mbox{ the classical state adjoint } \ket{X^B_1} \\
\begin{aligned}
\begin{tikzpicture}[string]
\node (x) [blackdot] at (0,0) {};
\draw (0,0) to (0,0.5) {};
\end{tikzpicture}
\end{aligned}
&\quad= \{(\star,0),(\star,2)\},  \quad \mbox{the classical state } \ket{X^A_0}
\end{align}

Thus there are two constant classical relations\footnote{A list of more example classical relations is given in Appendix \ref{app:clRel}.} $f:Z^A\to Z^B$, one for each classical state of $Z^B$. They are:
\begin{align*}
\{ (0,a),(0,b) ,(2,a),(2,b) \} \quad \mbox{and} \quad
\{ (0,c),(0,d), (2,c),(2,d) \}.
\end{align*}
By Definition \ref{def:bc}, balanced classical relations are those which do not relate $0$ or $2$ to either $b$ or $d$. There are four balanced classical relations for this example:
\begin{align*}
\{(0,c),(2,c),(1,d),(3,d)\} &\qquad \{(0,a),(1,b),(2,c),(3,d)\} \\
\{(2,a),(3,b),(0,c),(1,d)\} &\qquad \{(0,a),(2,a),(1,b),(3,b)\} 
\end{align*}
For a classical relation promised to be in one of these two classes, we can distinguish which with a single oracle query.
\end{example}

We generalize these definitions of constant and balanced classical relations to the following:
\begin{defn}
\label{def:const}
Let $Z^A=\oplus^NG_i$. A \textbf{constant relation} $f:Z^{A}\to Z^{B}$ relates all id$_{G_i}$ to a single classical state of $Z^B$.
\end{defn}

\begin{defn}
\label{def:balanced}
A relation $f:Z^{A}\to Z^{B}$ is \textbf{balanced} when no element in $X^{A}_0$ is related to an element in $X^{B}_1$.
\end{defn}

\begin{theorem}
\label{thm:dj_speedup}
The Deutsch-Jozsa algorithm defined above distinguishes constant relations from balanced relations in a single oracle query.
\end{theorem}
\begin{proof}
This follows immediately from Vicary's abstract proof of the Deutsch-Jozsa algorithm from Section~\ref{sec:abstractDJ}.
\end{proof}

\begin{remark}
It is important to note that the constant or balanced classes of classical relations in Example~\ref{ex:djrel} can, as non-deterministic classical relations, be distinguished by a single query with input $\ket{1},\ket{3},$ or $\ket{1\vee 3}$.  This observation might lead us to conclude that constant and balanced classical relations $f:Z^A\to Z^B$ can be distinguished by a single query of $f$ on any classical state of $X^A$ except the first one. In fact this is the case, as we now show.
\end{remark}

\begin{lemma}
\label{lem:balpreimage}
There does not exist a balanced classical $f:Z^A\to Z^B$ relation whose pre-image is given only by elements of $X^A_{0}$.
\end{lemma}
\begin{proof}
If the pre-image of $f$ is given only by elements of $X_{0}^A$, then the image of $f^{-1}$ must be the this same set $X_0^A$. However, balanced classical relations by definition have $\bra{X^A_0}\circ f^{-1}\circ  \ket{X_1^B} = 0.$ Thus no element of $X_1^B$ can be in the pre-image of $f^{-1}$ (in the image of $f$). Let $\delta_{Z^A}:A\to A\tensor A$ be the relational converse of the groupoid multiplication for $Z^A$ (and likewise for $\delta_{Z^B}$). Write $-X_1^B=\{x^{-1}~|~x\in X_1^B\}$. Then if no element of $X_1^B$ is in the image of $f$, we have:
\begin{align}
0 &= \bra{X_1^B}\tensor\bra{-X_1^B}\circ (f\tensor f)\circ \delta_{Z^A}\\
0 &= \bra{X_1^B}\tensor\bra{-X_1^B}\circ \delta_{Z^B}\circ f \qquad\qquad \mbox{by the dual of~\eqref{eq:monone}} \\
0 &= \bra{X_0^B}\circ f,
\end{align}
As classical relations are comonoid homomorphisms they must obey the duals of~\eqref{eq:monone} and~\eqref{eq:monunit}, but this last equation contradicts the dual of~\eqref{eq:monone}. Thus $f$ cannot both be a balanced classical relation and have a pre-image of only $X_0^A$.
\end{proof}

This allows us to show that we will always be able to construct a simple query of constant and balanced classical relations in order to distinguish them.

\begin{theorem}
\label{thm:trivRelDJ}
Constant and balanced classical relations can be distinguished in a single query whose input state has non-zero intersection with any classical state other than $\ket{Z^A_0}$.
\end{theorem}
\begin{proof}
 Let $\ket{Z_i^B}$ be a classical state of $Z^B$ and $\tinycounit[blackdot]$ be the classical co-state $\bra{Z^A_0}$. Any constant classical relation has the form $f:\ket{Z_i^B}\circ\tinycounit[blackdot]$, and so the pre-image of $f$ is only the elements in the first classical state of $A$. Thus, a query of a constant classical relation with input from any other classical state will return the empty set.  Further, Lemma~\ref{lem:balpreimage} shows that it is not possible to construct balanced relations which will have the same behavior. Thus a query with any element not in $\tinycounit[blackdot]$ will suffice to identify the class of the classical relation. 
\end{proof}

Theorem~\ref{thm:trivRelDJ} shows that the model of the Deutsch-Jozsa algorithm does not result in a classical algorithm for a non-trivial problem.  While this would have been a nice side effect of our analysis, it is not the main goal. The more important takeaway is that the operation of the quantum algorithm can be accurately modeled in QCRel and that it does optimally solve a problem in that context. We will discuss this further after two more examples.

\subsection{Single-shot Grover's Algorithm}
\label{sec:qcrelgrovers}
The usual Grover's algorithm~\cite{grover1996fast} takes as input a set $S$ and an indicator function $f:S\to\{0,1\}$ and outputs an element $s\in S$ such that $f(s)=1$. Though the algorithm is usually probabilistic and runs a repeated series of ``Grover steps", here we consider the deterministic version that runs with a single step. In this section we will consider Vicary's generalization of the single-shot Grover algorithm where the codomain of the indicator function is allowed to be an arbitrary group~\cite{vicary-tqa}. Our setup requires the set $S$, as one system, as well as another system $B$. We define the basis $Z^{S}=\bigoplus^{|H^S|}G^S$ and $X^S=\bigoplus^{|G^S|}H^S$ on the $S$ system.  System $B$ has complementary bases $Z^B=\bigoplus^{|H^B|}G^B$ and $X^B=\bigoplus^{|G^B|}H^B$. Let $\ket{X_0^B}$ be the first classical state of $X^B$, e.g. is $X^B=\mathbb{Z}_2\oplus\mathbb{Z}_2$ then $\ket{X_0^B}=\{(\star,1),(\star,3)\}$, where $1$ and $3$ are the non-identity elements of that factors of $X^B$. Let $\bra{X_{\rho}^B}$ be the converse of a classical state of $X^S$. Recall that $\ket{Z^S_0}=\{(\star,g)\,|\,g\in G^S\mbox{ is the first factor group of } Z^S\}$ is a classical point of $Z^S$, and that, by the complementary relationship of classical and unbiased points (Section~\ref{sec:RelFT}), $\ket{X^S_0}\isom\{(\star,\idm{G^S_i})\,|\,G^S_i\mbox{ is a factor group of } Z^S\}$.

In QCRel, the algorithm proceeds by the following steps:
\begin{enumerate}
\item Prepare system $S$ in the state $\ket{Z^S_0}$ and system $B$ in the state $\ket{X_0^B}$.

\item Apply the Fourier transform to system $S$, resulting in state $\ket{X^{S}_0}$.

\item Apply the oracle for a classical indicator relation $f:Z^S\to Z^B$.

\item Apply a diffusion relation $D:S\to S$ (defined below) to system $S$.

\item Measure system $S$ in the $X^S$ basis.

\end{enumerate}

Vicary's~\cite{vicary-tqa} presentation for this procedure is:
\begin{equation}
\label{eq:grovertopological}
\begin{aligned}
\begin{tikzpicture}[thick, xscale=1, yscale=0.5]
\begin{pgfonlayer}{foreground}
    \node (f) [smallbox, anchor=south, thick] at (0.7,2) {$f$};
\end{pgfonlayer}
    \node (dot) [blackdot] at (0,1) {};
    \node (m) [whitedot] at ([xshift=0.7cm, yshift=1cm] f.north) {};
\draw (0,-0.25)
        node [blackdot] (bdot) {}
    to (0,1)
    to [out=\nwangle, in=south] (-0.7,2)
    to ([yshift=1.4cm] m.center -| -0.7,1)
        node (rho) [state,hflip,yscale=1.5, xscale=1.1] {};
\node at (-0.7,5.9) {$\bra{\rho}$};
\draw (0,1)
    to [out=\neangle, in=south] (f.south)
    to (f.north)
    to [out=up, in=\swangle] +(0.7,1)
    to [out=\seangle, in=up] +(0.7,-1)
    to (2.1,-0.25)
        node [state,yscale=1.5, xscale=1.1] (sigmadag) {};
\node at (2.1,-1) {$\ket{\sigma}$};        
\draw (m.center) to (1.4,5.75)
        node [above] {};
\node [smallbox] at (-0.7,3.5) {$D$};
\node at (3.5,-0.25) [anchor=west] {Preparation};
\draw [thin, dashed] (-2,0.6) to (7,0.6);
\node at (3.5,2.25) [anchor=west] {Dynamics};
\draw [thin, dashed] (-2,4.5) to (7,4.5);
\node at (3.5,5) [anchor=west] {Measurement};
\end{tikzpicture}
\end{aligned}
\end{equation}

\noindent where numerical scalars have been dropped relative to that reference as there is only one non-zero scalar in QCRel.\footnote{Recall that scalars in a monoidal category with identity object $I$ are maps $s:I\to I$. Thus in \cat{Rel} $I=\{\star\}$, so the only scalars are the empty relation and the identity relation on the singleton set.} Compare~\eqref{eq:grovertopological} to Figure~\ref{fig:algtriplet}. Recall that $\tinyunit[blackdot]:\{\star\}\to S$ relates the singleton to the elements of $H_0$ and that $\tinycounit[blackdot]$ is its relational converse. We will use the map $\tinyunit[blackdot]\circ\tinycounit[blackdot]:S\to S$ in the following definition. Here there is a special relation $D:S\to S$ called the diffusion operator:
\begin{equation}
\label{eq:difftopological}
\begin{aligned}
\begin{tikzpicture}[thick, scale=1]
\draw (0,0) node [below] {$S$} to node [smallbox] {$D$} (0,2) node [above] {$S$};
\end{tikzpicture}
\end{aligned}
\hspace{5pt}\;=\;\hspace{5pt}
\hspace{-5pt}
\begin{aligned}
\begin{tikzpicture}[thick, scale=1]
\draw (0,0) node [below] {$S$} to (0,2) node [above] {$S$};
\end{tikzpicture}
\end{aligned}
\;-\;
\begin{aligned}
\begin{tikzpicture}[thick, scale=1]
\draw (0,0) node [below] {$S$} to (0,0.7) node [blackdot] {};
\draw (0,2) node [above] {$S$} to (0,1.3) node [blackdot] {};
\end{tikzpicture}
\end{aligned}
\qquad\qquad \qquad D := \{(x,x)\,|\,x\in S\}\bigtriangleup (H_0\times H_0)
\end{equation}
where the subtraction of two relations is given by the symmetric difference of their images. Explicitly then, the relational model for Grover's algorithm is:
\begin{align*}
\mbox{Grover}(f)&:\{\bullet\}\times \{\bullet\} \to \{\bullet\}\times B \\
&=
\bra{X_{\rho}^S}\times{\mbox{id}_B}\circ D\times{\mbox{id}_B}\circ\mbox{OracleRel}(f)\circ\ket{X^S_0}\times\ket{\sigma}
\\ &= \{((\bullet,\bullet),(\bullet,c\circ_{X}x))\;|\; \\
&\hspace{40pt}
 x\in X_{0}^B,y\in X_\rho^S, \mbox{id}_{G_n},b,z\in S \mbox{ s.t. } z\bullet_{Z^S} b=\mbox{id}_{G_{n}} \mbox{ and } bfc,zDy\}
\end{align*}

\begin{theorem}
\label{thm:topgrovers}
Equation \ref{eq:grovertopological} is zero only for classical states of $X^S$ denoted $\ket{X_{\rho}^S}$ that satisfy the following equation:
\begin{equation}
\label{eq:zerocondition}
\bra{X_0^B} \circ f \circ \ket{X_{\rho}^S} = \bra{X_0^B} \circ f \circ \ket{X_0^S}
\end{equation}
\end{theorem}
\begin{proof}
Proven in \cite{vicary-tqa}. See Section 3.2, Equation (34).
\end{proof}

Here $\ket{X_0^B}$ can be generalized to any fixed classical state $\ket{X_{\sigma}^B}$. This allows a generalization of the single-shot Grover's algorithm where the cardinality of system $B$ is increased \cite{vicary-tqa}.
Consequently, the LHS of Equation \ref{eq:zerocondition} tests if any element in the classical state $\ket{X_{\rho}^S}$ is related to any of the elements in $\ket{X_{\sigma}^B}$. The RHS tests if any of the elements of $X_0^S$ are related to $\ket{X_{\sigma}^B}$.

\begin{proposition}
The QCRel single-shot Grover algorithm only returns states $\ket{X_{\rho}^S}$ such that for all $h \in X^S_0$, $s\in X_{\rho}^S$ and $x\in X_{\sigma}^B$
\begin{align*}
h f x \quad = \quad \neg(s f x) .
\end{align*}
In other words, the only elements that can be possibilistically measured under the QCRel Born rule (Axiom~\ref{ax:relborn}) are elements of $S$ that have the opposite mapping to $X_{\sigma}^B$, under the relation $f$, than elements of $X^{S}_0$.
\end{proposition}
\begin{proof}
By Theorem \ref{thm:topgrovers} and definitions.
\end{proof}

\begin{example}
Let $S=\{0,1,2,3\}$ and choose $Z^S=\mathbb{Z}_2\oplus\mathbb{Z}_2$ and $X^S=\mathbb{Z}_2\oplus\mathbb{Z}_2$ as $G$ (black) and $H$ (white) bases respectively, so that $Z^{S}_0=\ket{0\vee 1}$ and $X^S_0 = \ket{0\vee 2}$. Let $B$ be the same four element system with the bases $Z^B=\mathbb{Z}_2\oplus\mathbb{Z}_2$ and $X^B=\mathbb{Z}_2\oplus\mathbb{Z}_2$ and choose $\ket{X_{\sigma}^B}=\ket{1\vee 3}$. The diffusion operator is then given by
\begin{align*}
D &:= \{(0,0),(1,1),(2,2),(3,3)\}-\{(0,0),(0,2),(2,0),(2,2)\}
\\&=\{(1,1),(3,3),(0,2),(2,0)\}.
\end{align*}

In this case, $D$ happens to be a bijection, it is a unitary relation and thus a possible evolution in QCRel.\footnote{This will not be the case whenever $S$ has more than two factor groups. Unitarity is a stringent condition on processes in QCRel.} Let $f$ be the classical relation\footnote{See Appendix \ref{app:clRel} for a list of classical relations $\mathbb{Z}_2\oplus\mathbb{Z}_2\to\mathbb{Z}_2\oplus\mathbb{Z}_2$.} $\{(0,2),(2,2),(1,3),(3,3)\}$, where elements of $X^S_0$ are not related to elements of $X_{\sigma}^B$. Thus the above algorithm will only return classical states of $X^{S}$ that \textit{are} related, under $f$, to $\ket{X_{\sigma}^B}$.  The only possible outcome state is $\ket{1\vee 3}$.
\end{example}

\begin{example}
\label{ex:relgrov2}
This is the same as the above example, but take $f$ to be the classical relation $\{(0,0),(2,0),(0,1),(2,1)\}$. As an element of $X^S_0$ is related to $\ket{X_{\sigma}^B}$, the algorithm will return classical states of $X^S$ which are \emph{not} mapped to $\ket{X_{\sigma}^B}$, i.e. the state $\ket{1\vee3}$.
\end{example}

If we loosen the QCRel model slightly, and do not require $f$ to be a classical relation, then it is easy to see that this algorithm solves a non-trivial classical search problem. Consider an $f$ that maps all classical states of $X^S$ to $\ket{X_{\sigma}^B}$  except exactly one other \emph{marked} classical state $X^S_i$, where $i\neq 0$. As in Example~\ref{ex:relgrov2}, we know that the QCRel Grover's algorithm will output only $X_i^S$ with a single query of $f$. We can easily imagine that there are a large number of classical states of $X^S$ that might be marked and, further, that the image of the marked classical state under $f$  is indistinguishable from that of any other classical state (other than not being related to $\ket{X_{\sigma}^B}$). A deterministic classical approach to this problem would certainly require many queries of $f$, and it is not immediate that there is an obvious non-deterministic solution with a single query; though the QCRel Grover's algorithm we describe here does achieve exactly that.

\subsection{The Groupoid homomorphism promise algorithm}

This section models the group homomorphism algorithm from Section~\ref{sec:grouphomid} in QCRel.  The quantum version of the algorithm takes as input a blackbox function $f:G\to A$ promised to be one of the homomorphisms between group $G$ and abelian group $A$.  It then outputs the identity of the homomorphism. In that section the full identification algorithm is built up by multiple calls to an instance of the problem for cyclic groups.\footnote{Making use of the structure theorem for abelian groups to complete the general case.} It is this cyclic group subroutine that we consider here. In the relational setting we will move from groups to groupoids. Let groupoid $H$ be complementary to groupoid $G$ and groupoid $B$ be complementary to groupoid $A$. The QCRel GroupHomID algorithm then takes as input a groupoid isomorphism $f:G\to A$.   Let $\ket{\rho}$ be a classical state of $H$, and $\ket{\sigma}$ be a classical state of $B$. 

The algorithm has the following abstract specification~\cite{zeng2014abstract}:
\begin{align}
\label{eq:groupdIDAlg}
\begin{aligned}
\begin{tikzpicture}[string, scale=1]
    \node (dot) [blackdot] at (0,1) {};
    \node (f) [morphism] at (0.7,2) {$f$};
    \node (m) [whitedot] at (1.4,3) {};
    \node (topsig) [copoint, scale=1.3,anchor=south] at (-0.7,3.6) {$\ket{\rho}$};
\draw (0,0)
        node [blackdot] {}
    to (0,1)
    to [out=left, in=south] (-0.7,2)
    to (topsig.south);
\draw (0,1)
    to [out=right, in=south] (f.south);
\draw  (f.north)
    to [out=up, in=left] (1.4,3)
    to [out=right, in=up] +(0.7,-1)
    to (2.1,0.4)
        node [point, scale=1.3, anchor=north] {$\ket{\sigma}$};
\draw (m.center) to (1.4,4.4)
        node [above] {};
\draw [thin, dashed] (-1.25,0.7) to (7.5,0.7);
\draw [thin, dashed] (-1.25,3.3) to (7.5,3.3);
\node at (3,0) [anchor=west] {Prepare initial states};
\node at (3,2) [anchor=west] {Apply a unitary map};
\node at (3,4) [anchor=west] {Measure the left system};
\end{tikzpicture}
\end{aligned}
\end{align}
Let the factor groups of a groupoid $G$ be denoted $G_n$. This gives the following relational model for the algorithm:
\begin{align*}
\mbox{GroupHomID}(f)&:\{\bullet\}\times \{\bullet\} \to \{\bullet\}\times B \\
&=
\bra{\rho}\times{\mbox{id}_B}\circ \mbox{OracleRel}(f)\circ\ket{H_0}\times\ket{\sigma}
\\ &= \{((\bullet,\bullet),(\bullet,c\circ_{X}x))\;|\; \\
&\hspace{40pt}
x\in\sigma,y\in\rho, \mbox{id}_{G_n},b\in A \mbox{ s.t. } y\bullet_G b=\mbox{id}_{G_{n}} \mbox{ and } bfc\}
\end{align*}

\begin{theorem}
The algorithm defined by~\eqref{eq:groupdIDAlg} has output state $\ket{\rho}$ only when for some $x\in \rho$ and some $y\in \sigma$ we have $(y,x)\in f$.
\end{theorem}
\begin{proof}
The verification in Section~\ref{sec:grouphomid} simplifies the algorithm in Equation \ref{eq:groupdIDAlg} to:
\begin{equation}
\begin{aligned}
\begin{tikzpicture}[string, scale=0.9]
\node (r) [state] at (0,2) {$\sigma$};
\node (s) [state, hflip] at (0,3.5) {$\rho$};
\node (f) [morphism] at (0,2.75) {$f^{-1}$};
\node (r2) at (1.5,3) [state] {$\sigma$};
\draw (s.south) to (f.north);
\draw (f.south) to (r.north);
\draw (r2.north) to +(0,0.5);
\end{tikzpicture}
\end{aligned}
\qquad= \quad \{(\bullet,(\bullet,x))\;|\;x f^{-1} y\;\mbox{for some } y\in\rho\},
\end{equation}
where we see that post-selection on the left hand system implies the theorem's condition via the QCRel Born rule (Axiom~\ref{ax:relborn}).
\end{proof}

\begin{theorem}
If $f$ is a groupoid isomorphism then the algorithm in Equation \ref{eq:groupdIDAlg} returns all states.
\end{theorem}
\begin{proof}
Groupoid isomorphisms relate every element of the domain to some element in the codomain and relate every element of the codomain to some element of the domain.
\end{proof}

\noindent Still, we can imagine running the algorithm from \eqref{eq:groupdIDAlg} where any classical relation $f$ is allowed as input to obtain non-trivial outcomes. The investigation of the usefulness of this algorithm is part of future work.

\section{Conclusion}
In this chapter we have investigated the structure of quantum algorithms using the QPT perspective. We have contributed the following new results:
\begin{enumerate}
\item A definition of the Fourier transform in general QPTs along with abstract proofs of the Fourier Inversion Theorem, Pontryagin Duality, and the Convolution Theorem.
\item A definition of the Fourier Transforms and an operational quantum Fourier transform in general oPTs.
\item We use complementary observables to construct a unitary oracle in a general QPT and provide an abstract proof of its unitarity.  We show an equivalence between the complementarity of those observables and the unitarity of this oracle.
\item We pose a new problem, the GROUPHOMID problem, and give a quantum algorithm for its solution with favorable query complexity over classical algorithms.
\item We provide models for the operation of quantum algorithms in non-deterministic classical computation by explicitly constructing the Deutsch-Jozsa algorithm, the single-shot Grover's algorithm, and the GROUPHOMID algorithm in the QPT QCRel. Along the way we introduce an operational notion of a QPT Fourier transform in \cat{FRel} and characterize self-conjugate comonoid homomorphisms and unitary oracles in this category.
\end{enumerate}

Models of quantum algorithms in other QPTs (such as QCRel), perform two functions. Firstly, they help us further understand the relationship between different kinds of computation.  Our main question is: 
\begin{align*}
\mbox{\emph{How are different models of computation related to each other?}}
\end{align*}  Typically, computer scientists address this question by keeping computational problems fixed and writing different algorithms for the same problem that take advantage of the computational model. This view is the basis of the field of computational complexity and has given many insights into the differences between computational models. The approach in this thesis aims to extend this view. In a sense, the QPT framework allows us to think about running the same algorithms on different QPTs as we would think about running them on different kinds of hardware. We ``compile" algorithms into different QPTs and analyzes the results to address our main questions. It is an algorithm-centric vs. problems-centric approach to computation. 

As compared to the foundational interest of the first function, the second function of this investigation is more practical.  Mapping algorithms between computational models allows us to generate new problems and algorithms. Some of these will be trivial (as in the QCRel Deutsch-Jozsa algorithm of Section~\ref{sec:qcreldj}) and some will not be (as in QCRel Grover's of Section~\ref{sec:qcrelgrovers}). An important thread of future work is to understand the conditions that allow for one case and not that other.

In terms of quantum algorithms specifically, the successes of this approach open up new avenues to study other blackbox quantum algorithms at this level of abstraction. We discuss more details of the outlook for future work in Chapter~\ref{chap:outlook}.