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 \]