Quantum Computing and Communications: An Engineering Approach

6

Quantum Fourier Transform and its Applications

When Fourier published his most famous work Théorie analitique de la chaleur in 1822 he had not the slightest idea that his transform – which was originally applied in thermodynamics – would run such a widespread course in many different areas of signal/information processing from spectroscopy to telecommunications where this transform constitutes the bridge between signal representations in time and frequency domains. The extraordinary success of the Fourier transform is due to its discrete version the so-called discrete Fourier transform (DFT), which has a computationally very efficient implementation in the form of the fast Fourier transform (FFT).

The quantum version of the Fourier transform lies at the core of many quantum computing algorithms. The quantum Fourier transform (QFT) is analogous to the classical FFT, and by exploiting the advantages of quantum parallelism, can be computed exponentially faster. However, as we will explain in this chapter this advantage cannot be used to enhance the speed of data processing directly, since all the individual Fourier coefficients (probability amplitudes) cannot be accessed by a measurement, similar to the fact we experienced with quantum parallelism. Instead QFT can be regarded as a building block of complex quantum algorithms.

First classical Fourier transform and its quantum counterpart will be introduced in Section 6.1 which is followed in Section 6.2 by its very useful application ...