Here we will be talking about the Quantum Fourier transform, a discrete analogue to the Discrete Fourier transform
Input: a vector of complex numbers
$$ (x_0,x_1,\ldots ,x_{N-1}) $$
Algorithm: we can then apply the transform following
$$ F:(x_0,x_1,\ldots ,x_{N-1}) \to (y_0 ,\ldots ,y_{N-1}) $$
where
$$ \boxed{y_k=\frac{1}{\sqrt{N}} \sum ^{N-1} _{j=0} x_j \exp \left ( \frac{2\pi ijk}{N} \right )} $$
🗒️ Note: $i$ is the complex number $j$ is what we are summing over and $k$ is the Fourier space
Output:
$$ (y_0 ,y_1,\ldots ,y_{N-1}) $$
Input: a computational basis
$$ \ket{j} \quad \text{for} \quad j=0,1,\ldots ,N-1 $$
with the number of combinations being $N=2^n$
Algorithm: the quantum Fourier transform
$$ F:\sum ^{N-1}{j=0} x_j \ket{j} \to \sum ^{N-1}{k=0} y_k \ket{k} $$
which we can represent as
$$ \begin{aligned}|j\rangle &= \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{\frac{2\pi i\,j\,k}{N}}\,|k\rangle \\[6pt]&= \frac{1}{2^{\tfrac{n}{2}}} \sum_{k_1=0}^1 \sum_{k_2=0}^1 \cdots \sum_{k_n=0}^1 e^{\frac{2\pi i\,j}{N}\bigl(\sum_{l=1}^n k_l\,2^{l-1}\bigr)} \,\bigotimes_{l=1}^n |k_l\rangle \\[6pt]&= \frac{1}{2^{\tfrac{n}{2}}} \sum_{i_1=0}^1 \sum_{i_2=0}^1 \cdots \sum_{i_n=0}^1 e^{\frac{2\pi i\,j}{N}\bigl(\sum_{l=1}^n i_l\,2^{l-1}\bigr)} \,\bigotimes_{l=1}^n |i_l\rangle \\[6pt]&= \frac{1}{2^{\tfrac{n}{2}}} \sum_{i_1=0}^1 \sum_{i_2=0}^1 \cdots \sum_{i_n=0}^1 e^{\frac{2\pi i\,j}{N}\bigl(\sum_{l=1}^n i_l\,2^{l-1}\bigr)} \,|i_1\,i_2\,\dots\,i_n\rangle \\[6pt]&= \frac{1}{2^{\tfrac{n}{2}}} \Bigl( \bigl(|0\rangle + e^{2\pi i\,0. j_n}\,|1\rangle\bigr)\otimes \bigl(|0\rangle + e^{2\pi i\,0. j_{n-1} j_n}\,|1\rangle\bigr)\otimes\cdots\otimes \bigl(|0\rangle + e^{2\pi i\,0. j_1\ldots j_n}\,|1\rangle\bigr)\Bigr)\end{aligned} $$
🗒️ Note: $0.j_1\cdots j_n$ is weird notation for $j_1 2^{-1}+j_22^{-2} +\cdots +j_n 2^{-n}$
which allows us to rewrite the algorithm
$$ F:\ket{j_1j_2\cdots j_n}\to \frac{1}{2^{\frac{n}{2}}} (\ket{0}+e^{2\pi i\, 0 . j_n } \ket{1} )\otimes \cdots \otimes (\ket{0} +e^{2\pi i\, 0. j_1j_2\cdots j_n}\ket{1}) $$
Representation: by defining, we can represent the algorithm as
$$ R_k=\begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i /2^k}
\end{pmatrix} $$
💼 Case: lets quickly go through the algorithm now that we have the complete circuit
Apply the Hadamard gate on the first qubit $\ket{j_1}$ to get
$$ \frac{1}{\sqrt{2^1}}(\ket{0} +e^{2\pi i\, 0.j_1} \ket{1} )\ket{j_2\cdots j_n} $$
where $e^{2\pi i\, 0.j_1}=1$ when $j_1=0$ and $-1$ when $j_1=1$
We apply the controlled-$R_2$ to $R_n$ gate to get
$$ \frac{1}{\sqrt{2^1}} (\ket{0} +e^{2\pi i\, 0.j_1j_2} \ket{1} )\ket{j_2\ldots j_n} $$
We then go to the second $\ket{j_2}$ and apply the Hadamard and the controlled-$R_2$ to $R_{n-1}$
$$ \frac{1}{\sqrt{2^2}} (\ket{0} + e^{2\pi i \, 0. j_1j_2\cdots j_n} \ket{1} )\otimes (\ket{0} +e^{2\pi i \, 0. j_2 \cdots j_n } \ket{1} )\ket{j_3\cdots j_n} $$
We repeat this for qubits $\ket{j_3}\cdots \ket{j_n}$ to give out general expression
$$ \frac{1}{2^{n/2}} (\ket{0} +e^{2\pi i\, 0. j_1j_2\cdots j_n}\ket{1}) \otimes \cdots \otimes (\ket{0}+e^{2\pi i\, 0 . j_n } \ket{1} ) $$
We can then reverse the order by applying swap operations to get
$$ \frac{1}{2^{\frac{n}{2}}} (\ket{0}+e^{2\pi i\, 0 . j_n } \ket{1} )\otimes \cdots \otimes (\ket{0} +e^{2\pi i\, 0. j_1j_2\cdots j_n}\ket{1}) $$
our desired expression
💎 Conclusion: the complexity here is $\mathcal O(n^2)$ the FFT scales as $\mathcal O (N\log N )\equiv \mathcal O(2^n n)$