Up to now almost all the groups considered for applications in signal processing are Abelian groups. Fast Fourier Transforms (FFTs) on finite Abelian groups are widely used in signal processing and quantum computing. The modern theory of such transforms is of increasing interest and many fundamental problems in particular applications have been solved already. The case of non--Abelian groups has not attracted as much attention although there are much more possible applications, in spite of or just because of the more involved algebraic methods. Groups which have received much interest in the signal processing community are Heisenberg--Weyl group (because of their connection to time--frequency methods) and the affine groups which form the basis of wavelet analysis.

In this work we study the quantum harmonic analysis of functions on the n-D Heisenberg-Weyl groups Hei(GF(p)) over the Galois field GF(p). Analogous to the quantum Fourier transform, the expansion of functions on the basis of irreducible complex matrix representations of the Heisenberg-Weyl group defines the quantum Fourier-Weyl-Heisenberg transform. Fast algorithms for the nD quantum transforms on the different Heisenberg-Weyl groups are developed in this paper.

lab@cs.tut.fi