For me, the "traditional Fourier Transform" is a **change of basis** of the algebra of functions from a *group* to some chosen field: from the canonical basis to something sometimes called the Fourier Basis. Because the Transform is constructed using the representation theory of the group, it has "natural" generalisations to objects with "similar" representation theory, e.g. it is defined for Hopf algebras.

I always think of the FT as this kind of **duality**. The Fourier Basis have lot's of interesting properties, but I have not seen a definition of it using extremals. It would be very interesting to see that.

A good start would be if someone gives an answer for **finite abelian groups** and finite **non-abelian groups**. Though "non-abelian" groups have a notion of FT, it is not uniquely defined and it is hard to work with it. An "extremal" condition would be enlightening.

**Update 14th Dec 2011**

Sorry that this comes several months later, but I found that there is "a way" to define the quantum Fourier transform for **abelian finite groups** using an *extremal* argument. This argument comes from reference [1] where the Fourier transform is studied as a tool to design measurements in Quantum Computation and proven to be optimal to solve the abelian hidden subgroup problem. Unfortunately, this property does not hold for **non-abelian** quantum Fourier transforms.

More concretely, what it is proven in [1] is the following (all definitions I use are defined in this paper):

Consider the *hidden subgroup problem* defined for an abelian group $G$, where the hidden subgroup $H$ is chosen uniformly at random from all subgroups of $G$. Given $n$ tensored random coset states (cosets of $H$), then the measurement that **maximises** the probability of correctly identifying the subgroup $H$ is the following:

- Start on a random coset-state $|x+H\rangle$ for unknown $H$ which is just a uniform quantum superposition over the elements of the coset $x+H$. Cf. [1] for details on how to create these quantum states.
- Apply the
**abelian quantum Fourier transform** of $G$ on this state.
- Perform a projective measurement.

Taking several outcomes of the above procedure one obtains a generating set of the orthogonal group $H^\perp$ from which the original subgroup $H$ can be recovered solving a system of linear modular equations [2]. As far as I know these "orthogonal subgroups" are sometimes called orthogonal complements in Mathematics.

To sum up, they key ingredient of the above quantum algorithm is the abelian Fourier transform which is used to implement a quantum measurement to solve the hidden subgroup problem since it maximises the probability of distinguishing the hidden subgroup. In [1] it is shown that the abelian quantum Fourier transform arises as an optimal POVM which is the solution of a semidefinite program. I guess that maybe you could adopt this kind of extremal property as a definition of the Fourier transform for finite abelian groups. **Note**: it is not clear to me that the optimal POVM found in [1] is *unique* (up to permutations).

Whatuniversality properties? What categories do you have in mind? $\endgroup$ – Yemon Choi Oct 16 '10 at 4:31