According to this answer by rrtucci, I still cannot catch the spirit of QFT algorithm.
So I would like to ask why are we using the Hadamard gate when computing the Fourier Transform?
Moreover, what is the main idea behind Hadamard Gate?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
The intuition, roughly speaking, is that the only way that you're going to get some difference between classical and quantum computing is if you are able to prepare qubits in a superposition. If you remain in a basis state the whole time, you just have a classical computation. So, you need superposition. Hadamard is the gate that prepares superpositions at the start of an algorithm, and it's the gate that, either by itself, or with the help of some phase gates in the Fourier transform, converts a superposition back into a basis state so that we can read it out at the end.
