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

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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