# Phase estimation algorithm: Bounding of probability in Nielsen and Chuang

I am currently studying the Quantum Phase Estimation (QPE) algorithm as described in Nielsen and Chuang, pages 223-224. We have the following situation there, we have the state:

$$\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 \quad\text{(5.23)}$$

Then let $$\alpha_l$$ be the amplitude of $$|(b+l)(\text{mod }2^t)\rangle$$,

$$\alpha_l \equiv \frac{1}{2^t} \sum\limits_{k=0}^{2^t-1} \left(e^{2\pi i(\varphi - (b+l)/2^t)}\right)^k \quad\text{(5.24)}$$

We aim to bound the probability of obtaining a value of $$m$$ such that $$|m-b|>e$$, where $$e$$ is a positive integer characterizing our desired tolerance to error. The probability of observing such an $$m$$ is given by:

$$p(|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\quad\text{(5.27)}$$

Here we have reached an interesting point that raises a few questions for me.

From equation 5.23 we can see that the variable $$l$$ goes from $$0$$ to $$2^t -1$$. If I shift the index by subtracting $$-2^{t-1}$$, I get the following new bounds for $$l$$ from $$-2^{t-1}$$ to $$2^{t-1}-1$$. Now a couple of questions arise.

First, in the left-hand sum in equation 5.27 the index is $$-2^{t-1} \color{red}{<} l\leq -(e+1)$$, why is it less than and not less than or equal to (highlighted in red)?

Second, let's look at the right-hand sum notice that the index here is as follows $$e+1\leq l\leq \color{red}{2^{t-1}}$$, I have again marked in red, which is not understandable to me. Why is the upper limit of the sum $$2^{t-1}$$ here, shouldn't it actually be $$2^{t-1}-1$$?

I hope my questions are understandable so far.

Short answer: to answer both your questions, it is sufficient to note that: $$\alpha_{-2^{t-1}}=\alpha_{2^{t-1}}$$ Indeed, $$\alpha_l$$ is the amplitude of $$\left|(b+l)\left(\mathrm{mod}2^t\right)\right\rangle$$. As such, $$\alpha_l$$ and $$\alpha_{l+k\times2^t}$$ are equal for any $$k\in\mathbb{Z}$$.

Now, you can easily see that your proposal is in fact equivalent to the one presented in Nielsen and Chuang. Indeed, if you add the $$\left|\alpha_{-2^{t-1}}\right|^2$$ term and remove the $$\left|\alpha_{2^{t-1}}\right|^2$$, you essentially add and remove the same term.

You can basically separate your offsets in two categories: positive ones and negative ones. If $$m>b$$, the offset is positive. If $$m, it is negative. Note that the offset is simply defined as $$m-b$$.

The important thing to note is that if $$m-b>2^{t-1}$$, the offset is actually negative. Indeed, if we take for instance $$b=1$$ and $$m=2^{t}-2$$, then $$m-b=2^t-3$$, but by reducing it modulo $$2^t$$, we can see this as an offset of $$-3$$.

More generally, if $$m-b>2^{t-1}$$, then the offset we really consider is $$-2^{t-1}. This explains why we separate this expression in two sums: we consider positive offsets and negative offsets, and only when their absolute value is strictly larger than $$e$$.

Now, there is a corner case for $$m-b=\pm2^{t-1}$$. Indeed, an offset of $$2^{t-1}$$ is exactly the same as an offset of $$-2^{t-1}$$. Thus, this offset would be counted twice if we consider the sum from $$-2^{t-1}$$ to $$-(e+1)$$ and the sum from $$e+1$$ to $$2^{t-1}$$. It is thus necessary to remove either the $$-2^{t-1}$$ term in the first sum or the $$2^{t-1}$$ term in the second one. You can choose whatever convention you like: Nielsen and Chuang chose to do the former, while you wanted to do the latter.

• I agree with the first part! In the regular case, our amplitudes would be $\alpha_l$ with $l$ from $0$ to $2^t-1$, say $\alpha_0$ to $\alpha_7$, for $t=3$. Now we shift our indices and we introduce the modulo operator and we find that, for example, $-4 \text{ mod } 8 = 4$ and $4 \text{ mod } 8 = 4$. So it is enough to consider only one of them. I agree! Commented Nov 1, 2021 at 17:08
• On the second part, I agree with you with a few exceptions, first question, what makes you say $m-b>2^t - 1$? and secondly to infer a negative offset from that? Second question, if you say $m-b>2^{t-1}$, how exactly do you infer $-2^{t-1}<m-b-2^t<0$? I agree with you on the last part of the second part ;) Have many thanks! Commented Nov 1, 2021 at 17:10
• @P_Gate Sorry for the first question, it was actually a typo. For the second one, if since $m$ is a measured state, it is necessarily lower than $2^t$. As such, we necessarily have $m-b<2^t$. If we additionnally have $m-b>2^{t-1}$, then you can get the desired inequality by subtracting $2^t$ on any side. Commented Nov 1, 2021 at 18:19
• @P_Gate I'm using the "mathematical" definition of the modulo. For instance: $$2^3-3\mathrm{mod}\ 2^3=5\mathrm{mod}\ 2^3=-3\mathrm{mod}\ 2^3=5+k\times2^3\mathrm{mod}\ 2^3\ \forall k\in\mathbb{Z}$$ What you want is to choose the $k$ that represents the shortest distance from your disered point. Taking back your example, you can add $5$ to $b$ to get $m$, or you can subtract $3$ to $b$ to also get $m$, modulo $8$. You can think of it as a circle where the $2^t$ points are placed on it clockwise: the closest points to $2^t-1$ are $0$ and $2^t-2$, both at a distance of $1$ from it. Commented Nov 3, 2021 at 13:22