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

Below is the implementation circuit taken from the above-mentioned site:

enter image description here

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!

  • $\begingroup$ Thank you for the excellent answer and the useful resource, it indeed cleared up my doubts! $\endgroup$ – Übermensch Apr 19 '20 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.