Phase estimation algorithm: probability bound of obtaining $m$

Question

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

Answer 1

Was a clarifying comment:

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?

Continuing from there:

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.