The algorithm
Since Shor’s algorithm, QFT (Quantum Fourier Transform) has become one of the most important pieces in quantum circuits.
Classically, Fourier Transform is a transformation used to map signals from time domain to frequency domain.
In qunatum, it acts similarly, however the idea here is to turn visible phase patterns.
The overall formulation for QFT is:
$$\ket{\phi_y} = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}{e^{\frac{2\pi i}{2^n}xy}\ket{x}}$$
being $n$ the number of qubits and $x$ and $y$ the basis states we are mapping.
To generalize, we could formulate it to generate a matrix such as:
$$\ket{\phi} = \frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1}\sum_{x=0}^{2^n-1}e^{\frac{2\pi i}{2^n}xy}\ket{x}\bra{y}$$
The idea is that, by manipulating phases we can embbed something that wasn’t measurable into the probability distribution.
For a single qubit, it’s done by applying a hadammard gate onto the given $\ket{\phi}$ state.
$$H\ket{\phi}$$
But for larger circuits, QFT can be implemented, in the standard format, by applying a sequence of Hadammards, CPhases and SWAP gates.
Example
Given a circuit with $2$ qubits and we are aiming to apply QFT to visualize the distribution generated by a phase $e^{\frac{i \pi}{2}}$.
which after measuremente give us:
When we apply $H$ and $P(\pi/2)$, the state becomes: $\frac{1}{\sqrt{2}} \left(\ket{00} + i \ket{01} \right)$.
Since QFT for $2$ qubits is:
$$ QFT_4 = \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & e^{\frac{\pi i}{2}} & e^{\pi i} & e^{\frac{3\pi i}{2}} \\ 1 & e^{\pi i} & e^{2 \pi i} & e^{3 \pi i} \\ 1 & e^{\frac{3\pi i}{2}} & e^{3 \pi i} & e^{\frac{9\pi i}{2}} \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{bmatrix} $$
after applying $QFT_4$ on the previous state we have: $\frac{\sqrt{2}}{4} \left( \left(1 + i\right)\ket{00} + \left(1 - i\right)\ket{10} \right) + \frac{\sqrt{2}}{2} \ket{11} $.
To understand it better, look closely to each column in $QFT_4$, notice that each column goes with some predefined step. At the first column the step is $e^{0}$, the second is $e^{\frac{\pi i}{2}}$, the third $e^{\pi i}$ and the last one $e^{\frac{3 \pi i}{2}}$. This way, if we select a column to be part of our superposition state, it will walk with this steps.
In our example, we had the state:
$$ \ket{\phi} = \frac{1}{\sqrt{2}} \begin{pmatrix} e^0 \\ e^{\frac{\pi i}{2}} \\ 0 \\ 0 \end{pmatrix} $$
With the application of $QFT_4$, the state is transformed into:
$$ \ket{\phi}_{QFT} = \frac{1}{2\sqrt{2}} \begin{pmatrix} e^0 e^0 + e^{\frac{\pi i}{2}} e^0 \\ e^0 e^0 + e^{\frac{\pi i}{2}} e^{\frac{\pi i}{2}} \\ e^0 e^0 + e^{\frac{\pi i}{2}} e^{\pi i}\\ e^0 e^0 + e^{\frac{\pi i}{2}} e^{\frac{3 \pi i}{2}} \\ \end{pmatrix} $$
Since the $\ket{00}$ is mapped by the first column it won’t be affected, but the second one will have its phase altered by steps of $e^{\frac{\pi i}{2}}$. In a hypothetical and simpler version, if we have no superposition neither a phase, the state would be:
$$ \ket{01}_{QFT} = \frac{1}{2} \begin{pmatrix} e^0 \\ e^{\frac{\pi i}{2}} \\ e^{\pi i}\\ e^{\frac{3 \pi i}{2}} \\ \end{pmatrix} = \frac{1}{2} \begin{pmatrix} 1 \\ i \\ -1 \\ -i \\ \end{pmatrix} $$
which is pretty much a round around the unitary complex circle in terms of phases (which could be seen as a sinusoidal signal), but raising an equal superposition.
But in a different format, if we had a superposition $\ket{1+}$:
$$ \ket{1+}_{QFT} = \frac{1}{2\sqrt{2}} \begin{pmatrix} e^{0} + e^{0} \\ e^{\pi i} + e^{\frac{3 \pi i}{2}} \\ e^{2 \pi i} + e^{3 \pi i} \\ e^{3 \pi i} + e^{\frac{9 \pi i}{2}} \\ \end{pmatrix} = \frac{1}{2\sqrt{2}} \begin{pmatrix} 2 \\ -1 - i \\ 0 \\ -1 + i \\ \end{pmatrix} $$
Which is completely different step in the circle.
A nice visualization of it is presented in the qiskit page:
Overall
In general, QFT can be seen as a method to make usage of phases to extract periods via phase steps, the idea is to encode the phases someway and via an specific step, extracting information about a superposition state.
This algorithm is one of the most important pieces of quantum code you can find, being applied in algorithms such as Quantum pattern recoginition, Shor’s algorithm and QPE.
For more information check: