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

DaftWullie · Accepted Answer

While the QFT and Hadamard transforms are different, their action on the input state $|00ldots 0rangle$ 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|0rangle=frac{|0rangle+|1rangle}{sqrt{2}}implies (H|0rangle)^{otimes n}=frac{1}{sqrt{2^n}}sum_{xin{0,1}^n}|xrangle
$$
Fourier Transform:
$$
U_{QFT}=frac{1}{sqrt{2^n}}sum_{x,y=0}^{2^n-1}e^{2pi ifrac{xy}{2^n}}|yranglelangle x|implies U_{QFT}|0rangle=frac{1}{sqrt{2^n}}sum_{x=0}^{2^n-1}|xrangleequivfrac{1}{sqrt{2^n}}sum_{xin{0,1}^n}|xrangle
$$

Nelimee · Answer

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:

Hadamard gates on all the "ancillary" qubits
Controlled unitary matrices (controlled circuits)
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).

Why can the QFT be replaced by Hadamard gates?

2 Answers

Add your own answers!

Ask a Question