# John Lindsay Orr

$\newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\RR}{\mathbb{R}} \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 where, as usual $N=2^n$ for an $n$ qubit circuit. Apply the adjoint $F^*$ of $F$, where $F$ is the Fourier transform. Then

Thus we measure outcome $j$ with probability 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 where $|\lambda|=1$ and using the identity $\sin\phi = (e^{\i\phi} - e^{-\i\phi})/2i$. Thus we measure outcome $j$ with probability 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 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$, Thus the probability of measuring this value of $j$ is Thus we can summarize