## Introduction to the Classical Discrete Fourier transform:

The DFT transforms a sequence of N$N$ complex numbers {xn}:=x0,x1,x2,...,xN−1$\{{\mathbf{x}}_{n}\}:={x}_{0},{x}_{1},{x}_{2},...,{x}_{N-1}$ into another sequence of complex numbers {Xk}:=X0,X1,X2,...$\{{\mathbf{X}}_{k}\}:={X}_{0},{X}_{1},{X}_{2},...$ which is defined by

Xk=∑n=0N−1xn.e±2πiknN$${X}_{k}=\sum _{n=0}^{N-1}{x}_{n}.{e}^{\pm \frac{2\pi ikn}{N}}$$

We might multiply by suitable normalization constants as necessary. Moreover, whether we take the plus or minus sign in the formula depends on the convention we choose.

Suppose, it's given that N=4$N=4$ and x=⎛⎝⎜⎜⎜12−i−i−1+2i⎞⎠⎟⎟⎟$\mathbf{x}=\left(\begin{array}{c}1\\ 2-i\\ -i\\ -1+2i\end{array}\right)$.

We need to find the column vector X$\mathbf{X}$. The general method is already shown on the Wikipedia page. But we will develop a matrix notation for the same. X$\mathbf{X}$ can be easily obtained by pre multiplying x$\mathbf{x}$ by the matrix:

M=1N−−√⎛⎝⎜⎜⎜11111ww2w31w2w4w61w3w6w9⎞⎠⎟⎟⎟$$M=\frac{1}{\sqrt{N}}\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& w& {w}^{2}& {w}^{3}\\ 1& {w}^{2}& {w}^{4}& {w}^{6}\\ 1& {w}^{3}& {w}^{6}& {w}^{9}\end{array}\right)$$

where w$w$ is e−2πiN${e}^{\frac{-2\pi i}{N}}$. Each element of the matrix is basically wij${w}^{ij}$. 1N√$\frac{1}{\sqrt{N}}$ is simply a normalization constant.

Finally, X$\mathbf{X}$ turns out to be: 12⎛⎝⎜⎜⎜2−2−2i−2i4+4i⎞⎠⎟⎟⎟$\frac{1}{2}\left(\begin{array}{c}2\\ -2-2i\\ -2i\\ 4+4i\end{array}\right)$.

Now, sit back for a while and notice a few important properties:

- All the columns of the matrix M$M$ are orthogonal to each other.
- All the columns of M$M$ have magnitude 1$1$.
- If you post multiply M$M$ with a column vector having lots of zeroes (large spread) you'll end up with a column vector with only a few zeroes (narrow spread). The converse also holds true. (Check!)

It can be very simply noticed that the classical DFT has a time complexity O(N2)$\mathcal{O}({N}^{2})$. That is because for obtaining every row of X$\mathbf{X}$, N$N$ operations need to be performed. And there are N$N$ rows in X$\mathbf{X}$.

## The Fast fourier transform:

Now, let us look at the Fast fourier transform. The fast Fourier transform uses the symmetry of the Fourier transform to reduce the computation time. Simply put, we rewrite the Fourier transform of size N$N$ as two Fourier transforms of size N/2$N/2$ - the odd and the even terms. We then repeat this over and over again to exponentially reduce the time. To see how this works in detail, we turn to the matrix of the Fourier transform. While we go through this, it might be helpful to have DFT8${\text{DFT}}_{8}$ in front of you to take a look at. Note that the exponents have been written modulo 8$8$, since w8=1${w}^{8}=1$.

Notice how row j$j$ is very similar to row j+4$j+4$. Also, notice how column j$j$
is very similar to column j+4$j+4$. Motivated by this, we are going to split the
Fourier transform up into its even and odd columns.

In the first frame, we have represented the whole Fourier transform matrix
by describing the j$j$th row and k$k$th column: wjk${w}^{jk}$. In the next frame, we separate the odd and even columns, and similarly separate the vector that is to be transformed. You should convince yourself that the first equality really is
an equality. In the third frame, we add a little symmetry by noticing that
wj+N/2=−wj${w}^{j+N/2}=-{w}^{j}$ (since wn/2=−1${w}^{n/2}=-1$).

w2jk${w}^{2jk}$w$w$w2${w}^{2}$N/2$N/2$j$j$k$k$w2jk${w}^{2jk}$DFT(N/2)${\text{DFT}}_{(N/2)}$DFTN${\text{DFT}}_{N}$ in a new way:
Now suppose we are calculating the Fourier transform of the function f(x)$f(x)$.
We can write the above manipulations as an equation that computes the jth
term f^(j)$\hat{f}(j)$.

*Note: QFT in the image just stands for DFT in this context. Also, M refers to what we are calling N.*

This turns our calculation of DFTN${\text{DFT}}_{N}$ into two applications of DFT(N/2)${\text{DFT}}_{(N/2)}$. We
can turn this into four applications of DFT(N/4)${\text{DFT}}_{(N/4)}$, and so forth. As long as N=2n$N=2n$ for some n$n$, we can break down our calculation of DFTN${\text{DFT}}_{N}$ into N$N$
calculations of DFT1=1${\text{DFT}}_{1}=1$. This greatly simplifies our calculation.

In case of the Fast fourier transform the time complexity reduces to O(Nlog(N))$\mathcal{O}(N\mathrm{log}(N))$ (try proving this yourself). This is a huge improvement over the classical DFT and pretty much the state-of-the-art algorithm used in modern day music systems like your iPod!

## The Quantum Fourier transform with quantum gates:

The strength of the FFT is that we are able to use the symmetry of the
discrete Fourier transform to our advantage. The circuit application of QFT
uses the same principle, but because of the power of superposition QFT is
even faster.

The QFT is motivated by the FFT so we will follow the same steps, but
because this is a quantum algorithm the implementation of the steps will be
different. That is, we first take the Fourier transform of the odd and even
parts, then multiply the odd terms by the phase wj${w}^{j}$.

In a quantum algorithm, the first step is fairly simple. The odd and even
terms are together in superposition: the odd terms are those whose least
significant bit is 1$1$, and the even with 0$0$. Therefore, we can apply QFT(N/2)${\text{QFT}}_{(N/2)}$ to both the odd and even terms together. We do this by applying we will simply apply QFT(N/2)${\text{QFT}}_{(N/2)}$ to the n−1$n-1$ most significant bits, and recombine the odd and even appropriately by applying the Hadamard to the least significant bit.

Now to carry out the phase multiplication, we need to multiply each odd
term j$j$ by the phase wj${w}^{j}$ . But remember, an odd number in binary ends with a 1$1$ while an even ends with a 0$0$. Thus we can use the controlled phase shift, where the least significant bit is the control, to multiply only the odd terms by the phase without doing anything to the even terms. Recall that the controlled phase shift is similar to the CNOT gate in that it only applies a phase to the target if the control bit is one.

*Note: In the image M refers to what we are calling N.*

The phase associated with each controlled phase shift should be equal to
wj${w}^{j}$ where j$j$ is associated to the k$k$-th bit by j=2k$j=2k$.
Thus, apply the controlled phase shift to each of the first n−1$n-1$ qubits,
with the least significant bit as the control. With the controlled phase shift
and the Hadamard transform, QFTN${\text{QFT}}_{N}$ has been reduced to QFT(N/2)${\text{QFT}}_{(N/2)}$.

*Note: In the image, M refers to what we are calling N.*

**Example:**

Lets construct QFT3${\text{QFT}}_{3}$. Following the algorithm, we will turn QFT3${\text{QFT}}_{3}$ into QFT2${\text{QFT}}_{2}$
and a few quantum gates. Then continuing on this way we turn QFT2${\text{QFT}}_{2}$ into
QFT1${\text{QFT}}_{1}$ (which is just a Hadamard gate) and another few gates. Controlled
phase gates will be represented by Rϕ${R}_{\varphi}$. Then run through another iteration to get rid of QFT2${\text{QFT}}_{2}$. You should now be able to visualize the circuit for QFT$\text{QFT}$ on more qubits easily. Furthermore, you can see that the number of gates necessary to carry out QFTN${\text{QFT}}_{N}$ it takes is exactly

∑i=1log(N)i=log(N)(log(N)+1)/2=O(log2N)$$\sum _{i=1}^{\mathrm{log}(N)}i=\mathrm{log}(N)(\mathrm{log}(N)+1)/2=\mathcal{O}({\mathrm{log}}^{2}N)$$

## Sources:

https://en.wikipedia.org/wiki/Discrete_Fourier_transform

https://en.wikipedia.org/wiki/Quantum_Fourier_transform

Quantum Mechanics and Quantum Computation MOOC (UC BerkeleyX) - Lecture Notes : Chapter 5

^{P.S: This answer is in its preliminary version. As @DaftWillie mentions in the comments, it doesn't go much into "any insight that might give some guidance with regards to other possible algorithms". I encourage alternate answers to the original question. I personally need to do a bit of reading and resource-digging so that I can answer that aspect of the question.}