Why can the QFT be replaced by Hadamard gates?

Question

I'm studying Shor's Algorithm. In the book, author explains QFT can be replaced by Hadamard gates? Why this process is possible??

Thank you everybody. This is QPE. I attach part of book!!

Answer 1

While the QFT and Hadamard transforms are different, their action on the input state $|00\ldots 0\rangle$ is identical; both produce the uniform superposition of all states. So, if you've got a choice of which to use, you shoulduse the one that is the easiest to implement: the Hadamard transform. Hadamard Transform: $$ H|0\rangle=\frac{|0\rangle+|1\rangle}{\sqrt{2}}\implies (H|0\rangle)^{\otimes n}=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle $$ Fourier Transform: $$ U_{QFT}=\frac{1}{\sqrt{2^n}}\sum_{x,y=0}^{2^n-1}e^{2\pi i\frac{xy}{2^n}}|y\rangle\langle x|\implies U_{QFT}|0\rangle=\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle\equiv\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle $$

Answer 2

The $H$ gates do not replace a Quantum Fourier Transform. The Quantum Phase Estimation algorithm is defined as shown in the picture you linked in your question:

1. Hadamard gates on all the "ancillary" qubits
2. Controlled unitary matrices (controlled circuits)
3. Inverse QFT.

Having an inverse QFT at the end of the circuit does not necessarily mean that there should be a QFT beforehand.

In this case, the inverse QFT is used because it allows us to extract the information we want from a measurement. Go check the maths (on the Wikipedia page for example) to convince yourself that the $H$ gates at the beginning do not replace a QFT.

You can also try to replace the $H$ gates by a QFT, do the maths, and see by yourself what would be the result of the algorithm in this case. It seems to be a good exercise, and hopefully it will convince you that a QFT has nothing to do at the beginning of the Quantum Phase Estimation algorithm (EDIT: it was the worst example possible to convince yourself, see @DaftWullie's answer).