# Fourier transform on all functions

## Definition

The Fourier transform on all functions is a unitary operator corresponding to a finite group, that transforms from the basis of characteristic functions of the elements to the basis of representative functions for the various representations.

## Facts

### For a normal subgroup

Let $N$ be a normal subgroup of $G$, and $Nx$ be a coset of $N$. Then if $f$ is the characteristic function of $Nx$ (that is, $f$ is 1 on the whole of $Nx$ and 0 elsewhere) then the Fourier transform of $f$ contains the representative functions corresponding only to those representations which restrict to the identity on $N$.

The proof of this is as follows:

• The space of functions on $G$ which are constant on the cosets of $N$ is isomorphic to the space of functions on $G/N$.
• We know that any function on $G/N$ can be expressed as a linear combination of representative functions on $G/N$. Hence, from the above correspondence, any function on $G$ which is constant on the cosets of $N$ can be expressed as a linear combinations of representative functions of those representations of $G$ that have $N$ in the kernel

In fact, the Fourier transform for characteristic functions on cosets corresponds to the Fourier transform on all functions in $G/N$.

### For any subgroup

For any subgroup, we can say the following:

• The characteristic function of any coset is a linear combination of representative functions arising from representations that are trivial on the normal core of the subgroup
• The functions that arise as linear combinations of representative functions that are trivial on the whole subgroup, are in fact constant on the cosets of the normal closure of the subgroup

## Importance of the Fourier transform for algorithms

The Fourier transform is important from the algorithmic viewpoint in quantum algorithms as follows. Suppose we have a quantum state that is a uniform superposition of some random coset of a subgroup, and we want to use this to find the subgroup. We cannot directly measure, as we can take only one measurement, and just measuring once will not give us any information about the subgroup.

What we do to use the uniform superposition on the coset is to perform a Fourier transform. This is permissible since the Fourier transform is a unitary operator. We now land up with a superposition of representative functions for representations which are trivial on the normal core of the subgroup. Performing a measurement now gives us the representative function for a particular representation which is trivial on the normal subgroup, and hence we have recovered a particular representation which is trivial on the normal core.

The idea of the algorithm beyond this is to repeat this experiment several times and hence collect many representations which are trivial on the normal core. Once we have done that, it is simply a matter of trying to find the common kernel for all these representations.