The Quantum Fourier Transform

If you took a college class in signal processing and communication, chances are you would already be at home with Fourier Transforms. If this is the first time you hear the words, don’t worry about it. Simply put, the Fourier Transform is a mathematical technique that takes functions from the spatial/temporal domain to the frequency domain. The Fourier Transform of a function is a complex-valued function of frequency whose magnitude represents the amount of that frequency present in the original function and whose argument is the phase offset of the basic sinusoid in that frequency. This technique has many uses, particularly in signal processing and noise cancellation. Those are not important to us for this course. What we are more interested in is the mathematical and geometric properties of the Fourier Transform in the quantum realm.