strongcomplft.tex

\section{The Fourier transform in QPTs}
\label{sec:strcomplFT}

Ongoing work in quantum algorithms emphasizes the need for a structural understanding of quantum speedups~\cite{aaronson2014need}. In this section we focus on the quantum Fourier transform and the structure in quantum theory that enables it. We elucidate a general connection in any QPT between the Fourier transform and strongly complementary observables, i.e. Hopf algebras in dagger symmetric monoidal categories. We emphasize that, while they happen to coincide for qubits and systems composed of qubits, the Fourier transform of a general system is mathematically distinct from a Fourier matrix.  In particular, a Fourier matrix is a Fourier transform equipped with the choice of an isomorphism that is, in general, non-canonical. These Fourier matrices then correspond to strongly complementary observables (with a choice of isomorphism) in the same way that complex Hadamard matrices correspond to complementary ones. The relationship between these concepts is illustrated in Figure~\ref{fig:FTtoHrelationship}. The section proceeds along the following outline:

\begin{figure}
\includegraphics[width=\linewidth]{images/ftschematic.eps}
\caption{Schematic of the relationship between Fourier transforms, Fourier matrices, Hadamard matrices, strongly complementary observables, and complementary observables.}
\label{fig:FTtoHrelationship}
\end{figure}

Section \ref{sec:FT} gives background for the traditional notion of the Fourier transform as is relevant for our construction.  We also emphasize the relationship between several different, but related concepts: the Fourier transform, Fourier matrices, and (complex) Hadamard matrices.

In Section \ref{sec:strcompl} we cover the definition of strong complementarity~\cite{coecke2011interacting}, which has been used in the foundations of quantum mechanics to study non-locality~\cite{coecke2012strong, gogioso2015mermin} (Chapter~\ref{chap:mermin}), quantum secret sharing~\cite{gogioso2015mermin, zamdzhiev2012abstract} (Section~\ref{section_QSS}), and blackbox quantum algorithms~\cite{vicary-tqa, zeng2014abstract, zeng2015models} (Section~\ref{sec:blackbox}). This allows a generalization beyond $\cat{FHilb}$ to strongly complementarity pairs of a quasi-Special $\dagger$-Frobenius Algebra ($\dagger$-qSFA or $\dagger$-qSCFA if commutative) and a $\dagger$-SCFA. We use this generalization to embed finite groups in arbitrary dagger symmetric monoidal categories.

In Section \ref{section_AbelianGroups_FourierTransform} the usual Fourier transform concepts from Section \ref{sec:FT} are lifted to general symmetric monoidal categories. We construct the accompanying general definitions for multiplicative characters and the abelian Fourier transform in this setting.  These results allow us to provide categorical versions, with abstract proofs, of the Fourier inversion theorem, the convolution theorem, and Pontryagin duality that are all based on a strongly complementary pair of observables.

In Section \ref{section_RelFT}, we study $\RelCategory$ as an example setting for our categorical Fourier transform. This example is of particular interest as it often acts as a toy model for quantum theory~\cite{evans2009classifying, cqm-notes, pavlovic2009quantum, zeng2015models}.  We find that while a generalized Fourier matrix is not suitably defined, a Fourier transform can be.

In Section \ref{section_NonAbelianFourierTransform} we review extensions of these results to the non-abelian case, with accompanying Fourier transform. Then, in Section~\ref{sec:measrep}, we summarize how these results relate to measurements in the ``representation basis."

These results both move Fourier theory into a new mathematical setting and capture the structural connection between quantum theory and the Fourier transform.  Though this connection has been much exploited in quantum algorithms, this work is the first abstract presentation that shows its place in the structure of quantum theory, i.e. alongside strongly complementary observables.
\subsection{The Fourier transform}
\label{sec:FT}
We begin with a quick review of Pontryagin duality and the Fourier transform as it relates to quantum computation. A number of different notions related to the Fourier transform on finite abelian groups can be found in mathematics, physics, computer science and quantum computation, so it is useful to clarify them:

\begin{enumerate}
  \item[1.] In mathematics, the Fourier transform is understood through Pontryagin duality.
  \item[2.] In physics and signal processing, the Fourier transform is understood as a transformation of fields/signals from time/space domain to energy\footnote{Or frequency.}/momentum domain.
  \item[3.] In quantum computing, we have Fourier matrices and (complex) Hadamard matrices that correspond to unitary quantum processes.
\end{enumerate}

This section is ultimately concerned with the first notion, where the Fourier transform is defined on locally compact groups. Still, the other notions are relevant, as our work situates this abstract definition in the context of QPTs, a structure inherited from quantum information. 

We begin by explaining the relationship of Notion 1 with the others listed above. In what follows, $(G,\cdot,0)$ is a finite abelian group of order $N$, and $\complexs^{\times}=\complexs\setminus\{0\}$ is the multiplicative group of non-zero complex numbers.

A \textbf{(multiplicative) character} of $G$ is a group homomorphism $\chi:G\to \complexs^\times$.\footnote{For finite $G$, $\chi$ maps into the subgroup $S^1 \subseteq C^\times$ of unit complex numbers.} If $G = \prod_j \integersMod{n_j}$,\footnote{Which is always true when $G$ is finite, for some family $(n_j)_j$ of positive integers.} a multiplicative character $\chi_h$ takes the following form, for any $g,h\in G $ s.t. $h=\prod_jh_j$ and $g = \prod_jg_j$:
\begin{equation}
\label{eqn:FTDefCharacters}
  g\mapsto \exp\left[\, i \, \sum_j \frac{2 \pi}{n_j} \left(\modclass{g_jh_j}{n_j}\right) \, \right]
\end{equation}

The set of characters, with pointwise multiplication defined as $(\chi\cdot\psi)(x):=\chi(x)\psi(x)$, forms a group; this is called the \textbf{Pontryagin dual} (or \textbf{dual group}) of $G$, and is denoted $G^\wedge$. In fact, the Pontryagin construction can be made (contravariantly) functorial on the category \cat{Grp} of groups and group homomorphisms. Define $f^\wedge : G^\wedge \rightarrow H^\wedge$, for any $f: H \rightarrow G$ morphism of abelian groups, as follows:
\begin{equation*}
  f^\wedge( \chi ) = \chi \circ f.
\end{equation*}

From~\eqref{eqn:FTDefCharacters} it is not hard to see that $G^\wedge \isom G$.\footnote{Note that if $G \isom H$, then there are always exactly as many isomorphisms $G \isom H$ as there are automorphisms $G \isom G$.} However, this isomorphism is \emph{not canonical}. This means that there is no natural way of identifying the multiplicative characters with group elements, and we must keep track of our choice of isomorphism $G^\wedge \isom G$. Remarkably though, there is a canonical isomorphism $G \isom (G^\wedge)^\wedge$ given as follows, making the functor $(-)^{\wedge}:$ \cat{Grp} $\to$ \cat{Grp} is its own (weak) inverse:
\begin{equation*}
  g \mapsto (\chi \mapsto \chi(g)).
\end{equation*}

\newcommand{\FourierTransformSym}[1]{\mathcal{F}_{#1}}
\newcommand{\InverseFourierTransformSym}[1]{\mathcal{F}_{#1}^{-1}}
\newcommand{\FourierTransform}[1]{\mathcal{F}_G[#1]}
\newcommand{\InverseFourierTransform}[1]{\mathcal{F}_G^{-1}[#1]}

We are now ready to introduce the Fourier transform in the context of Pontryagin duality: this is the most abstract among the notions, and the others are derived from it. Let $\Ltwo{G}$ denote the space of functions $f:G\to \complexs$. These functions are necessarily square-integrable (as $G$ is finite), and thus $\Ltwo{G}$ is an $N$-dimensional complex Hilbert space (and lives in the category $\fdHilbCategory$ of finite-dimensional complex Hilbert spaces and linear maps). 

\begin{defn}
The \textbf{Fourier transform} for a finite abelian group $G$ is a bijection $\mathcal{F}_G:\Ltwo{G}\rightarrow\Ltwo{G^\wedge}$, sending $f:G\to\complexs$ to the $\bar{f}:=\FourierTransform{f}:G^\wedge\to\complexs$ defined as follows:
\begin{equation}\label{eqn:DefTraditionalFT}
  \FourierTransform{f}(\chi) := \frac{1}{N}\sum_{g \in G}\chi^{-1}(g)f(g).
\end{equation}
The \textbf{Inverse Fourier transform} is the inverse bijection $\mathcal{F}_G^{-1}: \Ltwo{G^\wedge} \rightarrow \Ltwo{G}$ and is defined as follows:
\begin{equation}\label{eqn:DefTraditionalInverseFT}
  \InverseFourierTransform{\bar{f}}(g) := \sum_{\chi \in G^\wedge}\chi(g)\bar{f}(\chi).
\end{equation}
\end{defn}

The Fourier transform is natural.  This means it is invariant under automorphisms of abelian groups (note that the isomorphism $G \isom G^\wedge$ was not). Let $\Psi : G \rightarrow H$ be some isomorphism where $M_\Psi = \Ltwo{G} \rightarrow \Ltwo{H}$ is the corresponding unitary isomorphism that takes $f\mapsto f\circ \Psi$. We then always have:
\begin{equation}\label{eqn:FTcanonicity}
  M_{\Psi^\wedge} \circ \mathcal{F}_H \circ M_\Psi =  \mathcal{F}_G,
\end{equation}

There are a number of properties of interest for the Fourier transform, some rather straightforward and others more complicated to prove. One of specific interest to this work, because of its wide application and relationship with structures in QPTs, is the Convolution Theorem. The space $\Ltwo{G}$ comes with a distinguished orthonormal basis, given by the \textbf{delta functions} $(\delta_g)_{g\in G}$ defined as follows.
\begin{equation}
\label{eqn:computationalBasis}
  \delta_g(h):=\begin{cases}
    1, & \text{if $h=g$}.\\
    0, & \text{otherwise}.
  \end{cases}
\end{equation}
We sometimes refer to this as the \textbf{computational basis}, the name usually given to it in the context of (group-theoretic) quantum algorithms.

The computational basis comes with a monoid structure, defined below and with unit $\delta_0$:
\begin{equation}
  \left(\delta_g*\delta_h\right):=\delta_{g+h}.
\end{equation}

Linearly extended to $\Ltwo{G}$, this structure yields the \textbf{convolution operation} $\left( \Ltwo{G},*,\delta_0 \right)$.
\begin{align}
\label{eqn:convolutionOperation}
\left(f * f'\right) = \left(\sum_{g\in G} f(g) \delta_g \right) * \left( \sum_{g' \in  G} f'(g') \delta_{g'} \right) &= \sum_{g\in G} \sum_{g'\in G'} f(g) f'(g') \delta_{g+g'} \\ 
&= \sum_{h\in G} \left(\sum_{g'\in G} f(h-g') f'(g')\right) \delta_h
\end{align}

The Fourier transforms of the delta functions yield the following orthogonal basis for $\Ltwo{G^\wedge}$, which we refer to as the \textbf{basis of evaluation functions}:
\begin{align*}
\xi_{g} := \sqrt{N}\mathcal{F}[\delta_{-g}] = \left(\chi \mapsto \sum_{h \in G}\chi^{-1}(h)\delta_{-g}(h) \right)= \left(\chi \mapsto \chi(g)\right).
\end{align*}

The basis of evaluation functions also comes with a monoid structure, with unit $\xi_0: \chi \mapsto 1$:
\begin{equation*}
  \left(\xi_g\cdot\xi_h\right):= \chi \mapsto \xi_g(\chi)\xi_h(\chi) = \chi \mapsto \chi(g)\chi(h).
\end{equation*}

Functions $F \in \Ltwo{G^\wedge}$ on the dual group have the following expansion in terms of evaluation functions:
\begin{equation*}
  F = \sum_{g\in G} \left( \frac{1}{N}\sum_{\chi \in G^\wedge} F(\chi) \chi^{-1}(g) \right) \xi_g
\end{equation*}

Linearly extended to $\Ltwo{G^\wedge}$, the monoid structure above yields the \textbf{pointwise multiplication} $\left( \Ltwo{G^\wedge},\cdot,\xi_0 \right)$: 
\begin{align}
\label{eqn:PointwiseMultCharacters}
  \left(F \cdot F' \right) &= \tau \mapsto \sum_{\chi,\kappa \in G^\wedge}  F(\chi)  F'(\kappa) \left(\frac{1}{N} \sum_{g\in G} \chi^{-1}(g)\tau(g)\right) \left(\frac{1}{N} \sum_{g'\in G}\kappa^{-1}(g') \tau(g') \right) \\ &= \tau \mapsto F(\tau) F'(\tau)
\end{align}
We use the (easy to check) fact that, for any $\chi,\tau \in G^\wedge$, the expression $\frac{1}{N} \sum_{g\in G}\chi^{-1}(g) \tau(g)$ yields $1$ if $\tau = \chi$ and $0$ otherwise (this is usually referred to as \textbf{orthogonality of (multiplicative) characters}).

\begin{theorem}[Convolution Theorem]
The Fourier transform is a monoid isomorphism in $\fdHilbCategory$, from the convolution monoid $\left( \Ltwo{G},*,\delta_0 \right)$ to the pointwise multiplication monoid $\left( \Ltwo{G^\wedge},\cdot, \xi_0 \right)$. This statement amounts exactly to the following expression (for every $f\in \Ltwo{G}$), which is the usual formulation of the Convolution Theorem: 
\begin{equation}\label{eqn:ConvolutionTheorem}
  \mathcal{F}_G (f') \cdot \mathcal{F}_G (f) = \mathcal{F}_G (f * f').
\end{equation}
\end{theorem}

This concludes our presentation of the Fourier transform in the context of Pontryagin duality. A further reference for details of the topics in this presentation is~\cite{rudin1962fourier}. The Fourier transform finds wide applicability in signal processing, physics, engineering and the applied sciences, but the full formulation based on Pontryagin duality is rarely used, if mentioned at all. In the engineering context, one usually considers periodic real-valued or complex-valued functions on a $D$-dimensional space, discretized in a rectangular $D$-dimensional lattice, and defines the (Discrete) Fourier transform as a transformation on them. Due to the periodicity conditions, complex-valued functions on a rectangular $D$-dimensional lattice can be equivalently seen as living in $\Ltwo{G}$, where $G = \prod_{j=1}^D \integersMod{n_j}$ and $n_j$ is the number of lattice sites along the $j$-th dimension. The  Fourier transform $\mathcal{G} : \Ltwo{G} \rightarrow \Ltwo{G^\wedge}$ defined above sends these functions onto functions on another, isomorphic $D$-dimensional lattice corresponding to $G^\wedge$. In order to obtain functions living back on the original lattice, one \emph{fixes an isomorphism} $\Psi : G \rightarrow G^\wedge$ (traditionally the one from Equation \ref{eqn:FTDefCharacters}), and defines the Discrete Fourier transform as the following transformation on $\Ltwo{G}$:
\begin{equation}\label{eqn:FTDefDFT}
  \mathbf{F} := f \mapsto \mathcal{F}_G(f) \circ \Psi.
\end{equation}

This definition has the advantage of working with functions on the same lattice, but the disadvantage of implicitly depending on the choice $\Psi$ of isomorphism.\footnote{This is a common issue in signal processing and physics, where it is related to the symmetry group of the underlying space and the choice of units of measure for energy/frequency. We will not discuss this further.} The transformation $\mathbf{F}$ from Equation \ref{eqn:FTDefDFT} is in fact a unitary automorphism of $\Ltwo{G}$. Its matrix $(\mathbf{F}_{hg})_{h,g \in G}$ in the computational basis is:
\begin{equation} \label{eqn:HadamardMatrixDef}
  \mathbf{F}_{hg} = \exp\left[\, i \, \sum_j \frac{2 \pi}{n_j} \left(\modclass{g_jh_j}{n_j}\right) \, \right] %\text{ for } h = (h_j)_{j=1,...,D} \text{ and } g = (g_j)_{j=1,...,D} \text{ in } G = \prod_{j=1}^D \integersMod{n_j}
\end{equation}
and it is called a \textbf{Fourier matrix} in the context of quantum computing.

Fourier matrices correspond to a Fourier transform along with a choice of the isomorphism. Thus the Fourier matrices, exactly like the definition of the Discrete Fourier transform above, are non-canonical, and depend on an implicit choice of isomorphism $\Psi$. This contrasts with the Fourier transform, which is itself canonical.

Fourier matrices are a subclass of more general \textbf{complex Hadamard matrices}: orthogonal matrices\footnote{Here an orthogonal matrix $H$ is a square matrix such that $H^TH=HH^T=\mathbbm{1}$.} whose complex entries are unimodular, in particular (real) \textbf{Hadamard matrices} are orthogonal matrices with entries $\pm1$. Having defined these four different terms (the Fourier transform, Fourier matrices, Hadamard matrices, and complex Hadamard matrices, see Figure~\ref{fig:FTtoHrelationship}) we will clarify a few ways that they appear in quantum computation.

There is a particularly interesting reason the lack of canonicity of Fourier matrices is not usually an issue in quantum computing. Most of the algorithms are traditionally formulated for qubits, and the state-space of a $D$-qubit system is isomorphic to $\Ltwo{G}$ for $G = \prod_{j=1}^D \integersMod{2}$. The group $\integersMod{2}$ has a unique automorphism (the identity), and thus a unique isomorphism $\integersMod{2} \rightarrow \integersMod{2}^\wedge$, resulting in the familiar matrix
\begin{equation}
\label{hmat}
\begin{pmatrix}1 & 1 \\
1 & -1 \\
\end{pmatrix},
\end{equation}
which is both the only Fourier matrix on a two dimensional system and, in fact, a Hadamard matrix. There is then a unique isomorphism $\Psi : \integersMod{2}^N \rightarrow (\integersMod{2}^N)^\wedge$ which can be obtained by local qubit operations only, namely the $N$-fold tensor product of the isomorphism in \ref{hmat}; if multi-qubit operations are allowed, however, the isomorphism is not unique. We stress that for general groups, i.e. for combinations of quantum systems where some have dimensions larger than two, the Fourier transform in terms of Pontryagin duality does not fix a unique Fourier matrix (not even requiring that it is obtained by local operations only). Furthermore, not all complex Hadamard matrices correspond to a Fourier matrix. We'll return to these ideas in Section~\ref{sec:measrep}, but until then we use Fourier transform to refer explicitly to the canonical one defined in terms of Pontryagin duality.

There are a number of existing generalizations in the literature of the Fourier transform presented here that we make contact with to varying degrees. 
\begin{enumerate}
\item[1.] Pontryagin theory can be extended from finite abelian groups to arbitrary locally compact abelian groups equipped with the Haar measure: the groups $G$ and $G^\wedge$ are not necessarily isomorphic (e.g. $\reals^\wedge = \reals$ but $\integers^\wedge = S^1$), but the Fourier transform is still a canonical isomorphism between $\Ltwo{G}$ and $\Ltwo{G^\wedge}$, and it's still true that $(G^\wedge)^\wedge = G$. 

\item[2.] The representation theory can be extended from abelian to arbitrary locally compact groups by observing that $\Ltwo{G}$ is always a $C^\star$ algebra, and considering the Gelfand-Naimark representation. In the abelian case, this representation coincides with the Fourier transform. This connection is elaborated on in~\cite{gogioso2015fourier}. 

\item[3.] Tannaka-Krein duality provides a different generalisation from compact abelian groups to arbitrary compact groups that we saw previously in Example~\ref{ex:smcs}: the finite-dimensional linear representations of a compact group $G$ form a symmetric monoidal category $\Pi(G)$, generalising $G^\wedge$, with representations $R:G \rightarrow \Endoms{}{V_R}$ as objects, intertwiners (linear maps $f: V_R \rightarrow V_S$ s.t. $f \circ R(g) = S(g) \circ f$ for all $g\in G$) as morphisms and tensor product of representations as monoidal tensor. The category $\Pi(G)$ comes with a complex conjugation operation on morphisms, and a theorem of Tannaka shows that the set $\Gamma(\Pi(G))$ of all self-conjugate monoidal natural transformations $\idm{\Pi(G)} \rightarrow \idm{\Pi(G)}$ forms (once equipped with composition of natural transformations and an appropriate topology) a compact group isomorphic to $G$. A generalisation of Tannaka-Krein duality to braided monoidal categories appears in the representation theory of Drinfeld-Jimbo quantum groups. In this work, we do not deal with either Tannaka-Krein theory or Drinfeld-Jimbo quantum groups.
For more on quantum groups and their connection to Hopf algebras see, 
e.g.~\cite{cartier2007primer,street2007quantum}.
\end{enumerate}

\subsection{Strong Complementarity}
\label{sec:strcompl}

We will eventually show that the Fourier transform is related to a special type of complementarity called strong complementarity. In this section we introduce this strongly complementary notion. Definition \ref{def:classicalstruct} introduced classical structures as special and symmetric Frobenius algebras.  Here we operate with the slightly weaker notion of a quasi-special commutative Frobenius algebras. This is for convenience and allows us to lump scalars together rather than having to keep track of them at every step.

\begin{defn}\label{def:QuasiSpecial}
A \textbf{quasi-special} $\dagger$-Frobenius algebra \whitefrob{A} is one that satisfies the following equation for some invertible scalar $N$:
\begin{equation}\label{eqn:QuasiSpecialDef}
\begin{aligned}
\begin{tikzpicture}[xscale={1.5*\tikzxscale}, yscale={1.5*\tikzyscale}]
\draw (0,0.25) to (0,1) node [whitedot] {} to [out=\nwangle, in=down] (-0.5,1.5) to [out=up, in=\swangle] (0,2) node [whitedot] {} to (0,2.75);
\draw (0,1) to [out=\neangle, in=down] (0.5,1.5) to [out=up, in=\seangle] (0,2);
\end{tikzpicture}
\end{aligned}
\quad=\quad
  \begin{aligned}
  \begin{tikzpicture}[xscale={1.5*\tikzxscale}, yscale={1.5*\tikzyscale}]
  \node [whitedot] at (-1.5,1.5) {$N$};
  \draw (-0.5,0) to (-0.5,3);
  \end{tikzpicture}
  \end{aligned}
\end{equation}
We will use the shorthand $\dagger$-qSFA, and refer to $N$ as the \textbf{normalisation factor} for the $\dagger$-qSFA.
\end{defn}

These $\dagger$-qSFA's can be thought of as generalized orthogonal bases that are normalize-able (as long as the square root of the scalar $\sqrt{N}$ is invertible) even if they are not normalized.  While classical states can be defined in any $\dagger$-SMC, the following definition for matching families requires an appropriate \textit{zero scalar}. For this and other reasons, we consider categories enriched over commutative monoids,\footnote{Refer to Section~\ref{sec:enrichedQPTs} for more detail on enriched QPTs.} i.e. where homsets come with a commutative monoid structure $(\cat{C}(A,B),+,0)$, and we require the appropriate distributivity laws between the tensor product and the monoidal structure:
\begin{align}
(f+g) \tensor h &= (f\tensor h) + (g \tensor h)\\
f \tensor (g+h) &= (f \tensor g) + (f \tensor h)\\
0 \tensor f &= 0\\
f \tensor 0 &= 0
\end{align}

We will refer to these as \textbf{distributively $\cat{CMon}$-enriched} $\dagger$-SMCs.

\begin{defn}
\label{def:matchables}
Let $\ket{x}_{x \in X}$ be a finite family of states $I \rightarrow \SpaceG$ in a $\dagger$-SMC which is distributively $\cat{CMon}$-enriched. A \textbf{matchable family} $\ket{x}_{x \in X}$ for a monoid $(\SpaceG,\XmultSym, \XunitSym)$ are those for which the following holds for all $x,y \in X$:
\begin{equation}\label{eqn:matchables}
    \XmultSym \circ \left( \ket{x} \tensor \ket{y} \right) = 
    \begin{cases} 
        \ket{x} \text{ if } \ket{x} = \ket{y}\\
        0 \text{ otherwise }
    \end{cases}
\end{equation}
\end{defn}

We re-emphasize that while $\dagger$-qSCFA's correspond to bases in $\cat{FHilb}$ by Theorem~\ref{thm:cstructBases}, the general notion of a (orthogonal) basis is somewhat different.

\begin{defn}\label{def:basis}
A finite family of states $\ket{x}_{x\in X}: I \rightarrow \SpaceH$ is a \textbf{(orthogonal) basis} (for~$\SpaceH$) if it satisfies the following conditions:
\begin{enumerate}
\item[(i)] Orthogonality, i.e. $\langle y|x\rangle = 0$ if $x \neq y$ (where $\bra{y}$ stands for $\ket{y}^\dagger$).
\item[(ii)] Completeness, i.e. for every $f,g : \SpaceH \rightarrow \SpaceH'$ we have that $\forall x:X \, f \ket{x} = g \ket{x}$ implies $f=g$. 
\end{enumerate}
A finite family of co-states $\bra{x}_{x\in X}: \SpaceH \rightarrow I$ is a \textbf{(orthogonal) cobasis} (for $\SpaceH$) if the family of states $\ket{x}_{x\in X}: I \rightarrow \SpaceH$ is a basis.
\end{defn}
\noindent When the classical states for a classical structure form a basis in this manner, the algebra has ``enough classical points" (Definition \ref{def:enoughclassicalpoints}). In $\cat{FHilb}$, this is the usual linear-algebraic notion of orthogonal basis.
 
Strong complementarity was originally introduced by Coecke and Duncan in~\cite{coecke2011interacting} as the additional rule that makes classical structures into a Hopf algebra.\footnote{ They are also studied in this form, though separately from the process theoretic framework, as a foundation for graphical linear algebra by Bonchi et al.~\cite{bonchi2014interacting}.}

\begin{defn}\label{def:StrongComplementarity}
A pair of $\dagger$-qSFAs \whitefrob{A} and \blackfrob{A}, henceforth written as \scpair, is \textbf{strongly complementary} if they are coherent (Definition \ref{def:coherence})  and  satisfy the following \textbf{bialgebra equation} (\ref{eqn:bialgebraEqns}):
\begin{equation}
\label{eqn:bialgebraEqns}
\input{tikz/2_bialgebra.tikz}
\end{equation}
\end{defn}
\noindent Though this definition is usually given for classical structures, we generalise to $\dagger$-qSFAs to include non-commutative algebras and, hence, our later construction of a generalized non-abelian Fourier transform.

\begin{remark}
Recall that under certain assumptions on the $\dagger$-FAs that are common in process theories, the antipode is self-adjoint~\cite[Lem. 7.2.6]{kissinger2012pictures}, though we will work in the more general setting.
\end{remark}

It is easy to see that the name is an apt one, i.e. that strongly complementarity classical structures are also complementary in the sense of Definition \ref{def:complementarity}:
\begin{equation}
\input{tikz/3_SCIsC.tikz}
\end{equation}
where we have also assumed a self-adjoint antipode in the first step.

As we have slightly generalized the definition of strong complementarity, we also wish to present a slightly more general concept of an antipode that is not self-inverse. Note the slight difference between this definition and Definition~\ref{def:complementarity}. Our results will, of course, still hold in the case of a self-adjoint antipode.

\begin{defn}\label{def:Antipode} 
Given a strongly complementary pair of $\dagger$-FAs $\scpair$ on some object $\SpaceG$ in a $\dagger$-SMC, the \textbf{antipode} $\antipodeSym:\SpaceG \rightarrow \SpaceG$ is defined to be the following map:
\begin{equation}
    \input{tikz/3_antipode.tikz}
\end{equation}
\end{defn}

\begin{lemma}\label{lemma_AntipodeInverse}
Given a strongly complementary pair of $\dagger$-FAs \scpair~on some object $\SpaceG$ in a $\dagger$-SMC, the \textbf{antipode inverse} $\antipodeSym^{-1}:\SpaceG \rightarrow \SpaceG$ is the following map:
\begin{equation}
    \input{tikz/3_antipodeInverse.tikz}
\end{equation}
Furthermore, if at least one of the two $\dagger$-FAs has a finite matchable family that forms a basis, then the antipode is self-adjoint and unitary, i.e. antipode and antipode inverse coincide.
\end{lemma}
\begin{proof}
    The fact that $\antipodeSym^{-1}$ as defined is indeed the inverse of $\antipodeSym$ is an immediate consequence of the Frobenius law (one application per colour). Now suppose without loss of generality that the matchable states $\ket{g}_{g \in G}$ of $\XdotSym$ form a basis, and remember that $\ZdotSym$ acts as some (possibly non-abelian) group $(G,\cdot,1)$ on them (Lemma~\ref{lem:phaseunbiased}). Then $\bra{h}\, \antipodeSym \ket{g} = \braket{h \cdot g}{1}$ and $\bra{h} \; \antipodeSym^{-1} \ket{g} = \braket{1}{h \cdot g}$ and $\bra{h}\; \antipodeSym^\dagger \ket{g} = \braket{1}{g \cdot h}$ and $\bra{h}\; (\antipodeSym^{-1})^\dagger \ket{g} = \braket{g \cdot h}{1}$ coincide for all $g,h \in G$, proving that $\antipodeSym = \antipodeSym^{-1} = \antipodeSym^{\dagger} = \ket{g} \mapsto \ket{g^{-1}}$ for all $g\in G$.
\end{proof}

Coecke and Duncan showed that strongly complementary classical structures have a specific relationship between their phase groups and classical states.

\begin{theorem}[\cite{coecke2011interacting}]
Let \whitecomonoid{A} and \blackcomonoid{A} be a pair of strong complementary classical structures with finite numbers of classical states. Then $K_{\dotonly{blackdot}}\subseteq P_{\dotonly{whitedot}}$, i.e. the classical states of the black classical structure form a subgroup of the phase group of the white classical structure. The converse is true when \blackcomonoid{A} has enough classical points.
\end{theorem}

This leads to Kissinger's motivating classification of strongly complementary classical structures:
\begin{corollary}[{\cite[Cor. 3.10]{coecke2012strong}}]
\label{col:SCclassification}
Every pair of strongly complementary classical structures in \cat{FHilb} is
of the following form: 
\begin{equation}
\left\{\begin{array}{cl}
\tinycomult[blackdot]   & :: \ket{g}\mapsto \ket{g}\otimes \ket{g}\vspace{1mm}\\
\tinycounit[blackdot] & :: \ket{g}\mapsto 1
\end{array}\right.
\quad
\left\{\begin{array}{cl}
\tinymult[whitedot]   & :: \ket{g}\otimes \ket{h} \mapsto {1\over\sqrt{D}} \ket{g + h}\vspace{1mm} \\
\tinyunit[whitedot] & :: 1 \mapsto \sqrt{D} \ket{0}
\end{array}\right.
\end{equation}
where $(G =\{g, h, \ldots\}, +, 0)$ is a finite Abelian
group. Conversely, each such pair is always strongly complementary.  
\end{corollary}

Inspired by this classification, we use strongly complementary structures to embed groups into an arbitrary QPT.

\begin{defn}\label{def:AbClassicalGroup} An \textbf{internal group}, denoted by $(\,\SpaceG , \timemultSym, \timeunitSym, \tinycomult[blackdot], \tinycounit[blackdot]$ ) or  $(\,\SpaceG , \dotonly{whitedot}, \dotonly{blackdot})$ when no confusion should arise), consists of a strongly complementary pair on the same object $\SpaceG$ of a $\dagger$-SMC and
\begin{enumerate}
\item A $\dagger$-qSFA \whitefrob{\mathcal{G}}, the \textbf{group structure}, denoted by $\dotonly{whitedot}$.
\item A $\dagger$-qSCFA \blackfrob{\mathcal{G}}, the \textbf{point structure}, denoted by $\dotonly{blackdot}$.
\end{enumerate}
The multiplication and unit for the group structure are called \textbf{group multiplication} and \textbf{group unit}, and the antipode $\antipodeSym$ for the pair is called the \textbf{group inverse}. An \textbf{abelian internal group} is one where the group structure is commutative.
\end{defn}

The internal groups in a QPT form a category $\cat{Grp}[\cat{C}]$, with objects given by the strongly complementary pairs $(\,\SpaceG , \dotonly{whitedot}, \dotonly{blackdot})$, and morphisms $(\,\SpaceG , \dotonly{whitedot}, \dotonly{blackdot}) \rightarrow (\,\SpaceG' , \dotonly{altwhitedot}, \dotonly{altblackdot})$ given by $f: \SpaceG \rightarrow \SpaceG'$ in $\cat{C}$ that are co-monoid homomorphisms $f: (\tinycomult[blackdot],\tinycounit[blackdot]) \rightarrow (\tinycomult[altblackdot],\tinycounit[altblackdot])$ and monoid homomorphisms $f: (\tinymult[whitedot],\tinyunit[whitedot]) \rightarrow ( \tinymult[altwhitedot],\tinyunit[altwhitedot])$; the abelian internal groups form a full subcategory $\cat{AbGrp}[\cat{C}]$. We will refer to these morphisms as \textbf{internal group homomorphisms}, both when seen as morphisms in $\cat{Grp}[\cat{C}]$ and in $\cat{C}$.

\begin{theorem}\label{thm_InteralGroupsTraditionalGroups} 
        If $(\,\SpaceG , \dotonly{whitedot}, \dotonly{blackdot})$  is an (abelian) internal group in any $\dagger$-SMC, then $(\timemultSym, \timeunitSym)$ acts as an (abelian) group $G$ on the classical points of $(\;\timediagSym, \trivialcharSym)$, henceforth the \textbf{group elements}. Furthermore, this correspondence yields an equivalence between the category of (abelian) internal groups in $\cat{FHilb}$ and the category of finite (abelian) groups.
\end{theorem}

In $\cat{FHilb}$, the point structure $(\dotonly{blackdot})$ characterises the group elements $\ket{g}_{g\in G}$ as an orthonormal basis for $\SpaceG$.  This is the basis of delta functions from Equation \ref{eqn:computationalBasis}, with $\ket{g} := \delta_g$. The corresponding isomorphism $\Ltwo{G} \isom \SpaceG$ sends any square-integrable $f: G \rightarrow \complexs$ to the vector $\ket{f} \in \SpaceG$ defined by $\ket{f} = \sum_{g\in G} f(g) \ket{g}$. Also under this isomorphism, the multiplicative fragment $(\, \SpaceG,\timemultSym,\timeunitSym)$ of the internal group structure acts as the convolution operation from Equation \ref{eqn:convolutionOperation}. Simply put, an internal group  $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ in $\fdHilbCategory$ consists of:
\begin{enumerate}
\item[(i)] a space $\SpaceG$
\item[(ii)] a distinguished orthogonal basis, encoded by the $\dagger$-qSCFA $\XdotSym$
\item[(iii)] a group structure on that basis, encoded by the $\dagger$-qSFA $\ZdotSym$
\end{enumerate}


From the point of view of the category $\cat{Grp}[\cat{C}]$, $\mathbb{G}$ should be understood as the group $G$ encoded by $\ZdotSym$, while from the point of view of the category $\fdHilbCategory$ it should be considered as endowing $\SpaceG$ with the structure of $\Ltwo{G}$.\footnote{In this correspondence, the orthogonal basis in $\SpaceG$ corresponds to the basis of delta functions in $\Ltwo{G}$, as given in Equation \ref{eqn:computationalBasis}. The groups structure given by $\ZdotSym$ corresponds to the convolution operation from Equation \ref{eqn:convolutionOperation}.} As we abstract away from Hilbert spaces, we will take this conceptual standpoint. Sometimes, when talking about an internal group $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$, we will refer to states $\ket{f} : I \rightarrow \SpaceG$ as \textbf{states of $\mathbb{G}$}, generalising square-integrable functions $f\in \Ltwo{G}$.

\subsection{Abelian Fourier transform}
\label{section_AbelianGroups_FourierTransform}

The previous section provides us with the basic tools to do group theory in arbitrary $\dagger$-SMCs. We can now connect it to the more traditional theory from in Section~\ref{sec:FT}. We begin by introducing multiplicative characters as co-states, building on ideas from Vicary~\cite{vicary-tqa} and~\cite{zeng2014abstract}.

The use of the $\Ltwo{G}$ notation in this section is consistent with the fact that $\LtwoSym$-spaces over finite groups are exactly finite-dimensional Hilbert spaces that come with a canonical choice of basis (the group elements) and a group operation over them. Throughout, we have identified $\Ltwo{\hat{G}}\isom \Ltwo{G}^\star$ as the multiplicative characters are a basis of $\Ltwo{G}^\star$.

\begin{defn}\label{def:MultiplicativeCharacters}
A \textbf{multiplicative character} for a pair \scpair~in a $\dagger$-SMC is a monoid homomorphism from $(\timemultSym, \timeunitSym)$ to the canonical monoid on the trivial object $I$ induced by the unitors, or equivalently it is a co-state $\multCharacterEffectSym{}: \SpaceG \rightarrow I$ satisfying the following equations:
        \begin{equation}\label{eqn:MultCharDef}
                \input{tikz/3_multchardef.tikz}
        \end{equation}
\end{defn}

\begin{lemma}\label{thm_AbCopiablesMultiplicativeCharacters}
If $(\,\SpaceG,\ZdotSym,\XdotSym)$ is an internal group in a $\dagger$-SMC, then the classical states of the group structure are exactly the (adjoints of its) multiplicative characters. In the case of $\fdHilbCategory$, the group structure of an abelian internal group thus characterises the (group theoretic) multiplicative characters of $G$ as a co-basis for $\SpaceG$.
% all characters having norm $N$, the normalisation factor for $\XdotSym$.
\end{lemma}
\begin{proof} 
  The first part is immediate, the second follows from the equivalence of classical structures and bases in Theorem~\ref{thm:cstructBases}.
\end{proof}

In $\fdHilbCategory$, the multiplicative characters of an internal group $(\,\SpaceG,\ZdotSym,\XdotSym)$ are co-states $\SpaceG \rightarrow \complexs$, while the multiplicative characters defined in Section \ref{sec:FT} are group homomorphisms $G \rightarrow \complexs^\times$. Under the isomorphism $\Ltwo{G} \isom \SpaceG$ given by the point structure, the multiplicative characters of the internal group are exactly the linear extensions to $\Ltwo{G}$ of the multiplicative characters of $G$. If the internal group is abelian, then the multiplicative characters are exactly the adjoints of the unique orthogonal basis associated with the $\XdotSym$ structure.

\begin{theorem}\label{thm_PontryaginDualsSMC}
Let $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ be an abelian internal group in a $\dagger$-SMC $\CategoryC$.
Then $\mathbb{G}^\wedge := (\,\SpaceG,\XdotSym,\ZdotSym)$ is an abelian internal group in the $\dagger$-SMC $\cat{C^{op}}$, and we shall refer to it as the \textbf{Pontryagin dual} of $(\,\SpaceG,\ZdotSym,\XdotSym)$. The group elements of $(\,\SpaceG,\XdotSym,\ZdotSym)$ are exactly the multiplicative characters of $(\,\SpaceG,\ZdotSym,\XdotSym)$ -- this is to say that $\timediagSym$ acts as a group, the \textbf{pointwise multiplication} group, on the multiplicative characters, with the \textbf{trivial character} $\trivialcharSym$ as unit. The antipode acts again as group inverse. 
\end{theorem}

It is worth clarifying that the pointwise multiplication of Equation \ref{eqn:PointwiseMultCharacters} is different from the pointwise multiplication of Theorem \ref{thm_PontryaginDualsSMC}: the former is a pointwise product of functions of characters, and would correspond to the co-monoid $(\timecomultSym,\timecounitSym)$ (because the group multiplication duplicates multiplicative characters), while the latter is a pointwise product of functions of group elements, and thus corresponds to the co-monoid $(\timediagSym,\trivialcharSym)$ (which duplicates group elements). Also, note that $(\mathbb{G}^\wedge)^\wedge = \mathbb{G}$, as in the traditional formulation of Pontryagin duality.

The usual formulation of the Fourier transform, and of its properties, involves several summations, but a careful analysis shows that they boil down to appropriate resolutions of the identity (Definition~\ref{def:resid}), like $\frac{1}{N} \sum_{g\in G} \ket{g}\bra{g} = \idm{\Ltwo{G}}$, and to various formulations of orthogonality of characters. The following lemma shows that, from a categorical perspective, the two are equivalent.

\begin{lemma}\label{lemma_BasisResolutionPartition}
Let $\XdotSym$ be a $\dagger$-qSFA with normalization $N$ on an object $\SpaceG$ in a $\dagger$-SMC which is distributively $\cat{CMon}$-enriched, and let $\ket{x}_{x\in X}$ be a finite set of classical states for the co-monoid $(\tinycomult[blackdot],\tinycounit[blackdot])$ such that
\begin{enumerate}
\item[(a.)] the family is \textbf{orthogonal}, i.e. $\langle x'|x\rangle= 0$ (the zero scalar) for all $x \neq x'$
\item[(b.)] the family is \textbf{normalisable}, i.e. $\langle x|x\rangle$ is an invertible scalar for all $x$.
\end{enumerate} 
Then the following are equivalent:
\begin{enumerate}
\item[(i)] The classical states $\ket{x}_{x\in X}$ form a (orthogonal) basis, as per Definition \ref{def:basis}.
\item[(ii)] The classical states $\ket{x}_{x\in X}$ form a \textbf{ resolution of the identity}, as per Definition~\ref{def:resid}.
\item[(iii)] The adjoints of the classical states form an \textbf{(orthogonal) partition of the counit}, i.e. they satisfy the following equation:
\begin{equation}\label{eqn:PartitionCounit}
\frac{1}{N}\sum_x \!\!\!\!\text{\effectSym{x}}\!\! = \tinycounit[blackdot]
\end{equation}
\end{enumerate}
\end{lemma}
\begin{proof}
Since we have assumed that $\langle \chi|\chi\rangle$ is invertible, then $\langle \chi|\chi\rangle = N$.
\begin{itemize}

\item $(i) \implies (ii)$ Suppose that the classical states form a basis, i.e. suppose that $\forall \chi , f \circ \ket{\chi} = g \circ \ket{\chi}$ implies $f=g$ (completeness). Then we get, for all $\chi'$:
\begin{equation*}
\left(\frac{1}{N} \sum_\chi \, \ket{\chi}\bra{\chi}\right) \circ \ket{\chi'} = \frac{1}{N} \ket{\chi'} \braket{\chi'}{\chi'} = \ket{\chi'} = \idm{\SpaceG} \circ \ket{\chi'}
\end{equation*}
where we have used orthogonality. We conclude $(ii)$ by completeness.

\item $(ii) \implies (iii)$ By using the fact that $\XcounitSym \circ \ket{\chi} = 1$ for all $\chi\in X$ we immediately get $(iii)$:
\begin{equation*}
\XcounitSym \circ \left(\frac{1}{N} \sum_\chi \ket{\chi} \bra{\chi} \right) = \frac{1}{N} \sum_\chi \left( \XcounitSym \circ \ket{\chi} \right) \bra{\chi} = \frac{1}{N} \sum_\chi \bra{\chi}
\end{equation*}
 
\item $(ii) \implies (i)$ All we have to prove is completeness, as orthogonality of the family $\ket{\chi}_{\chi\in X}$ was assumed as a hypothesis of the lemma. Assume $f \circ \ket{\chi} = g \circ \ket{\chi}$ for all $\chi$, then we get:
\begin{equation*}
\frac{1}{N} \sum_\chi f \circ \ket{\chi} \bra{\chi} = \frac{1}{N} \sum_\chi g \circ \ket{\chi} \bra{\chi}
\end{equation*}
But the LHS is $f \circ \idm{\SpaceG}$, i.e. $f$, and the RHS is $g \circ \idm{\SpaceG}$, i.e. $g$.


\item $(iii) \implies (ii)$ Assume that $\XcounitSym = \frac{1}{N} \sum_\chi \bra{\chi}$, then we get (using Frobenius law in the first equality):
\begin{align*}
\idm{\SpaceG} &= (\tinycounit[blackdot] \tensor \idm{\SpaceG})\circ (\XmultSym \tensor \idm{\SpaceG}) \circ (\idm{\SpaceG} \tensor \tinycomult[blackdot]) \circ (\idm{\SpaceG} \tensor \XunitSym) \\&= \frac{1}{N} \sum_\chi \frac{1}{N} \sum_{\chi'} \ket{\chi'} \braket{\chi'}{\chi} \bra{\chi} \\&= \frac{1}{N} \sum_\chi \ket{\chi} \bra{\chi}
\end{align*}
 
\end{itemize}

As a final remark, note that orthogonality, assumed separately, is already included in the definition of basis used in point $(i)$; it is, however, necessary to assume it explicitly in points $(ii)$ and $(iii)$. As for point $(iii)$, a counterexample can be found in $\fRelCategory$, by replacing an orthogonal family with the one obtained by repeating some element $\bra{\chi}$, and using the fact that $\bra{\chi} + \bra{\chi} = \bra{\chi}$ (since the enriched monoidal operation $\sum$ in \cat{FRel} is just the set union $\cup$). As for point $(ii)$, one can consider the category of finite-dimensional vector spaces over the field with 2 elements (where $1+1=0$): if $\ket{\chi}$ is a norm-1 vector in a 1-dimensional space $\SpaceG$, the family $(\ket{\chi},\ket{\chi},\ket{\chi})$ is non-orthogonal, and yet a resolution of the identity as $\ket{\chi}\bra{\chi}+\ket{\chi}\bra{\chi}+\ket{\chi}\bra{\chi} = \ket{\chi}\bra{\chi} = \idm{\SpaceG}$ (this cannot happen in $\fdHilbCategory$).
\end{proof}

The formulation in terms of orthogonal partition of the counit is related to the orthogonality of (multiplicative) characters traditionally mentioned in the context of Fourier transform (e.g. used here in Equation \ref{eqn:PointwiseMultCharacters}), as the following lemma shows. 

\begin{theorem}[Orthogonality of Multiplicative Characters] \label{lemma_OrthogonalityCharacters}
Let $(\,\SpaceG,\ZdotSym,\XdotSym)$ be an internal group in a $\dagger$-SMC $\CategoryC$, and $N$ be the normalisation factor for the quasi-special condition of $\ZdotSym$. Assume that the characters are all orthogonal, in the sense that $\braket{\chi}{\chi'} = 0$ for $\chi \neq \chi'$, and that $\braket{1}{1} = N$, where $\bra{1} := \tinycounit[blackdot]$ is the trivial character. Then if $\ket{\chi},\ket{\chi'}$ are (not necessarily distinct) multiplicative characters of the internal group, the following \textbf{orthogonality of multiplicative characters} holds:
\begin{equation}\label{eqn:orthogonalityMultChars}
        \input{tikz/3_orthogonalityMultChar.tikz}
\end{equation}
Now assume that \cat{C} is distributively $\cat{CMon}$-enriched. If the family $\bra{g}_{g\in G}$ of (adjoints of) group elements is normalisable and forms an orthogonal partition of the counit, then Equation \ref{eqn:orthogonalityMultChars} can be re-written in the following, more familiar form (where we have set $\ket{\chi^{-1}} := \ket{\chi} \circ \antipodeSym$):
\begin{equation}\label{eqn:orthogonalityMultCharsFamiliar}
\frac{1}{N}\sum_{g\in G} \braket{\chi^{-1}}{g}\braket{\chi'}{g} = \delta_{\chi\chi'}
\end{equation} 
\end{theorem}
\begin{proof}
By Theorem \ref{thm_PontryaginDualsSMC}, the comultiplication $\XcomultSym$ acts as a group on the multiplicative characters, and $\antipodeSym$ as the group inverse. The LHS of Equation \ref{eqn:orthogonalityMultChars} can be re-written as $\braket{\chi^{-1} \cdot \tau}{1}$, and $\cdot$ is the pointwise multiplication: since we assumed that the multiplicative characters are orthogonal, the result follows. In order to obtain Equation \ref{eqn:orthogonalityMultCharsFamiliar} from Equation \ref{eqn:orthogonalityMultChars}, all we have to do is observe that the group elements $\ket{g}_{g\in G}$ form an orthogonal partition of the unit $\XunitSym$ (by taking adjoints), and that they are classical points of $\XdotSym$.
\end{proof}
Note that, by Definition \ref{def:Antipode} and Frobenius law for $\XdotSym$, Equation \ref{eqn:orthogonalityMultChars} can equivalently be written as the following, stating that the multiplicative characters are a matchable family (Definition~\ref{def:matchables})  for $(\tinycomult[whitedot],\tinycounit[whitedot])$: 
\begin{equation}
\label{eqn:orthogonalityMultCharsRed}
\input{tikz/3_orthRED.tikz}
\end{equation}
Equations \ref{eqn:orthogonalityMultChars} and \ref{eqn:orthogonalityMultCharsRed} provide a summation-free version of the orthogonality of multiplicative characters of Equation \ref{eqn:orthogonalityMultCharsFamiliar} (under appropriate conditions). This leads us to the following summation-free definition of the Fourier transform, valid for any internal group in any $\dagger$-SMC.

\begin{defn}\label{def:FourierTransform}
        Let $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ be an internal group in any $\dagger$-SMC. The \textbf{Fourier transform} is defined to be the following mapping $\FourierTransformSym{\mathbb{G}}$ of states of $\SpaceG$ to co-states of $\SpaceG$:
\begin{equation}\label{eqn:FT}
\input{tikz/3_FTv3.tikz}
\end{equation} 
The \textbf{inverse Fourier transform} is defined to be the following mapping $\InverseFourierTransformSym{\mathbb{G}}$ of co-states of $\SpaceG$ to states of $\SpaceG$: 
\begin{equation}\label{eqn:InverseFT}
\input{tikz/3_inverseFTv3.tikz}
 \end{equation} 
\end{defn}

Under appropriate circumstances, the Fourier transform of Definition \ref{def:FourierTransform} takes the more familiar form of Equation \ref{eqn:DefTraditionalFT}, as shown by the following lemma and its subsequent application to $\fdHilbCategory$.

\begin{lemma}\label{lemma_FTTraditionalSMC}
Let $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ be an internal group in a $\dagger$-SMC which is distributively $\cat{CMon}$-enriched. Further assume that the multiplicative characters and the group elements of $\mathbb{G}$ are both finite, normalisable families, which form an orthogonal partition of the counits $\ZcounitSym$ and $\XcounitSym$ respectively. Then the Fourier transform of Definition \ref{eqn:FT} can be written in the following way:
\begin{equation}\label{eqn:FTSummation}
\input{tikz/3_FTv2.tikz}
\end{equation} 
Furthermore, the Inverse Fourier transform of Definition \ref{eqn:InverseFT} can be written in the following way:
\begin{equation}\label{eqn:InverseFTSummation}
\input{tikz/3_inverseFTv2.tikz}
 \end{equation} 
\end{lemma}
\begin{proof}
For the Fourier transform, use the fact that the multiplicative characters form an orthogonal partition of the counit $\XcounitSym$, as per Equation \ref{eqn:PartitionCounit}, and that they are classical states of $\tinycomult[blackdot]$, as per Equation \ref{eqn:MultCharDef}. Similar reasoning is used for the Inverse Fourier transform.
\end{proof}

In $\fdHilbCategory$, the conditions of Lemma \ref{lemma_FTTraditionalSMC} hold for abelian internal groups (but not for non-abelian ones, as the multiplicative characters fail to form a basis). The rightmost expression in equation \ref{eqn:FTSummation} can be written as follows, where we have $\ket{\chi^{-1}} = \ket{\chi} \circ \antipodeSym$ (as in Lemma \ref{lemma_OrthogonalityCharacters}):
\begin{equation*}
\frac{1}{N} \sum_\chi \bra{\chi} \braket{\chi^{-1}}{f}
\end{equation*}
The vector $\ket{f}$ can be expanded by using a resolution of the identity in terms of the group elements, courtesy of Lemma \ref{lemma_BasisResolutionPartition}:
\begin{equation*}
\sum_\chi \bra{\chi} \frac{1}{N} \sum_g \braket{\chi^{-1}}{g} \braket{g}{f}
\end{equation*}
Now we use the isomorphism $\SpaceG \isom \Ltwo{G}$ induced by the point structure, under which $f : \Ltwo{G}$ gets mapped to $\ket{f} := \sum_g \ket{g} f(g)$, to obtain:
\begin{equation*}
\sum_\chi \bra{\chi} \frac{1}{N} \sum_g \braket{\chi^{-1}}{g} f(g)
\end{equation*}
Furthermore, the multiplicative characters of $\mathbb{G}$ are, in $\fdHilbCategory$ and under the isomorphism $\SpaceG \isom \Ltwo{G}$ above, the linear extensions of the multiplicative characters of the $G$, and we can re-write the above as:
\begin{equation*}
 \sum_\chi \bra{\chi} \frac{1}{N} \sum_g \chi^{-1}(g) f(g)
\end{equation*}
Finally, we use the isomorphism $\SpaceG^\star \isom \Ltwo{G^\wedge}$ induced by the group structure,\footnote{Where we have used the fact that $\fdHilbCategory$ can be $\fdHilbCategory$-enriched, and thus that the homset $\fdHilbCategory(\SpaceG,\complexs)$ can be canonically endowed with the finite-dimensional Hilbert space structure of the space $\SpaceG^\star$ of linear functionals $\SpaceG \rightarrow \complexs$.} under which $\tilde{f}:\Ltwo{G^\wedge}$ gets mapped to $\bra{\tilde{f}} := \sum_\chi \bra{\chi} \tilde{f}(\chi)$, to finally obtain:
\begin{equation*}
\tilde{f}(\chi) = \frac{1}{N} \sum_g \chi^{-1}(g) f(g)
\end{equation*}

This is exactly the same as Equation \ref{eqn:DefTraditionalFT}, and a similar reasoning shows that in $\fdHilbCategory$ Equation \ref{eqn:InverseFTSummation} coincides with Equation \ref{eqn:DefTraditionalInverseFT}. Therefore Definition \ref{def:FourierTransform} matches the traditional definition in the case of abelian internal groups of $\fdHilbCategory$, but it remains to be seen under which circumstances and in which form its usual properties extend to internal groups in arbitrary $\dagger$-SMCs. Here we will focus on three particularly important results: the Fourier Inversion Theorem, the Convolution Theorem and Pontryagin Duality. In order to clarify their categorical formulation, we summarize the role played by each structure:
\begin{enumerate}
\item[(i)] When states $\complexs \rightarrow \SpaceG$ are identified as functions in $\Ltwo{G}$ via the basis of group elements, the monoid $(\ZmultSym,\ZunitSym)$ acts as the \emph{convolution} operation on $\Ltwo{G}$:
\begin{align}
\ZmultSym \circ \left( \sum_g  f(g) \,\ket{g} \tensor \sum_{g} f'(g)\, \ket{g} \right) &= \sum_g \left( \sum_h f(h)f'(g-h) \right)\, \ket{g} \\
&= \sum_g (f\star_G f')(g)\, \ket{g}
\end{align}

\item[(ii)] When states $\complexs \rightarrow \SpaceG$ are identified with functions in $\Ltwo{G}$ via the basis of group elements, the monoid $(\XmultSym,\XunitSym)$ acts as the \emph{pointwise multiplication} operation on $\Ltwo{G}$:
\begin{equation}
\XmultSym \circ \left( \sum_g  f(g) \,\ket{g} \tensor \sum_{g} f'(g)\, \ket{g} \right) = \sum_g f(g)f'(g)\, \ket{g} 
\end{equation}

\item[(iii)] When co-states $\SpaceG \rightarrow \complexs$ are identified with functions in $\Ltwo{G^\wedge}$ via the co-basis of multiplicative characters, the monoid\footnote{It is a co-monoid in $\fdHilbCategory$, but when acting on co-states it is a monoid.} $(\XcomultSym,\XcounitSym)$ acts as the \emph{convolution} operation on $\Ltwo{G^\wedge}$:
\begin{align}
\XcomultSym \circ \left( \sum_\chi f(\chi)\, \bra{\chi} \tensor \sum_\chi f'(\chi)\, \bra{\chi} \right) &= \sum_\chi \left( \sum_\sigma f(\sigma)f'(\chi-\sigma) \right)\, \bra{\chi} \\
&= \sum_\chi (f\star_{G^\wedge} f')(\chi)\, \bra{\chi}
\end{align}

\item[(iv)] When co-states $\SpaceG \rightarrow \complexs$ are identified with functions in $\Ltwo{G^\wedge}$ via the co-basis of multiplicative characters, the monoid. $(\ZcomultSym,\ZcounitSym)$ acts as the \emph{pointwise multiplication} operation on $\Ltwo{G^\wedge}$:
\begin{equation}
\ZcomultSym \circ \left( \sum_\chi f(\chi)\, \bra{\chi} \tensor \sum_\chi f'(\chi)\, \bra{\chi} \right) = \sum_\chi f(\chi)f'(\chi)\, \bra{\chi}
\end{equation}

\end{enumerate}

\begin{theorem}[Categorical Fourier Inversion Theorem]\label{thm_CategoricalFourierInversion}
Let $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ be an internal group in any $\dagger$-SMC $\CategoryC$. Then the Fourier transform and the Inverse Fourier transform from Definition \ref{def:FourierTransform} are mutually inverse bijections between states and co-states of $\SpaceG$.
\end{theorem}
\begin{proof}
The following shows that $\InverseFourierTransformSym{\mathbb{G}} \circ \FourierTransformSym{\mathbb{G}} = \idm{\mathcal{G}}$, by using the Definition \ref{def:Antipode} for the antipode and Lemma \ref{lemma_AntipodeInverse}:
\begin{equation}\label{eqn:FTInversionThm}
\input{tikz/3_FTInversionThm.tikz}
\end{equation} 
A similar proof holds for $\FourierTransformSym{\mathbb{G}} \circ \InverseFourierTransformSym{\mathbb{G}} = \idm{\mathcal{G}}$, by expanding the antipode in terms of its definition and using Frobenius law (once per colour, exactly like in the proof of Lemma  \ref{lemma_AntipodeInverse}).
\end{proof}

\begin{theorem}[Categorical Convolution Theorem] \label{thm_categoricalConvolutionTheorem}
Let $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ be an internal group in any $\dagger$-SMC $\CategoryC$. Then the Fourier transform is a monoid homomorphism:
\begin{equation}
\FourierTransformSym{\mathbb{G}} : (\,\SpaceG,\ZmultSym,\ZunitSym) \longrightarrow  (\,\SpaceG,\tinycomult[whitedot],\tinycounit[whitedot])
\end{equation}
\end{theorem}
\begin{proof}
That $\mathcal{F}_{\mathbb{G}}$ preserves the unit $\tinyunit[whitedot]$ is obvious by the unitality of \tinymult[whitedot]. Using associativity, followed by one application of Frobenius Law, we get the desired:
\begin{equation}\label{eqn:ConvolutionThmProof}
\input{tikz/3_ConvolutionThmProof.tikz}
\end{equation} 
\end{proof}

\begin{theorem}[Categorical Pontryagin Duality]\label{thm_CategoricalPontryaginDuality}
Let $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ be an internal group in a $\dagger$-SMC $\CategoryC$. Then the Fourier transform $\FourierTransformSym{\mathbb{G}}$ is a bijection between states of $\mathbb{G}$ and states of $\mathbb{G}^\wedge$, which is furthermore canonical in the sense that:
\begin{equation}
^{(\varphi^\wedge)}M \cdot \FourierTransformSym{\mathbb{H}} \cdot _{\varphi\!}M = \FourierTransformSym{\mathbb{G}}
\end{equation}
where $\varphi: \mathbb{G} \rightarrow \mathbb{H}$ is any unitary isomorphism of internal groups in $\CategoryC$, for  $\mathbb{H} = (\,\SpaceH,\dotonly{altwhitedot},\dotonly{altblackdot})$ any other internal group of $\CategoryC$. We have defined the following:
\begin{enumerate}
\item[(i)] $\varphi^\wedge := \varphi$ is an isomorphism of internal groups $\mathbb{H}^\wedge \rightarrow \mathbb{G}^\wedge$ in $\cat{C^{op}}$
\item[(ii)] $_\varphi M$ as the map sending state $\ket{f} : \tensorUnit \rightarrow \SpaceG$ to state $\varphi \circ \ket{f}: I \rightarrow \SpaceH$
\item[(iii)] $^{(\varphi^\wedge)} M$ as the map sending co-state $\bra{f} : \SpaceH \rightarrow I$ (a state in $\cat{C^{op}}$) to co-state $\bra{f}\circ \varphi : \SpaceG \rightarrow I$
\end{enumerate}
\end{theorem}
\begin{proof}
The bijection is proven by Theorem \ref{thm_CategoricalFourierInversion}, so all we have to show is canonicity:
\begin{equation}\label{eqn:PontDualityCanonProof}
\input{tikz/3_PontDualityCanonProof.tikz}
\end{equation} 
The first equality follows from the fact that $\varphi$ is a morphism of internal groups. The second equality follows from the (easy to check) fact that, if $\varphi$ is a unitary isomorphism $\varphi: \mathbb{G} \rightarrow \mathbb{H}$, then $\varphi^\dagger$ is a unitary isomorphism $\varphi^\dagger: \mathbb{H} \rightarrow \mathbb{G}$, and hence we have:
\begin{equation}
\tinycounit[altwhitedot] \circ \varphi = \left(\varphi^\dagger \circ\tinyunit[altwhitedot] \right)^\dagger = \left(  \ZunitSym\right)^\dagger = \ZcounitSym
\end{equation}
\end{proof}
In $\fdHilbCategory$ (with abelian internal groups),~\eqref{eqn:PontDualityCanonProof} takes the form of~\eqref{eqn:FTcanonicity}. To conclude, we provide a categorical definition of Fourier matrices, which helps to frame the difference between them and the Fourier transform.

\begin{defn}
\label{def:CategoricalFmat}
Let $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ be an internal group in a $\dagger$-SMC $\CategoryC$. A \textbf{Fourier~matrix} is defined to be a co-monoid isomorphism $F:(\,\tinycomult[blackdot],\tinycounit[blackdot]) \rightarrow (\,\ZcomultSym,\ZcounitSym)$ which is furthermore a monoid isomorphism $F:(\,\timemultSym,\timeunitSym) \rightarrow (\,\tinymult[blackdot],\tinyunit[blackdot])$. We write it as:
\begin{equation}
\begin{pic}
\node [morphism] (h) at (0,0) {$F$};
\draw (0,-1) to (h.south);
\draw (0,1) to (h.north);
\end{pic}
\end{equation}
%s.t. $h^\dagger$ is also a monoid isomorphism $h^\dagger:(\;\timemultSym,\timeunitSym) %\rightarrow (\;\timematchSym,\timematchunitSym)$. 
\end{defn}
Definition \ref{def:CategoricalFmat} may look cryptic at first, but it is in fact quite natural as we clarify in the following remark.
\begin{remark}\label{rmrk_CategoricalFmat}
A co-monoid isomorphism $F:(\XcomultSym,\XcounitSym) \rightarrow (\,\ZcomultSym,\ZcounitSym)$ is an isomorphism $F: \SpaceG \rightarrow \SpaceG$ which satisfies:
\begin{align}
    \ZcomultSym \cdot F &= \left( F \tensor F \right) \cdot \tinycomult[blackdot] \\
    \ZcounitSym \cdot F &= \tinycounit[blackdot]
\end{align}
and in particular it maps $\XdotSym$-classical states to $\ZdotSym$-classical states (since it is an isomorphism, it is a bijection between the classical states of the two comonoids). The requirement that $F$ is furthermore a monoid isomorphism $F:(\,\timemultSym,\timeunitSym) \rightarrow (\,\XmultSym,\XunitSym)$ amounts to the requirement that:
\begin{align}
    F \circ \ZmultSym &= \XmultSym \circ \left( F \tensor F \right)\\
    F \circ \ZunitSym &= \XunitSym
\end{align}
and in particular, as a bijection of classical states, $F$ is a group isomorphism from the group given by $(\ZmultSym,\ZunitSym)$ acting on $\ZdotSym$-classical states to the group given by $(\XmultSym,\XunitSym)$ acting on $\ZdotSym$-classical states.
\end{remark}

In $\fdHilbCategory$ (with abelian internal groups), Definition \ref{def:CategoricalFmat} yields the usual Fourier matrices. Indeed $F$ corresponds to an isomorphism $\Psi: G \rightarrow G^\wedge$ (by considering its action on classical states): the linear isomorphism $F$ is itself the Discrete Fourier transform of Equation \ref{eqn:FTDefDFT} (where $\SpaceG$ is identified with $\Ltwo{G}$ and $\Ltwo{G^\wedge}$ using $\XdotSym$ and $\ZdotSym$ respectively), and the matrix of $F$ in the basis defined by $\XdotSym$ is the Fourier matrix of Equation \ref{eqn:HadamardMatrixDef}.

\subsection{The Fourier transform in the category $\fRelCategory$}
\label{section_RelFT}


The abstract correspondence between strongly complementary observables and Fourier transforms in Section \ref{section_AbelianGroups_FourierTransform} means that a characterization of strongly complementary observables in any $\dagger$-SMC allows for the definition of a Fourier transform in that category.  In this section, we apply this idea to $\fRelCategory$, the category of finite sets and relations (Example~\ref{ex:smcs}). One can find more details on \cat{FRel} as a QPT in Section~\ref{sec:qalgrel}. In this setting, the relevant classical structures are classified by abelian groupoids, in a sense made clear by Theorem \ref{thm_classicalStructuresRel} below. Also recall that the monoidal identity is given by the singleton, i.e. $I = \{\star\}$. Please note that in $\fRelCategory$ the scalars are the booleans $\{\bot,\top\}$, and $\top = \idm{\tensorUnit}: I \rightarrow I$ is the only invertible scalar. As a consequence, all $\dagger$-qSFAs are automatically $\dagger$-SFAs (and thus all $\dagger$-qSCFAs are in fact classical structures). 

\begin{defn}
A \textbf{(finite) abelian groupoid} on some finite set $A$ is any finite family $(G_\lambda,+_\lambda,0_\lambda)_{\lambda \in \Lambda}$ of finite abelian groups such that $(G_\lambda)_{\lambda \in \Lambda}$ is a finite partition of $A$ into disjoint subsets. We denote one such groupoid by $\oplus_{\lambda \in \Lambda} G_\lambda$, leaving the groups' structures understood.
\end{defn}

\begin{theorem}\label{thm_classicalStructuresRel}
Let $\ZdotSym$ be a classical structure in $\fRelCategory$ on a finite set $X$. Then there exists a (unique) abelian groupoid $\oplus_{\lambda \in \Lambda} G_\lambda$ on $A$ such that, for all $a,b \in A$:
\begin{equation}
    \ZmultSym \circ \left( \{a\} \times \{b\} \right) = 
    \begin{cases}
        \{ a +_\lambda b\} \text{ if for some } \lambda \in \Lambda \text{ we have } a,b \in G_\lambda \\
        \emptyset \text{ otherwise}
    \end{cases}
\end{equation}
Furthermore, each abelian groupoid defines a unique classical structure in this way. The classical states of the co-monoid fragment $(\ZcomultSym,\ZcounitSym)$ are the family $(G_\lambda)_{\lambda \in \Lambda}$, which is also a matching family for the monoid fragment $(\ZmultSym,\ZunitSym)$.\footnote{Recall that the states $I \rightarrow A$ of a finite set $A$ in $\fRelCategory$ are exactly the subsets of $A$.}
\end{theorem}
\begin{proof}
Proven by Pavlovic~\cite{pavlovic2009quantum}, and extended to the case of non-commutative $\dagger$-SFAs / non-abelian groupoids by Heunen et al.~\cite{heunen-relFrob}.
\end{proof}

Evans et al. show that the groupoids corresponding to complementary / strongly complementary classical structures take a particularly nice form:

\begin{theorem}[\cite{evans2009classifying}]\label{thm_StrongComplementarityRel}
Let $\oplus_{\gamma \in \Gamma} H_\gamma$ and $\oplus_{\lambda \in \Lambda} G_\lambda$ be abelian groupoids on some finite set $A$, and let $\XdotSym$ and $\ZdotSym$ be the corresponding classical structures on $A$ in $\fRelCategory$. Then $\XdotSym$ and $\ZdotSym$ are strongly complementary if and only if: 
\begin{enumerate}
\item[(i)] there is a finite abelian group $H$ such that for all $\gamma \in \Gamma$ we have $H_\gamma \isom H$ as groups.
\item[(ii)] there is a finite abelian group $G$ such that for all $\lambda \in \Lambda$ we have $G_\lambda \isom G$ as groups.
\item[(iii)] for each $(\lambda,\gamma) \in \Lambda \times \Gamma$, the intersection $G_\lambda \cap H_\gamma$ is a singleton. 
\end{enumerate}
\end{theorem}

In particular, this means that $\Lambda \isom H$ and $\Gamma \isom G$ as sets: as a consequence, we will write abelian groupoids corresponding to strongly complementary classical structures as $\oplus^{|G|}H$ and $\oplus^{|H|}G$, leaving the indexing of the partitions as understood. We will also implicitly label the elements of the underlying set $A$ as:
\begin{equation}
A \isom \suchthat{(h,g)}{h \in H \text{ and } g \in G}
\end{equation}

In $\fdHilbCategory$, strongly complementary pairs of classical structures have the same number of classical states, and their monoid fragments act on each other's classical states as isomorphic groups $G$ and $G^\wedge$. As a consequence, it is possible to fix isomorphisms between the two groups and construct Fourier matrices as per Definition \ref{def:CategoricalFmat}. In $\fRelCategory$, on the other hand, Fourier matrices only exist in very special cases.

\begin{theorem} Let $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ be an abelian internal group in $\fRelCategory$, and let $Z = \oplus^{|G|}H$ and $X = \oplus^{|H|}G$ be the groupoids corresponding to the $\XdotSym$ and $\ZdotSym$ classical structures respectively. Then $(\ZmultSym,\ZunitSym)$ acts on the $\XdotSym$-classical states $(H_g)_{g \in G}$ as the finite abelian group $G$, and $(\XmultSym,\XunitSym)$ acts on the $\ZdotSym$-classical states $(G_h)_{h \in H}$ as the finite abelian group $H$.
\end{theorem}
\begin{proof}
It is sufficient to prove for $(\ZmultSym,\ZunitSym)$ acting on the $\XdotSym$-classical states. Indeed we have that $\ZunitSym = H_0$ is a $\XdotSym$-classical state by strong complementarity, and that:
\begin{align}
\ZmultSym \circ \left( \ket{H_g} \times \ket{H_{g'}} \right) &= \bigcup_{h,h' \in H} \ZmultSym \circ \left( \{(h,g)\} \times \{(h',g')\} \right) \\&= \bigcup_{h \in H} \{(h,g+g')\} = \ket{H_{g+g'}}
\end{align}
\end{proof}

\begin{example}
The groupoids $Z = \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2$ and $X = \mathbb{Z}_3 \oplus \mathbb{Z}_3$ correspond to strongly complementary structures, call them $\XdotSym$ and $\ZdotSym$ respectively, on a 6-element set $A$. We can label the elements of $A$ as:
\begin{equation}
A \isom \{(h,g)\mbox{ s.t. }h \in \integersMod{2} \text{ and } g \in \integersMod{3}\}
\end{equation}
The classical states of $\XdotSym$ are the 3 subsets $(\integersMod{2},g)$ for $g \in \integersMod{3}$, while the classical states of $\ZdotSym$ are the 2 subsets $(h,\integersMod{3})$ for $h \in \integersMod{2}$. The monoid $(\ZmultSym,\ZunitSym)$ acts on the $\XdotSym$-classical states as the group $\integersMod{3}$, while the monoid $(\XmultSym,\XunitSym)$ acts on the $\ZdotSym$-classical states as the group $\integersMod{2}$.
\end{example}

\begin{corollary}
Let $\mathbb{G} = (\,A,\ZdotSym,\XdotSym)$ be an abelian internal group in $\cat{FRel}$. Fourier matrices for $\mathbb{G}$ exist if and only if the two groups $G$ and $H$ are isomorphic.
\end{corollary}
\begin{proof}
By Remark \ref{rmrk_CategoricalFmat}, a Fourier matrix gives a group isomorphism between the groups given by the action of the two monoid fragments on each other's classical states: in this case, the existence of a Fourier matrix forces $G$ and $H$ to be isomorphic. On the other hand, if $\Psi: G \rightarrow H$ is a group isomorphism, one could define a map $M_\Psi: A \rightarrow A$ as follows:
\begin{equation}
M_\Psi := \bigcup_{g \in G} \ket{G_{\Psi(g)}}\bra{H_g}  
\end{equation}
This satisfies the monoid and comonoid homomorphism requirements from Definition~\ref{def:CategoricalFmat}, but is not an isomorphism in $\fRelCategory$. To get an isomorphism, and prove the existence of a relevant Fourier matrix in $\fRelCategory$, we consider a new map $t: A \rightarrow A$, which we give in the form of a relation $t \subseteq A \times A$:
\begin{equation}
t := \suchthat{\left((h,g),(\Psi g,\Psi^{-1}h)\right)}{h \in H \text{ and } g \in G}
\end{equation}
\end{proof}

The Fourier transform as given by Definition \ref{def:FourierTransform} is valid in any $\dagger$-SMC with a pair of strongly complementary classical structures, and in particular it holds in $\fRelCategory$. The more traditional formulation given by Lemma \ref{lemma_FTTraditionalSMC}, which allows one to see the Fourier transform as a canonical isomorphism $\Ltwo{G} \isom \Ltwo{G^\wedge}$, is based on the assumption that the group elements of an abelian internal group $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ in $\fdHilbCategory$ form a basis, giving $\Hom_{\fdHilbCategory}(\complexs,\SpaceG)$ the Hilbert space structure of $\Ltwo{G}$ in a natural way, and that the multiplicative characters form a co-basis, giving $\Hom_{\fdHilbCategory}(\complexs,\SpaceG)$ the Hilbert space structure of $\Ltwo{G^\wedge}$ in a natural way.

In $\fRelCategory$, however, the assumptions of Lemma \ref{lemma_FTTraditionalSMC} only hold in one, somewhat trivial case. The classical states of a classical structure in $\fRelCategory$ are always a finite, orthogonal and normalisable family, and $\fRelCategory$ is distributively $\cat{CMon}$-enriched as required. However, as Lemma \ref{thm_partitionIdentityRel} below notes, there is a unique classical structure on any finite set $A$ with classical states forming the resolution of the identity, and the only abelian internal group in $\fRelCategory$ satisfying the assumptions of Lemma \ref{lemma_FTTraditionalSMC} is the one on the tensor unit $\{\star\}$ of $\fRelCategory$.

\begin{lemma}
\label{thm_partitionIdentityRel}
Let $\ZdotSym$ be a classical structure on a finite set $A$ in $\fRelCategory$, and let $Z$ be the associated abelian groupoid. The classical points of $\XdotSym$ form an orthogonal resolution of the identity if and only if the abelian groupoid is discrete, i.e.  $Z=\bigoplus^{A}\mathbb{Z}_1$. Furthermore, if $(\XdotSym,\ZdotSym)$ is a strongly complementary pair on $A$, with $\XdotSym$ associated to an abelian groupoid $Z=\bigoplus^{A}\mathbb{Z}_1$, then the abelian groupoid associated with $\ZdotSym$ is in fact a group, in the form $X = G$ for some finite abelian group $G = (A,+,0)$ on the element set $A$. As a consequence, the only abelian internal group in $\fRelCategory$ satisfying the assumptions of Lemma \ref{lemma_FTTraditionalSMC} is the (unique) abelian internal group on the tensor unit $\{\star\}$.
\end{lemma}
\begin{proof} 
In $\RelCategory$ the scalars are $0$ or $1$ and summation is given by set union.  Thus a resolution of the identity must satisfy the following equation, where each $\chi$ is a classical state:
  \begin{equation}\label{eqn:MultCharResolutionIdRel}
    \input{tikz/3_multcharresIDRel.tikz}
  \end{equation}
In the specific case of $Z=\bigoplus^{A}\mathbb{Z}_1$, we have that classical points are in the form $\chi = \{(\star,a)\}$ and~\eqref{eqn:MultCharResolutionIdRel} reads
\begin{align}
\bigcup_{a \in A} \{(\star, a)\}\circ\{(a,\star)\} 
= \bigcup_{a \in A} \{(a, a)\} = \idm{A}.
\end{align}

When $Z$ is of the generic form $Z = \bigoplus_{\lambda \in \Lambda} G_\lambda$, the classical points are in the form $\chi = G_\lambda$, and~\eqref{eqn:MultCharResolutionIdRel} reads
\begin{align}
\bigcup_{\lambda \in \Lambda} \{(\star, g')|g': G_\lambda\}\circ\{(g,\star)|g: G_\lambda\} =  \bigcup_{\lambda \in \Lambda} \{(g, g')|g,g': G_\lambda\},
\end{align}
which cannot be the identity if $|G_h|>1$. Therefore the unique classical structures $\ZdotSym$ with classical states forming an orthogonal resolution of the identity are the ones associated to discrete abelian groupoids, in the form $Z=\bigoplus^{A}\mathbb{Z}_1$. If $\XdotSym$ is one such classical structure, and $\ZdotSym$ is strongly complementary to it, then it follows immediately from Theorem \ref{thm_StrongComplementarityRel}, and subsequent remarks, that the abelian groupoid $X$ associated to $\ZdotSym$ must be in fact an abelian group, in the form $X = \oplus^{\integersMod{1}} G$, where $G$ is some finite abelian group with element set $A$. But to satisfy the assumptions of Lemma \ref{lemma_FTTraditionalSMC}, we must have that $X$ is also a discrete groupoid, which forces $G \isom \integersMod{1}$ and $A \isom \{\star\}$.
\end{proof}

So there is no direct parallel in $\fRelCategory$ of the $\fdHilbCategory$ view that the Fourier transform is a canonical isomorphism $\Ltwo{G} \isom \Ltwo{G^\wedge}$, or of its traditional formulation from Equation \ref{eqn:DefTraditionalFT}. At first sight, this seems to be because the classical states of the two structures of a generic abelian internal group need not form a basis. The question then naturally arises whether restricting our attention to some subclass of states (e.g. those which are linear combinations of the classical states) would lead to a canonical isomorphism similar to the $\fdHilbCategory$ one. Theorem \ref{thm_NoCanonicalIsomRel} below answers this question negatively.

Define the \textbf{span} $\langle s_j \rangle_{j \in J}$ of a family of states $s_j \subseteq A$ to be the set of all states $r \subseteq A$ which can be obtained as the union $r = \cup_{j \in I} s_j$ of some subfamily $(s_j)_{j \in I\subseteq J}$. If the $(s_j)_{j \in J}$ are pairwise disjoint, then the states $r \in \langle s_j \rangle_{j \in J}$ are exactly those that descend to boolean functions over the set $\suchthat{s_j}{j \in J}$:
\begin{align}\label{eqn:spanBooleanFunctions}
    r \in \langle s_j \rangle_{j \in J} \;\; \mapsto \;\; \left(j \mapsto \braket{s_j}{r}\right) \in \mathbb{B}[J]
\end{align}
where we denoted by $\ket{s} : I \rightarrow A$ the state corresponding to subset $s \subseteq A$. Now consider an abelian internal group $\mathbb{G} = (A,\XdotSym,\ZdotSym)$ in $\fRelCategory$, and let $Z = \bigoplus^{|G|}H$ and $X = \bigoplus^{|H|}G$ be the abelian groupoids corresponding to $\XdotSym$ and $\ZdotSym$ respectively. Then $\langle H_g \rangle_{g\in G}$, seen as the set $\{0,1\}^G$ of boolean functions on $\suchthat{H_g}{g\in G}$, plays the role in $\RelCategory$ that $\Ltwo{G}$ played in $\fdHilbCategory$, and similarly $\langle G_h \rangle_{h\in H}$, seen as $\{0,1\}^H$, is the analogue of $\Ltwo{H}$ (and takes the place $\Ltwo{G^\wedge}$ had in $\fdHilbCategory$). 

\begin{theorem}\label{thm_NoCanonicalIsomRel}
Let $\mathbb{G} = (A,\XdotSym,\ZdotSym)$ be an abelian internal group in $\fRelCategory$, and let $Z = \bigoplus^{|G|}H$ and $X = \bigoplus^{|H|}G$ be the abelian groupoids corresponding to $\XdotSym$ and $\ZdotSym$ respectively. Then $\langle H_g \rangle_{g \in G} \cap \langle G_h \rangle_{h \in H} = \{\emptyset, A\}$. In particular, under the correspondence of~\eqref{eqn:spanBooleanFunctions},  the Fourier transform of $\fRelCategory$ does not restrict to an isomorphism $\{\bot,\top\}^G \isom \{\bot,\top\}^H$, nor can it be restricted to an isomorphism $S_G \isom S_H$ for any $S_G \subseteq \{\bot,\top\}^G$ and $S_H \subseteq\{\bot,\top\}^H$ containing non-constant functions. 
\end{theorem}
\begin{proof}
Let $r \in \langle H_g \rangle_{g\in G} \cap \langle G_h \rangle_{h \in H}$, then $r$ is either the empty set or it contains some $(h',g') \in A$. But if $(h',g') \in r$, then for all $g \in G$ we have $(h',g) \in r$ (because $r \in \langle G_h \rangle_{h\in H}$), and then for any $g \in G$ we have that for all $h \in H$ $(h,g) \in r$ (because  $r \in \langle H_g \rangle_{g \in G}$). Thus for all $g \in G$ and $h \in H$ we have $(h,g) \in r$, i.e. $r = A$. The state $r = \emptyset$ in $\langle H_g \rangle_{g\in G} \cap \langle G_h \rangle_{h \in H}$ corresponds the constant $\bot$ function in $\{\bot,\top\}^H$ and in $\{\bot,\top\}^G$ (under Equation \ref{eqn:spanBooleanFunctions}), while the state $r = A$ corresponds to the constant $\top$ function. The Fourier transform maps the constant $\bot$ function of $\{\bot,\top\}^G$ to the constant $\bot$ function of $\{\bot,\top\}^H$, and similarly with the constant $\top$ functions. However, if $r \in \langle H_g \rangle_{g\in G}$ is neither empty nor the whole of $A$, i.e. if it corresponds to a non-constant function in $\{\bot,\top\}^G$, then its Fourier transform does not lie in the span $\langle G_h \rangle_{h \in H}$, and thus cannot be seen as a function in $\{\bot,\top\}^H$.
\end{proof}

As a consequence of Theorem \ref{thm_NoCanonicalIsomRel}, the best analogue in $\fRelCategory$ of the statement that the Fourier transform is a canonical isomorphism $\Ltwo{G} \isom \Ltwo{G^\wedge}$ in $\fdHilbCategory$ is the trivial statement that the Fourier transform in $\fRelCategory$ is an isomorphism $\{\bot_G,\top_G\} \isom \{\bot_H,\top_H\}$ between the constant functions of $\{\bot,\top\}^G$ and of $\{\bot,\top\}^H$.

To summarise, in $\fdHilbCategory$ we have the following views of the Fourier transform for abelian internal groups:
\begin{enumerate}
\item[1.] As quantum Fourier transform, implemented by application of a Fourier matrix (subject to a non-canonical choice of isomorphism $G \isom G^\wedge$) followed by operations in the computational basis.
\item[2.] In the sense of Pontryagin duality, as a canonical isomorphism $\Ltwo{G} \isom \Ltwo{G^\wedge}$.
\item[3.] Again as quantum Fourier transform, but implemented by measuring in a basis that is strongly complementary to the computational basis.
\end{enumerate}

In $\cat{FRel}$, on the other hand, things are very different:
\begin{enumerate}
\item[1.] Except in the case where $Z = \bigoplus^{|G|}G$ and $X = \bigoplus^{|G|}G$ (isomorphic, but different), no Fourier matrix can exist in $\RelCategory$.
\item[2.] The Fourier transform does not give, in $\RelCategory$, an isomorphism $\{0,1\}^G \isom \{0,1\}^H$ between the spaces of boolean-valued functions on the group elements / multiplicative characters.
\item[3.] The operational definition based on strong complementarity, however, is still valid in $\fRelCategory$. 
\end{enumerate}

To conclude, the following examples give explicit examples of quantum Fourier transforms in $\RelCategory$.

\begin{example}
Take $G=\integersMod{2}=\{0,1\}$, $H=\integersMod{1}=\{\star\}$, $Z = G = \{ 0_\star,1_\star \}$ and $X=H\oplus H = \{ \star_0,\star_1 \}$. The computational basis is the family $(H_g)_{g:G}$ of copyable points for $X$, i.e. $H_0 = \{(\star,0)\}$ and $H_1 = \{(\star,1)\}$. The character family used for the quantum Fourier transform consists 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 the measurement in the character family will be trivial.
\end{example}

\begin{example}
Take $G=\integersMod{2}=\{0,1\}$, $H=\integersMod{2}=\{a,b\}$, $Z = G \oplus G = \{ 0_a,1_a,0_b,1_b\}$ and $X= H \oplus H = \{ a_0, b_0, a_1, b_1 \}$. The computational \inlineQuote{basis} is the family $(H_g)_{g:G}$ of classical states for $X$, i.e. $H_0 = \{(a,0),(b,0)\}$ and $H_1 = \{(a,1),(b,1)\}$. The character family used for the quantum Fourier transform is the family $(G_h)_{h:H}$ of classical states for $Z$, i.e. $G_a = \{(a,0),(a,1)\}$ and $G_b = \{(b,0),(b,1)\}$.
\end{example}

It is part of the process theoretic programme that the operational features of quantum theory should be modelled categorically, and that any category sharing features with $\fdHilbCategory$ should be considered, at least in principle, as a potential (toy?) model of quantum mechanics. The category $\fRelCategory$ is an example of one such model. We have shown that Fourier matrices do not generalise well outside $\fdHilbCategory$, and certainly fail to implement a quantum Fourier transform in $\RelCategory$, but that our treatment of Fourier theory based on strong complementarity goes through unharmed. As a consequence, categorical quantum algorithms where the quantum Fourier transform is formulated using strong complementarity will straightforwardly generalise to $\RelCategory$ and other categories. We take this to be an indication that our perspective on the quantum Fourier transform is conceptually sound and operationally advantageous.

\subsection{Non-abelian Fourier transform}
\label{section_NonAbelianFourierTransform}

In $\fdHilbCategory$, abelian internal groups satisfy the assumptions of Lemma \ref{lemma_FTTraditionalSMC}, and the corresponding Fourier transform can be seen, via enrichment, as a canonical isomorphism of $\LtwoSym$-spaces $\Ltwo{G} \isom \Ltwo{G^\wedge}$. Non-abelian internal groups in $\fdHilbCategory$, however, fail those assumptions, as the classical states of the group structure never form a basis. However, it is a consequence of the Peter-Weyl theorem that the irreducible representations can be used to obtain a resolution of the identity. We will introduce matrix algebras in a QPT in order to handle these multi-dimensional representations. This then allows us, the rest of the section, to review the generalisation of our treatment in the previous sections as is presented by Gogioso in~\cite{gogioso2015fourier}. The work presented there allows full-blown representation theory and concludes with a formulation of non-abelian Fourier transform connected with the Gelfand--Naimark--Segal construction.

First, let's see why non-abelian internal groups in $\fdHilbCategory$ cannot satisfy the assumptions of Lemma \ref{lemma_FTTraditionalSMC}. The classical states of the point structure form an orthogonal basis, and are the elements of some non-abelian group $G$. The classical states of the group structures are the multiplicative characters of $G$: they are always orthogonal and normalisable, but as long as we show that there are less of them than the number of elements of $G$, we can conclude that they won't form a co-basis as would be required by Lemma \ref{lemma_FTTraditionalSMC}. But the multiplicative characters of a group $G$ are the same as the multiplicative character of its abelianization $G'$, which is always strictly smaller than $G$ (at least by a factor of 2). Therefore there are always strictly less multiplicative characters than group elements for a non-abelian internal group in $\fdHilbCategory$, and hence the assumptions of Lemma \ref{lemma_FTTraditionalSMC} always fail. It turns out that this is not restricted to $\fdHilbCategory$:
\begin{theorem}
Let $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ be an internal group in a $\dagger$-SMC $\CategoryC$. If the classical states of $\ZdotSym$ form a basis, then $\mathbb{G}$ is necessarily an abelian internal group.
\end{theorem}
\begin{proof}
All we have to show is that $\ZmultSym = \ZmultSym \circ s_{\SpaceG\SpaceG}$, where $s_{\SpaceG\SpaceG}$ is the braiding operator. Equivalently, it is enough to show that $\ZcomultSym = s_{\SpaceG\SpaceG} \circ \ZcomultSym$. But indeed for any classical state $\ket{\chi}$ of $\ZdotSym$ we have $\ZcomultSym \circ \ket{\chi} = \ket{\chi} \tensor \ket{\chi} = s_{\SpaceG\SpaceG} \circ \ket{\chi} \tensor \ket{\chi} =   s_{\SpaceG\SpaceG} \circ \ZcomultSym \circ \ket{\chi}$. As we have assumed that the classical states form a basis, this completes the proof.
\end{proof}

To deal with the non-abelian case, we will introduce matrix algebras into QPTs. Recall that Hilbert spaces $\SpaceH_n$ of dimension $n$ are isomorphic to $\mathbb{C}^n$. This means that in $\cat{FHilb}$  the name~\eqref{eq:cj} of a morphism is an $n\times n$ matrix: 
\begin{equation}
\begin{pic}[xscale=\tikzxscale, yscale=\tikzyscale]
\node at (0,0) {$\name{f}$};
\node (L) [morphism, xscale=2.5] at (0,0) {};
\draw [<-]([xshift=-1cm] L.north) to ([xshift=-1cm, yshift=1.5cm] L) node [above] {$\mathbb{C}^n$};
\draw [->]([xshift=1cm] L.north) to ([xshift=1cm, yshift=1.5cm] L) node [above] {$\mathbb{C} ^n$};
\end{pic}
\quad:=\quad\hspace{-5pt}
\begin{pic}[xscale=\tikzxscale, yscale=-1*\tikzyscale]
\draw [arrow=0.5](0,-1.5) node [above] {$\mathbb{C} ^n$} to (0,0) to [out=up, in=\swangle] (0.7,1);
\draw [<-](1.4,0) to [out=up, in=\seangle] (0.7,1);
\node [] at (0.7,1) {};
\node (L) [morphism, anchor=south] at (1.4,0) {$f$};
\draw (L.north) to (1.4,-1.5) node [above] {$\mathbb{C} ^n$};
\end{pic}
\end{equation}
This motivates us, following Vicary~\cite{vicary-tqa}, to build up a $\dagger$-Frobenius algebra (a matrix algebra) in an arbitrary QPT using caps and cups. The monoid, unit, comonoid, and counit of this algebra are given as follows:
\begin{equation}
\label{eq:matrixFrob}
\input{tikz/4_matrixmulFrob.tikz}
\end{equation}

One-dimensional representations of a monoid $(\SpaceG, \ZmultSym, \ZunitSym)$ are morphisms into the trivial monoid on $\SpaceH=I$. In general though, multidimensional representations are morphisms into the monoid from~\eqref{eq:matrixFrob}.

\begin{defn}\label{def:Reps}
        The \textbf{representations} of a monoid $(\, \SpaceG , \ZmultSym,\ZunitSym)$ in a compact-closed $\dagger$-SMC are the morphisms $\rho : \SpaceG \rightarrow \SpaceH \tensor \SpaceH^\star$ satisfying the first two equations in~\eqref{eqn:RepsDef}. The representations of an internal groups $(\, \SpaceG , \ZdotSym,\XdotSym)$ are the representations of the monoid $(\, \SpaceG , \ZmultSym,\ZunitSym)$ part of the internal group. A representation of an internal group is \textbf{unitary} if it satisfies the third as well. A representation is \textbf{isometric} if it is an isometry.
        \begin{equation}\label{eqn:RepsDef}
\input{tikz/4_repsdef1.tikz}
        \end{equation}
\end{defn}

\begin{defn}\label{def:Characters}
        The \textbf{character} associated with a representation $\rho: \SpaceG \rightarrow \SpaceH \tensor \SpaceH^\star$ of a monoid / internal group in a compact-closed $\dagger$-SMC is the morphism $\chi_\rho : \SpaceG \rightarrow \tensorUnit$ defined by Equation \ref{eqn:CharacterDef}. In the case of internal groups, a character $\chi_\rho$ is \textbf{unitary} if the representation $\rho$ is. 
        \begin{equation}\label{eqn:CharacterDef}
\input{tikz/4_charDef.tikz}
        \end{equation}
\end{defn}

These notions clearly generalize those given in Section~\ref{section_AbelianGroups_FourierTransform}. The orthogonality of representations and characters by these abstract definitions is categorically proven by Gogioso in~\cite{gogioso2015fourier}. This allows a generalization of the Abelian Fourier transform from the previous section
\begin{lemma}\label{lemma_FTTraditionalSMC2}
Let $\mathbb{G} = (\,\SpaceG,\ZdotSym,\XdotSym)$ be an internal group in a compact-closed $\dagger$-SMC which is distributively $\cat{CMon}$-enriched. Further assume that $(\rho)_{\rho \in \mathcal{R}}$ is a finite, normalisable family of representations of $\mathbb{G}$ (with normalisation factors $(N_\rho)_{\rho \in \mathcal{R}}$), which forms an orthogonal resolution of the identity. Then the Fourier transform of Definition~\ref{eqn:FT} can be written in the following way:
\begin{equation}\label{eqn:FTv2nonabelian}
\input{tikz/4_FTnonAb.tikz}
\end{equation} 
\end{lemma}
\begin{proof}
Given in~\cite{gogioso2015fourier}. It proceeds along the same lines as that of the abelian version given here.
\end{proof}

Gogioso extends this perspective to provide a categorical version of the Gelfand-Naimark theorem~\cite{gogioso2015fourier}.


\subsection{Measurements and representation theory}
\label{sec:measrep}
We have seen that the representations of an abelian internal group can form a basis, and, in particular, that they are the dagger of classical states of one half of a strongly complementary pair of classical structures \scpair. Indeed, even in the non-abelian case, representations of larger than one dimension will also be orthogonal and form a resolution of the identity~\cite{gogioso2015fourier}. If we consider the group elements as embedded in classical states of $\dotonly{whitedot}$ then the group's representations are effects for the $\dotonly{blackdot}$ classical structure. By the QPT Born rule (Definition~\ref{def:bornrule}) we now have a full and abstract grasp on what it means to measure in the ``representation basis" or ``Fourier basis", i.e. composing with a representation's effect acts as a post-selected measurement of that outcome in the ``representation basis." We clarify the results in this section that will appear in our characterization of quantum algorithms with Figure~\ref{fig:ft}. The generalized Fourier matrix will play a particularly important role in characterizing quantum-like algorithms in process theories.  Indeed the quantum Fourier transform algorithm, when implemented in a QPT, acts like a Fourier matrix (Figure~\ref{fig:ft}).

\newpage

\begin{figure}[H]
\caption[Summary of internal groups, representations, and the Fourier transform in QPTs.]{Summary of the results of Section~\ref{sec:strcomplFT} as they pertain to the analysis of quantum algorithms in the following sections. These constructions are with reference to an internal group $\mathbb{G}= (\SpaceG,\ZdotSym,\XdotSym)$ in a QPT (Definition~\ref{def:AbClassicalGroup}).
}
\label{fig:ft}
{\renewcommand{\arraystretch}{2}\small
\begin{tabulary}{\linewidth}{|p{7cm}|c|}\hline
\textbf{Group structure}; acts as a group on its elements and as pointwise multiplication on representations. The unit is the identity element.
&  \quad  \begin{array}{c} \\[-5pt] \ZmultSym::\ket{g_1}\otimes\ket{g_2}\mapsto\ket{g_1+g_2} \qquad \ZunitSym\;::\ket{\mathbbm{1}} \end{array} \quad \\\hline
\textbf{Group elements}; these are classical states of $\XdotSym$.
& \rule{0pt}{8ex}  \left\{\begin{pic}[xscale={\tikzxscale}, yscale={\tikzyscale}]
\node [point, fill=black, scale=1.4] (0) at (0, -2) {};
\node at (0.6, -2.6) {$g$};
\node [none] (1) at (0, -0) {};
\draw (0) to (1);
\end{pic}\right\}\quad\mbox{OR}\quad
\left\{\begin{pic}[xscale={\tikzxscale}, yscale={\tikzyscale}]
\node [whitedot] (0) at (0, -2) {$g$};
\node [none] (1) at (0, -0) {};
\draw (0) to (1);
\end{pic}\right\}  \\\hline
\textbf{Representation structure}; acts as pointwise multiplication on group elements and as the representation group on representations. The unit is the trivial representation.& \rule{0pt}{8ex}\quad $\XmultSym::\ket{g_1}\otimes\ket{g_2}\mapsto\ket{g_1+g_2} \qquad \XunitSym\;::\ket{\mathbbm{1}}$ \quad \\\hline
\textbf{Representations} and \textbf{representation states} (abelian $\mathbb{G}$); these are daggers of each other and are classical co-states and states of $\ZdotSym$ respectively. & \rule{0pt}{8ex}  \left\{\begin{pic}[xscale={\tikzxscale}, yscale={\tikzyscale}]
\node [point, scale=1.4] (0) at (0, -2) {};
\node at (0.6, -2.6) {$\chi$};
\node [none] (1) at (0, -0) {};
\draw (0) to (1);
\end{pic}\right\}\quad\mbox{OR}\quad
\left\{\begin{pic}[xscale={\tikzxscale}, yscale={\tikzyscale}]
\node [blackdot, scale=2] (0) at (0, -2) {};
\node at (0.6, -2.6) {$\chi$};
\node [none] (1) at (0, -0) {};
\draw (0) to (1);
\end{pic}\right\} \\\hline
\textbf{Representations} and \textbf{representation states} (non-abelian $\mathbb{G}$); these are daggers of each other and act as generalized classical co-states and states of $\ZdotSym$ respectively.
& \rule{0pt}{10ex} \left\{\begin{pic}[xscale={\tikzxscale}, yscale={\tikzyscale}]
\node [mapdag] (0) at (0, -2) {$\chi$};
\node [none] (1) at (0, -0) {};
\node [none] (2) at (-0.5, -3.5) {};
\node [none] (3) at (0.5, -3.5) {};
\draw (0) to (1);
\draw (-0.5,-2.7) to (2);
\draw (0.5,-2.7) to (3);
\end{pic}\right\} \\\hline
\textbf{Fourier transform}; For arbitrary state $f$; Definition~\ref{def:FourierTransform} and Lemma~\ref{lemma_FTTraditionalSMC2} (any $\mathbb{G}$).& \rule{0pt}{10ex} \input{tikz/4_FTnonAb2.tikz}\\\hline
\textbf{Fourier matrix}; Definition~\ref{def:CategoricalFmat}. This can be thought of as a color-change operation. 
& \begin{pic}
\node [morphism] (h) at (0,0) {$F$};
\node [whitedot] (w) at (0,-0.75) {$\alpha$};
\draw (w)  to (h.south);
\draw (0,0.75) to (h.north);
\end{pic}
\;=\;
\begin{pic}[xscale={\tikzxscale}, yscale={\tikzyscale}]
\node [blackdot, scale=2] (0) at (0, -2) {};
\node at (0.6, -2.6) {$\alpha$};
\node [none] (1) at (0, -0) {};
\draw (0) to (1);
\end{pic}
\qquad\quad
\rule{0pt}{13ex}
\input{tikz/4_HadamardSpider.tikz}
\\\hline
\end{tabulary}
}

\end{figure}