The Quantum Fourier Transform

Let’s dive into a subroutine of Shor's Algorithm that involves the Fourier Transform. In particular, we will implement its analog in the quantum realm.

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.

Get hands-on with 1200+ tech skills courses.