# How does Inverse QFT work in Quantum Phase Estimation?

I'm trying to implement Quantum Phase Estimation from qiskit textbook.

Below is the implementation circuit taken from the above-mentioned site: The output at position 2 will be as follows:

$$|\psi _2⟩ = \frac{1}{2^{\frac{n}{2}}} \sum_{k=0}^{2^{n}-1} e^{2\pi i k} |k⟩ ⊗ |\psi⟩$$

and after applying inverse QFT, the state becomes:

$$| \psi _3⟩ = \frac{1}{2^{n}} \sum_{x=0}^{2^{n}-1} \sum_{k=0}^{2^{n}-1} e^{- \frac{2 \pi i k}{2^{n}}(x-2^n \theta)} |x⟩ ⊗| \psi⟩$$

However, the next step claims that the above expression peaks near $$x = 2^n \theta$$ which is my point of doubt, why is this the case? Wouldn't the maximum amplitude be when $$x = 0$$ based on simple calculus?

The expression you obtain after applying the QFT contains sums of the unit square, $$e^{2\pi i/2^n}$$, which sum up to 0 if you sum over the full range of $$2^n$$:

$$\sum_{k=0}^{2^n - 1} e^{\frac{2\pi i}{2^n} k} = 0$$

See here for explanations why this is the case.

Now the inner sum in the amplitudes will also sum up to 0, if $$(x - 2^n\theta)$$ is an integer, because that's just multiplication with a constant factor and the sum-to-zero-rule still holds.

$$\sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} e^{\frac{2\pi i}{2^n} k (x - 2^n \theta)}$$

But: If $$(x - 2^n \theta) = 0$$, then the exponential will be $$e^0 = 1$$ and your sum is collapsing to

$$\sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} 1$$

Therefore, the amplitudes are 0 if $$x \neq 2^n \theta$$ and 1 if $$x = 2^n \theta$$. Note that the derivation is more complicated if $$2^n\theta$$ is not an integer.

The QFT and its derivation is also very well explained in Nielsen and Chuang, chapter 5.1, page 217, I would recommend to look up there if you have any questions!

• Thank you for the excellent answer and the useful resource, it indeed cleared up my doubts! Apr 19, 2020 at 9:32