# Phase estimation algorithm: probability bound of obtaining $m$

Note: Cross-posted on Physics SE.

Hi, I'm studying the quantum phase estimation algorithm from this book: M.A. Nielsen, I.L. Chuang, "Quantum Computation and Quantum Information", Cambridge Univ. Press (2000) [~p. 221].

He defines $$b$$ as the integer in the range $$0$$ to $$2^t-1$$ such that $$\frac{b}{2^t}$$ is the best t bit approximation to $$\varphi$$ (the phase that we want to estimate).

From the first part of the circuit we have this state:

$$\frac{1}{2^{t/2}} \sum\limits_{k=0}^{2^t-1} e^{2 \pi i \varphi k}|k\rangle$$

Applying the inverse quantum Fourier transform we have:

$$\frac{1}{2^t} \sum\limits_{k,l=0}^{2^t-1} e^{\frac{-2\pi i k l}{2^t}} e^{2 \pi i \varphi k} |l\rangle$$

Then he define $$\alpha_l$$ as the amplitude of $$|(b+l) \bmod{2^t}\rangle$$

Then we want to bound the probability of obtaining a value of $$m$$ such that $$|m-b|>e$$

$$\sum\limits_{-2^{t-1} < l \le -(e+1)} |\alpha_l|^2 + \sum\limits_{e+1 \le l \le 2^{t-1}} |\alpha_l|^2$$

I understand the end with $$e$$ but not the one with $$2^{t-1}$$

• Thanks, the doubt is correct. I have understood what you say but why not $l \le 2^t -1$ – MementoMori Mar 26 '19 at 8:31

If I'm interpreting your confusion correctly. You're thinking you just need to say $$e+1 \leq l$$ not the $$l \leq 2^{t-1}$$ part. After all there is no such coefficient as $$\alpha_{100000}$$ if $$t$$ is only 3 for example. All that $$2^{t-1}$$ is doing is making sure there are only $$2^t$$ coefficients. That is it is a qudit with $$d=t$$. Is that your confusion?
Change the indexing from 0 to $$2^t$$ as you have already by subtracting $$2^{t-1}$$ so you get $$-2^{t-1}$$ to $$2^{t-1}$$ instead.
l just has to be indexed by a fundamental domain of modulo $$2^{t}$$ so 0 to $$2^t$$ works just as well as $$-2^{t-1}$$ to $$2^{t-1}$$. The answer just looks symmetrical with the second.