Fourier transforms from strongly complementary observables

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.