# Why can the QFT be replaced by Hadamard gates?

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!! • Hi! Could you give a few more details about what you mean? Feb 7 '20 at 9:17
• @met927: For example in phase estimation, qubits are firstly initialized with Hadamard gates. This construnction replaces QFT. Feb 7 '20 at 10:08
• I attach part of book!! could you explaint that part??
– 유도경
Feb 7 '20 at 11:25

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$$

• Thank you so much. Then what this means?? "The Fourier transform on the input can be exchanged for the Walsh-Hadamard transform (Hadamard gates)"
– 유도경
Feb 7 '20 at 11:23
• It means that you can use either. It doesn't matter. Feb 7 '20 at 11:52
• Thanks for writing up the maths, I did not expect the two to have the same effect. I learned something, thank you! :) Feb 7 '20 at 12:57
• Thank you very much. Have a nice day!!
– 유도경
Feb 7 '20 at 14:13

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).

• You are so kind!! Thank you very much. Have a nice day!!
– 유도경
Feb 7 '20 at 11:04