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.


1 Answer 1


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<b$, 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}<m-b-2^t<0$. 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.

  • 1
    $\begingroup$ @P_Gate I've added a longer answer, please tell me if that answers your question $\endgroup$
    – Tristan Nemoz
    Commented Nov 1, 2021 at 13:23
  • $\begingroup$ 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! $\endgroup$
    – P_Gate
    Commented Nov 1, 2021 at 17:08
  • $\begingroup$ 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! $\endgroup$
    – P_Gate
    Commented Nov 1, 2021 at 17:10
  • $\begingroup$ @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. $\endgroup$
    – Tristan Nemoz
    Commented Nov 1, 2021 at 18:19
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tristan Nemoz
    Commented Nov 3, 2021 at 13:22

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.