In Nielsen and Chuang the explanation of phase estimation states:

We have the following state:

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

Now we apply the inverse Fourier transform to it and get:

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

Now the following assumption is made, or the following is stated: "Let $\alpha_l$ be the amplitude of $|(b+l)(\text{mod }2^t)\rangle$", thus we now obtain:

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

My first question is, how does one come to say that "Let $\alpha_l$ be the amplitude of $|(b+l)(\text{mod }2^t)\rangle$" is valid? Specifically, I am interested in how one comes up with the modulo part.

My second question then refers to the last equation, how does the transition from equation 5.23 to equation 5.24 occur?

I hope my question is understandable so far.


1 Answer 1


Let us consider the following state, described in Equation 5.23: $$\frac{1}{2^t} \sum_{k,l=0}^{2^t-1} \mathrm{e}^{\frac{-2\pi i k l}{2^t}} \mathrm{e}^{2 \pi i \varphi k} |l\rangle$$ This can also be written as: $$\sum_{l=0}^{2^t-1}\left(\frac{1}{2^t}\sum_{k=0}^{2^t-1}\mathrm{e}^{2\mathrm{i}\pi k\left(\varphi-\frac{l}{2^t}\right)}\right)|l\rangle$$ Ideally, we would like to measure the state $|b\rangle$. It is however possible that we measure some state $|b+l\rangle$, with $l$ being the distance between our ideal state and our measured state. Thus, it makes sense to rewrite the previous state as a superposition over the $|b+l\rangle$ basis states. This simply corresponds to shifting the previous sum by an offset equal to $b$. Preventing $b+l$ from being larger than $2^t-1$, we can rewrite this state as: $$\sum_{l=0}^{b-1}\left(\frac{1}{2^t}\sum_{k=0}^{2^t-1}\mathrm{e}^{2\mathrm{i}\pi k\left(\varphi-\frac{l}{2^t}\right)}\right)|l\rangle+\sum_{l=0}^{2^t-b-1}\left(\frac{1}{2^t}\sum_{k=0}^{2^t-1}\mathrm{e}^{2\mathrm{i}\pi k\left(\varphi-\frac{l+b}{2^t}\right)}\right)|l+b\rangle$$ You can see the definition of $\alpha_l$ appear in the rightmost sum. Now, let us consider the state $|l\rangle$ for $0\leqslant l\leqslant b-1$. We have that: $$l=\left[\left(2^t-b+l\right)+b\right]\left(\mathrm{mod}\ 2^t\right)$$ Let us define $j$ to be: $$j = 2^t-b+l$$ so that $l$ can be written as: $$l=(j+b)\left(\mathrm{mod}\ 2^t\right)$$ Note that for $l$ going from $0$ to $b-1$, $j$ goes from $2^t-b$ to $2^t-1$. This allows to rewrite this state as: $$\sum_{j=2^t-b}^{2^t-1}\left(\frac{1}{2^t}\sum_{k=0}^{2^t-1}\mathrm{e}^{2\mathrm{i}\pi k\left(\varphi-\frac{(j+b)\left(\mathrm{mod}\ 2^t\right)}{2^t}\right)}\right)|(j+b)\left(\mathrm{mod}\ 2^t\right)\rangle+\sum_{l=0}^{2^t-b-1}\left(\frac{1}{2^t}\sum_{k=0}^{2^t-1}\mathrm{e}^{2\mathrm{i}\pi k\left(\varphi-\frac{(l+b)\left(\mathrm{mod}\ 2^t\right)}{2^t}\right)}\right)|(l+b)\left(\mathrm{mod}\ 2^t\right)\rangle$$ We can see that these sums have the same general term, so we can gather them be redefining $l$ to be equal to $j$ in the first one. Thus, $\alpha_l$ is by definition equal to: $$\alpha_l=\frac{1}{2^t}\sum_{k=0}^{2^t-1}\mathrm{e}^{2\mathrm{i}\pi k\left(\varphi-\frac{(l+b)\left(\mathrm{mod}\ 2^t\right)}{2^t}\right)}$$ Finally, we can write: $$(l+b)\left(\mathrm{mod}\ 2^t\right) = l+b - q\times2^t$$ Thus: $$\begin{align*} \alpha_l&=\frac{1}{2^t}\sum_{k=0}^{2^t-1}\mathrm{e}^{2\mathrm{i}\pi k\left(\varphi-\frac{l+b}{2^t}+q\right)}\\ &=\frac{1}{2^t}\sum_{k=0}^{2^t-1}\mathrm{e}^{2\mathrm{i}\pi k\left(\varphi-\frac{l+b}{2^t}\right)}\underbrace{\mathrm{e}^{2\mathrm{i}\pi k q}}_{1} \end{align*}$$ which finally gives you the definition of $\alpha_l$ as described in Equation 5.24.

  • $\begingroup$ Thank you for the answer in which there are many details (+1)! I have one more question about your answer. You introduce next $l=\left[\left(2^t-b+l\right)+b\right]\left(\mathrm{mod}\ 2^t\right)$, to me this is equivalent to $l=l\left(\mathrm{mod}\ 2^t\right)$, however I don't see exactly how this is helpful here. I would be grateful if you could perhaps make this a little clearer. $\endgroup$
    – P_Gate
    Oct 29, 2021 at 8:27
  • 1
    $\begingroup$ @P_Gate I've edited my answer, please tell me if there's something you still don't understand. Essentially, writing it like this allows to see that the state $|l\rangle$ for $0\leqslant l\leqslant b-1$ is created by shifting the state $\left|2^t-b+l\right\rangle$ by an offset equal to $b$. This allows us to derive the bounds of the first sum to gather them later. $\endgroup$ Oct 29, 2021 at 9:37
  • $\begingroup$ Thanks for the clarification that really helped me. A short question: If you have defined the $l=(j+b)\left(\mathrm{mod}\ 2^t\right)$ in this way (understandable), then it should be $|(j+b)\left(\mathrm{mod}\ 2^t\right)$ in the first sum, instead of $|(l+b)\left(\mathrm{mod}\ 2^t\right)$? $\endgroup$
    – P_Gate
    Oct 29, 2021 at 10:21
  • 1
    $\begingroup$ @P_Gate You're totally right, I just forgot to update the state accordingly $\endgroup$ Oct 29, 2021 at 10:49
  • $\begingroup$ For your effort and very helpful reply, I mark this as a answer. $\endgroup$
    – P_Gate
    Oct 29, 2021 at 11:51

Your Answer

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

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