# Derivation of efficiency of Phase Estimation Algorithm

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

In order to obtain Eq. 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. 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,

$$-2^{t-1}

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

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}. 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).
• Could you please elaborate on the reasoning. My understanding is that $−𝑎<−𝑥≤𝑎$ and $0≤𝑦≤𝑏⟹−𝑎<−𝑥≤𝑎+𝑏$. With this argument the inequality is $-𝜋<2𝜋(𝛿−𝑙/2𝑡)≤𝜋+\pi/2^t$, right ? Nov 24 '21 at 8:28