Fourier Transform on Finite Groups (Quantum Fourier Transform)

Often it’s useful to study functions on spaces by examining how they transform under various transformations of the spaces. This general idea gives rise to many interesting objects. For instance, if the space is the real line, we can ask how functions transform when the real line is translated. This gives rise to the Fourier transform. For functions on a sphere, we can ask about transformation under rotations. This is the origin of the spherical harmonics. On a finite cyclic group, we can ask how functions transform when the group is left- or right- multiplied by a group element. Thinking of the group elements as marking positions in space, we can think of this group action as a shift, and think about the resulting discrete Fourier transform as a discrete analogue of the standard one.

In this post, I’ll discuss briefly a generalization of the discrete Fourier transform to arbitrary finite groups. The unifying thread in all the examples above is that the functions can be organized into irreducible representations of the group of transformations being applied to the space on which they’re defined. Those transformations here will be left- and right-multiplication by group elements.

1. Definition of the QFT

Let G be a finite group of size \left\vert G\right\vert. Since G is finite, we don’t have to be particularly careful about what we mean by “functions on G“, but because it matches up with the infinite case and because we’ll want an inner-product structure, we’ll specify the space \ell^2(G) of square-summable complex-valued functions. This space has a basis \left\lbrace\delta_g\right\rbrace_{g\in G} of functions defined by \delta_g(g)=1, \delta_g(h)=0 for all h\in G, h\neq g. Following QI convention, I’ll denote this \left\vert g\right\rangle.

Let \Lambda be a maximal set of unitarily-inequivalent unitary representations of G. We know that

\begin{aligned} \sum_{\lambda\in \Lambda}d_\lambda^2=\left\vert G\right\vert \end{aligned}

where d_\lambda is the dimension of the representation \lambda\in\Lambda. We can therefore choose another orthonormal basis for \ell^2(G) with basis functions labeled by elements \left\vert\lambda;ij\right\rangle for \lambda\in \Lambda and i,j=1,2,\ldots, d_\lambda. Now we can define the Quantum Fourier Transform (QFT) and its inverse as transformations from the basis \left\vert g\right\rangle to the basis \left\vert\lambda;ij\right\rangle and back:

\begin{aligned} U_{QFT}&=\sum_{\lambda\in\Lambda}\sum_{i,j=1}^{d_\lambda}\sum_{g\in G}\sqrt{\frac{d_\lambda}{\left\vert G\right\vert}}\left[R_\lambda(g)\right]_{ij}\left\vert\lambda;ij\right\rangle\left\langle g\right\vert\\ \\ U_{QFT}^\dagger&=\sum_{\lambda\in\Lambda}\sum_{i,j=1}^{d_\lambda}\sum_{g\in G}\sqrt{\frac{d_\lambda}{\left\vert G\right\vert}}\left[R_\lambda(g)\right]_{ij}^*\left\vert g\right\rangle\left\langle \lambda;ij\right\vert \end{aligned}

There’s nothing particularly quantum about this, other than the use of Dirac notation. However, an efficient implementation of the QFT is at the heart of Shor’s factorization algorithm. Somewhat tragically, the algorithm only uses the QFT for cyclic groups, so its full generality isn’t featured in that setting.

The QFT can be thought of as a map from complex functions on G to complex matrix-valued functions on the inequivalent unitary irreducible representations of G, where the value of the function at \lambda is a d_\lambda\times d_\lambda matrix. A convenient way to visualize the Quantum Fourier Transform is via the following table. The row next to a group element g is the QFT of \left\vert g\right\rangle, and the complex conjugate of the column under the (i,j) matrix element of the representation \lambda is the inverse QFT of \left\vert \lambda;ij\right\rangle. In other words, the table is (transpose of) the matrix of the unitary transformation U_\text{QFT}. The fact that the columns form an orthonormal set is the Schur orthogonality relation. This can be used to prove that U_\text{QFT} is in fact unitary, so the rows do as well.


2. Transformation of Functions Under Group Action

The Fourier basis \left\vert \lambda;ij\right\rangle defined above turns out to be a useful basis for seeing how functions transform under group actions. In the group element basis, we have

U_\text{QFT}^\dagger\left\vert \tau;nm\right\rangle=\sum_g\sqrt{\frac{d_\tau}{\left\vert G\right\vert}}\left[R_\tau(g)\right]_{nm}^*\left\vert g\right\rangle

For h\in G, define the operators L_h and R_h by L_h\left\vert g\right\rangle=\left\vert hg\right\rangle and R_h\left\vert g\right\rangle=\left\vert gh^{-1}\right\rangle. As representations of G on \ell^2(G), these are know as the right and left regular representations, respectively. (I made the mistake of using R for both the right regular representation of G on \ell^2(G) and the matrices of the irreducible representations of G, but it should be clear from context what is meant.) Then:

\begin{aligned} L_hU_\text{QFT}^\dagger\left\vert\tau;nm\right\rangle&=\sum_g\sqrt{\frac{d_\tau}{\left\vert G\right\vert}}\left[R_\tau(g)\right]_{nm}^*\left\vert hg\right\rangle=\sum_g\sqrt{\frac{d_\tau}{\left\vert G\right\vert}}\left[R_\tau(h^{-1}g)\right]_{nm}^*\left\vert g\right\rangle=\sum_g\sqrt{\frac{d_\tau}{\left\vert G\right\vert}}\left[R_\tau(h^{-1})R_\tau(g)\right]_{nm}^*\left\vert g\right\rangle\\ &=\sum_k\left[R_\tau(h^{-1})\right]_{nk}^*\sum_g\sqrt{\frac{d_\tau}{\left\vert G\right\vert}}\left[R_\tau(g)\right]_{km}^*\left\vert g\right\rangle=\sum_k\left[R_\tau(h^{-1})\right]_{nk}^*U_\text{QFT}^\dagger\left\vert\tau;km\right\rangle\\ &=\sum_k\left[R_\tau(h)\right]_{kn}U_\text{QFT}^\dagger\left\vert\tau;km\right\rangle\\ \\ R_hU_\text{QFT}^\dagger\left\vert\tau;nm\right\rangle&=\sum_g\sqrt{\frac{d_\tau}{\left\vert G\right\vert}}\left[R_\tau(g)\right]_{nm}^*\left\vert gh^{-1}\right\rangle=\sum_g\sqrt{\frac{d_\tau}{\left\vert G\right\vert}}\left[R_\tau(gh)\right]_{nm}^*\left\vert g\right\rangle=\sum_g\sqrt{\frac{d_\tau}{\left\vert G\right\vert}}\left[R_\tau(g)R_\tau(h)\right]_{nm}^*\left\vert g\right\rangle\\ &=\sum_k\left[R_\tau(h)\right]_{km}^*\sum_g\sqrt{\frac{d_\tau}{\left\vert G\right\vert}}\left[R_\tau(g)\right]_{nk}^*\left\vert g\right\rangle=\sum_k\left[R_\tau(h^{-1})\right]_{mk}U_\text{QFT}^\dagger\left\vert\tau;nk\right\rangle \end{aligned}

where I’ve used the fact that these are unitary representations. Sticking a U_\text{QFT} in front of these two equations, we find

\begin{aligned} U_\text{QFT}L_hU_\text{QFT}^\dagger\left\vert\tau;nm\right\rangle&=\sum_{k=1}^{d_\tau}\left[R_\tau(h)\right]_{kn}\left\vert\tau;km\right\rangle\\ \\ U_\text{QFT}R_hU_\text{QFT}^\dagger\left\vert\tau;nm\right\rangle&=\sum_{k=1}^{d_\tau}\left[R_\tau(h^{-1})\right]_{mk}\left\vert\tau;nk\right\rangle \end{aligned}

so that

\boxed{\begin{aligned} \left\langle\lambda;ij\right\vert U_\text{QFT}L_hU_\text{QFT}^\dagger\left\vert\tau;nm\right\rangle&=\left[R_\tau(h)\right]_{in}\delta_{\lambda\tau}\delta_{jm}\\ \\ \left\langle\lambda;ij\right\vert U_\text{QFT}R_hU_\text{QFT}^\dagger\left\vert\tau;nm\right\rangle&=\left[R_\tau(h^{-1})\right]_{mj}\delta_{\lambda\tau}\delta_{in}. \end{aligned}}

What we’ve done is to use the QFT to block diagonalize the left and right regular representations of the group G on \ell^2(G). Notice that, unless G is Abelian and thus d_\lambda =1 for all \lambda, it isn’t possible to fully simultaneously diagonalize the operators L_g and R_g. Instead, we find a set of \left\vert G\right\vert=\sum_{\lambda}d_\lambda^2 basis functions on G grouped into sets of d_\lambda that transform under the representation \lambda, with multiplicity d_\lambda. We can think of these as being organized into a block diagonal matrix with blocks of size d_\lambda, one for each irreducible representation \lambda, with the left regular representation mixing functions in the same column and the right regular representation mixing functions in the same row. This is exactly how the d_\lambda\times d_\lambda matrices transform under left and right multiplications by g or g^{-1}.

This analysis sheds some light on what the group Fourier transform/QFT is – a way to analyze functions on G based on how they transform under the left and right actions of G on itself – but it doesn’t necessarily explain why we should care. One answer is simply that it provides a way of seeing these functions from a different perspective. I don’t know of any “real world” examples of what looking at the Fourier transform of a function on a generic finite group tells us. For instance, Fourier transforms of time-series yield frequency-space functions, which can be used e.g. to identify periodically recurring phenomena. It would be nice to have a similarly data-processing-motivated intuition for the Fourier transform on arbitrary groups. Part of the problem is that there aren’t many cases (that I can think of) of data taking the form of a function on any interesting group. Some googling suggests that one application is to functions on symmetric groups, where the Fourier transform can be used to study mixing times for randomly shuffled decks of cards.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s