Representation-theoretical properties of the approximate quantum Fourier transform (Q937218)

The discrete Fourier transform (DFT) plays a key role in quantum computing. The authors consider approximate Fourier transforms which are obtained by pruning the twiddle factors of DFT. A parameter determines the level of pruning. The extreme cases are no pruning, which leads to the DFT, and complete pruning, which leads to the Hadamard transform. The main result of this paper is a representation-theoretical interpretation of the transform obtained for all intermediate levels of pruning. It is shown that the resulting approximate quantum Fourier transforms are basefield transforms, i.e., they decompose the regular representation of the cyclic group over non-splitting fields.