# Why should we use inverse QFT instead of QFT in Shor's algorithm?

Why should we use inverse QFT instead of QFT in Shor's algorithm? When I tried to simulate Shor's algorithm for small numbers, I got an answer even when I used just QFT instead of inverse QFT.

• How did you simulate the algorithm? Could you give the details? – Sanchayan Dutta Jun 9 '19 at 8:13

If you apply the QFT twice, it is equivalent to a classical multiplication by -1 modulo $$2^n$$ where $$n$$ is the size of the register. That is to say, it reverses the order of all of the computational basis states except for $$|0\rangle$$ which stays where it started. $$|k\rangle$$ becomes $$|-k\rangle = |2^n - k\rangle$$.
Now, in Shor's algorithm, the output of the QFT is a state with amplitudes whose magnitudes are approximately periodic with a period that divides $$2^n$$. This isn't a coincidence; it's crucial to how the whole algorithm works. Because the period is a divisor of the number of computational basis states, reversing their order has a negligible effect on the state. Therefore there is little difference between using the QFT and the inverse QFT, because $$\text{QFT}^{-1} = \text{QFT} \cdot \text{QFT}^{-1} \cdot \text{QFT}^{-1} = \text{QFT} \cdot \text{Mul}(-1)$$.