= Solution
The inverse <quantum Fourier transform> in the original PDF has matrix elements $N^{-1/2}e^{-2\pi iky/N}$ multiplying $|y\rangle\langle k|$. The converted TeX incorrectly repeats $y$ in the bra; using the actual PDF operator,
$$
F^\dagger|\psi\rangle
=\frac1N\sum_{y=0}^{N-1}\left(\sum_{x=0}^{N-1}e^{2\pi i(a-y)x/N}\right)|y\rangle.
$$
If $y=a$, every summand of the inner sum is one, so it equals $N$. If $y\ne a$, let $q=e^{2\pi i(a-y)/N}$. Then $q\ne1$ and $q^N=1$, and the finite <geometric series> gives $\sum_{x=0}^{N-1}q^x=(1-q^N)/(1-q)=0$. This is <orthogonality of roots of unity>. Hence
$$
\boxed{F^\dagger|\psi\rangle=|a\rangle.}
$$
A <quantum measurement in the computational basis> consequently returns the integer $a$ with probability one.
Back to article page
