  Ongoing work in quantum information emphasises the need for a structural
understanding of quantum speedups: in this work, we focus on the quantum
Fourier transform and the structures in quantum theory that enable it. We
elucidate a general connection in any process theory between the Fourier
transform and strongly complementary observables, i.e. Hopf algebras in dagger
symmetric monoidal categories. We generalise the necessary tools of
representation theory from fdHilb to arbitrary dagger symmetric monoidal
categories. We define groups, characters and representations, and we prove
their relation to strong complementarity. The Fourier transform is then defined
in terms of pairs of strongly complementary observables, in both the abelian
and non-abelian case. In the abelian case, we draw the connection with
Pontryagin duality and provide categorical proofs of the Fourier Inversion
Theorem, the Convolution Theory, and Pontryagin duality. Our work finds
application in the novel characterisation of the Fourier transform for the
category fRel of finite sets and relations. This is a result of interest for
the study of categorical quantum algorithms, as the usual construction of the
quantum Fourier transform in terms of Fourier matrices is shown to fail in
fRel. Despite this, the process theoretic perspective on the Fourier transform
is sensible in this setting. Furthermore, our categorical setting provides a
generalisation of the abelian Fourier transform from finite-dimensional Hilbert
spaces to finite-dimensional modules over arbitrary semirings, as well as a
further generalisation to finite non-abelian groups, including a fully
categorical generalisation of the Gelfand-Naimark theorem.
