Introducing the classical Discrete Fourier Transform (DFT)

Before we dive into the QFT, it is important to know about the DFT because the QFT is derived from the DFT. The DFT is known as the frequency domain representation of an input sequence. It is used in the spectral analysis of various signals, such as reducing the variance of a spectrum. It is also utilized in the lossy compression of image and sound data. Apart from the previous applications mentioned, the DFT is also used in mathematics, such as for solving partial differential equations and in polynomial multiplication as well. Since the Discrete-Time Fourier Transform (DTFT) of a sequence represents a continuous and periodic transformation of the input sequence, if we sample the DTFT at periodic intervals, we get the DFT of the input sequence.

Mathematically, the DFT is defined by the following equation:

From the mathematical equation of the DFT, it is clear that there is a mapping from the input...