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)|$.


$$ -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} $$

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}<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).

  • $\begingroup$ 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 ? $\endgroup$
    – Sooraj S
    Nov 24 '21 at 8:28
  • $\begingroup$ Oh, I'm sorry. I somewhat lost track of what it was you were doing and what the book did. Yes, I agree with what you did. $\endgroup$
    – DaftWullie
    Nov 24 '21 at 9:08
  • $\begingroup$ @P_Gate That's a very different question. Please ask it separately. $\endgroup$
    – DaftWullie
    Nov 24 '21 at 9:09
  • $\begingroup$ @SoorajS Hopefully that now explains the extra step you needed. $\endgroup$
    – DaftWullie
    Nov 24 '21 at 9:16

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.