Representation-theoretical Properties of the Approximate Quantum Fourier Transform

Among the transformations used in quantum computing the discrete Fourier transform (DFT) plays a key role. A striking fact is that the computational complexity of the DFT with respect to the quantum gate model is polylogarithmic in the length of the input data. In this paper we consider approximate Fourier transformations which are obtained by pruning the twiddle factors of DFT. A parameter is used which 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. Our main result is to give a representation-theoretical interpretation of the transformation obtained for all intermediate levels of pruning. We show that the resulting approximate quantum Fourier transforms are basefield transformations, i.e., they decompose the regular representation of the cyclic group over non-splitting fields.