Derivation of efficiency of Phase Estimation Algorithm

Question

In the section Performance and requirements of the phase estimation algorithm of Page 224, Quantum Computation and Quantum Information by Nielsen and Chuang

---

Let $b$ be the integer in the range $0$ to $2^t − 1$ such that $b/2^t = 0.b_1\cdots b_t=\frac{b_1}{2}+\frac{b_2}{2^2}\cdots\frac{b_t}{2^t}$ is the best $t$ bit approximation to the required phase $φ$, which is less than $φ$. \begin{align} b&=b_12^{t-1}+b_22^{t-2}+\cdots+b_t2^0=b_1b_2\cdots b_t\\ &\implies\frac{b}{2^t}={b_1}2^{-1}+{b_2}2^{-2}\cdots{b_t}2^{-t}=0.b_1b_2\cdots b_t\\ \phi&=0.\phi_1\phi_2\cdots\phi_t\phi_{t+1}\cdots\\ &=\phi_12^{-1}+\phi_22^{-2}+\cdots+\phi_{t-1}2^{-(t-1)}+\phi_t2^{-t}+\phi_{t+1}2^{-(t+1)}+\cdots\\ &=b_12^{-1}+b_22^{-2}+\cdots+b_{t-1}2^{-(t-1)}+\phi_t2^{-t}+\phi_{t+1}2^{-(t+1)}+\cdots\\ &\implies 0\leq\delta=\phi-\dfrac{b}{2^t}\leq 2^{-t} \end{align} That is, the difference $δ ≡ φ − b/2^t$ between $φ$ and $b/2^t$ satisfies $0 ≤ δ ≤ 2^{−t}$. We aim to show that the observation at the end of the phase estimation procedure produces a result that is close to b, and thus enables us to estimate $φ$ accurately, with high probability.

The final state of the first register in the phase estimation procedure is, $\dfrac{1}{2^{t/2}}\sum_{k=0}^{2^t-1}e^{2\pi i\phi k}|k\rangle$

The action of inverse quantum Fourier transform on the state $|j\rangle$ is that, $QFT^\dagger|j\rangle=\dfrac{1}{2^{t/2}}\sum_{k=0}^{2^t-1}e^{-2\pi ijk/2^t}|k\rangle$

Therefore, applying the inverse quantum Fourier transform to the final state of the first register in the phase estimation procedure is, \begin{align} QFT^\dagger\Big(\dfrac{1}{2^{t/2}}\sum_{k=0}^{2^t-1}e^{2\pi i\phi k}|k\rangle\Big)&=\dfrac{1}{2^{t/2}}\sum_{k=0}^{2^t-1}e^{2\pi i\phi k}QFT^\dagger|k\rangle\\ &=\dfrac{1}{2^{t/2}}\sum_{k=0}^{2^t-1}e^{2\pi i\phi k}\dfrac{1}{2^{t/2}}\sum_{l=0}^{2^t-1}e^{-2\pi ikl/2^t}|s\rangle\\ &=\dfrac{1}{2^{t}}\sum_{k,l=0}^{2^t-1}e^{2\pi i\phi k}e^{-2\pi ikl/2^t}|s\rangle \tag{5.23}\label{5.23} \end{align}

Let $\alpha_l$ be the amplitude of $|(b+l)(\mod 2^t)\rangle$ then from equation \ref{5.23}, we can see \begin{align} \alpha_l&=\dfrac{1}{2^{t}}\sum_{k}^{2^t-1}e^{2\pi i\phi k}e^{-2\pi ik(b+l)/2^t}\\ &=\dfrac{1}{2^{t}}\sum_{k=0}^{2^t-1}e^{-2\pi ik(\phi-(b+l)/2^t)}\\ &=\dfrac{1}{2^{t}}\sum_{k=0}^{2^t-1}\Big(e^{-2\pi i(\phi-(b+l)/2^t)}\Big)^k\tag{5.24} \end{align} This is a sum of a geometric progression with $a=1$ and $r=e^{-2\pi i(\phi-(b+l)/2^t)}$ for which $S_n=\dfrac{a(1-r^n)}{1-r}$ with $n=2^t$, so \begin{align} \alpha_l&=\frac{1}{2^t}\Big(\frac{1-e^{2\pi i(2^t\phi-(b+l))}}{1-e^{2\pi i(\phi-(b+l)/2^t)}}\Big)\tag{5.25}\\ &=\frac{1}{2^t}\Big(\frac{1-e^{2\pi i(2^t\delta-l)}}{1-e^{2\pi i(\delta-l/2^t)}}\Big)\tag{5.26}\\ \end{align} where $\delta=\phi-b/2^t$

Suppose the outcome of the final measurement is $m$. We aim to bound the probability of obtaining a value of $m$ such that $|m − b| > e$, where $e$ is a positive integer characterizing our desired tolerance to error. The probability of observing such an $m$ is given by $$ p(|m-b|>e)=\sum_{-2^{t-1}<l\le -(e+1)}|\alpha_l|^2+\sum_{e+1\le l\le 2^{t-1}}|\alpha_l|^2\tag{5.27}\label{5.27} $$ But for any real $θ$, $|1 − exp(iθ)| ≤ 2$, so $$ |\alpha_l|\le \frac{2}{2^t|1-e^{2\pi i(\delta-l/2^t)}|}\tag{5.28} $$ By elementary geometry or calculus $|1 − exp(iθ)| ≥ 2|θ|/π$ whenever $−π ≤ θ ≤ π$. But when $−2^t−1 < l ≤ 2^t−1$ we have $−π ≤ 2π(δ − l/2^t ) ≤ π$. Thus $$ |\alpha_l|\le \frac{1}{2^{t+1}(\delta-l/2^t)}\tag{5.29}\label{5.29} $$ Combining \ref{5.27} and \ref{5.29} gives $$ p(|m-b|>e)\le \frac{1}{4}\bigg[\sum_{l=-2^{t-1}+1}^{-(e+1)}\frac{1}{(l-2^t\delta)^2}+\sum_{l=e+1}^{2^{t-1}}\frac{1}{(l-2^t\delta)^2}\bigg]\tag{5.30} $$ Recalling that $0 ≤ 2^t δ ≤ 1$, we obtain \begin{align} p(|m-b|>e)&\le \frac{1}{4}\bigg[\sum_{l=-2^{t-1}+1}^{-(e+1)}\frac{1}{l^2}+\sum_{l=e+1}^{2^{t-1}}\frac{1}{(l-1)^2}\bigg]\tag{5.31}\\ &\le\frac{1}{2}\sum_{l=e}^{2^{t-1}-1}\frac{1}{l^2}\tag{5.32}\\ &\le \frac{1}{2}\int_{e-1}^{2^{t-1}-1}dl\frac{1}{l^2}\tag{5.33}\\ &=\frac{1}{2(e-1)}\tag{5.34} \end{align}

---

In order to obtain Eq. \ref{5.27} we have shifted the index $l$ by subtracting $2^{t-1}-1$, thereby changing the range $0\leq l\leq 2^t-1$ to $-2^{t-1}+1\leq l\leq 2.2^{t-1}-1-2^{t-1}+1$ or $-2^{t-1}+1\leq l\leq 2^{t-1}$ or $-2^{t-1}< l\leq 2^{t-1}$.

For deriving Eq. \ref{5.29} it seems to make use of the fact that $\sin|x|\geq 2|x|/\pi$ when $-\pi/2\leq x\leq\pi/2$ since $|1-\exp(i\theta)|=2|\sin(\theta/2)|$.

Now,

\begin{align} &-2^{t-1}<l\leq 2^{t-1} \quad\&\quad 0\leq \delta\leq 2^{-t}\\ &\implies -2^{-1}<-l/2^t\leq 2^{-1}\\ &\implies -2^{-1}<\delta-l/2^t\leq 2^{-1}+2^{-t}\\ &\implies -\pi<2\pi(\delta-l/2^t)\leq \pi+2\pi2^{-t} \end{align}

How do we obtain that $-\pi\leq 2\pi(\delta-l/2^t)\leq \pi$ ?

Answer 1

You've got two relevant conditions in that big block of text: \begin{align*} -2^{t-1}<&l\leq 2^{t-1} \\ 0 \leq&\delta\leq2^{-t} \end{align*} So, consider $\delta-l/2^t$. You have $$ -1/2\leq \delta-l/2^t<2^{-t}+1/2. $$ (Remember to be careful with which bounds you take. For the lower bound, you need to lower bound on $\delta$ and the upper bound on $l/2^t$.) Now just multiply through by $2\pi$.

The only problem compared to what N&C show is there's an extra $2\pi 2^{-t}$ term on the upper bound. However, note that the lower bound on $l$ was $-2^{t-1}<l$. So, since $l$ is an integer, we might equally write $-2^{t-1}+1\leq l$. This subtracts an extra $2\pi/2^t$ from the upper bound, which is exactly what you need (and now the upper bound contains the possibility of equality).