Joan Lindsay Orr

$$\newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\RR}{\mathbb{R}} \newcommand{\TT}{\mathbb{T}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\H}{\mathcal{H}} \newcommand{\e}{\epsilon} \newcommand{\x}{\mathbf{x}} \newcommand{\y}{\mathbf{y}}$$

$$\newcommand{\i}{\textbf{i}} \newcommand{\ket}[1]{|#1\rangle}$$

Quantum Phase Estimation

Let $$U$$ be a unitary operator and let $$e^{i\theta}$$ be in the spectrum of $$U$$. We use a mix of Walsh-Hadamard gates and controlled-$$U$$ gates to prepare the state $y := N^{-\frac{1}{2}}\sum_{k=0}^{N-1} e^{\i\theta k} \ket{k}$ where, as usual $$N=2^n$$ for an $$n$$ qubit circuit. Apply the adjoint $$F^*$$ of $$F$$, where $$F$$ is the Fourier transform. Then

$\begin{eqnarray} F^*y &=& \frac{1}{N} \sum_{j=0}^{N-1}\sum_{k=0}^{N-1} e^{-2\pi \i jk / N} e^{\i \theta k} \ket{j} \\ &=& \frac{1}{N} \sum_{j=0}^{N-1}\left(\sum_{k=0}^{N-1} e^{\i(\theta - 2\pi j / N)k}\right) \ket{j} \end{eqnarray}$

Thus we measure outcome $$j$$ with probability $\left|\frac{1}{N} \sum_{k=0}^{N-1} e^{\i(\theta - 2\pi j / N)k}\right|^2$ We are interested in $$2\pi\frac{j}{N}$$ as an $$n$$-bit approximation to $$\theta$$ and so we write $$s := \theta - 2\pi\frac{j}{N}$$. Calculate $\begin{eqnarray} \sum_{j=0}^{N-1} e^{\i sj} &=& \frac{e^{\i Ns} - 1}{ e^{\i s} - 1} \\ &=& \left(\frac{e^{-\i s/2}}{e^{-\i s/2}}\right) \left(\frac{e^{-\i Ns/2}}{e^{-\i Ns/2}}\right) \frac{e^{\i Ns} - 1}{ e^{\i s} - 1} \\ &=& \left(\frac{e^{-\i s/2}}{e^{-\i Ns/2}}\right) \frac{e^{\i Ns/2} - e^{-\i Ns/2}}{e^{\i s/2} - e^{-\i s/2}} \\ &=& \lambda \frac{\sin(Ns/2)}{\sin(s/2)} \end{eqnarray}$ where $$|\lambda|=1$$ and using the identity $$\sin\phi = (e^{\i\phi} - e^{-\i\phi})/2i$$. Thus we measure outcome $$j$$ with probability $\frac{1}{N^2}\frac{\sin^2(Ns/2)}{\sin^2(s/2)}$ Observe that is is equal to $$\frac{1}{N}K_N(s)$$ where $$K_N(s)$$ is the Fejér Kernel.

Another way of seeing this is to observe that the probability of measuring $$j$$ is $\begin{eqnarray} \left|\frac{1}{N} \sum_{k=0}^{N-1} e^{\i sk}\right|^2 &=& \frac{1}{N^2} \sum_{k=0}^{N-1}\sum_{l=0}^{N-1} e^{\i(k-l)s} \\ &=& \frac{1}{N^2} \sum_{r=-N+1}^{N-1}(n - |r|) e^{\i rs} \\ &=& \frac{1}{N} C_N(s) \end{eqnarray}$ where $$C_N$$ can be recognized as the $$N$$'th Cesàro Mean of the formal Fourier Series $$\sum_{k=-\infty}^\infty e^{\i ks}$$ and from elementary Fourier Analysis this is equal to the Fejér Kernel, $$K_N(s)$$.

Now observe that since $$0\le \theta < 2\pi$$ and $$0\le j < N$$, there is a value of $$j$$ such that $$|s| = |\theta - 2\pi j/N| < \pi/N$$. But thus both $$|s/2|$$ and $$|Ns/2|$$ are less than $$\pi/2$$ and for any $$|\phi|<\pi/2$$, $\frac{2|\phi|}{\pi} < |\sin\phi | < |\phi|$ Thus the probability of measuring this value of $$j$$ is $\frac{1}{N^2}\frac{\sin^2(Ns/2)}{\sin^2(s/2)} \ge \frac{1}{N^2} \left(\frac{Ns}{\pi}\right)^2\left(\frac{2}{s}\right)^2 =\frac{4}{\pi^2} > 0.4$ Thus we can summarize $P\left(\left|\theta - \frac{2\pi j}{N}\right| < \frac{\pi}{N}\right) \ge 0.4 \quad\text{or}\quad P\left(\left|j - \frac{N\theta}{2\pi}\right| < \frac{1}{2}\right) \ge 0.4$