# Phase estimation algorithm: Modulo part in Nielsen and Chuang

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.

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.
• 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. Oct 29 '21 at 8:27
• @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. Oct 29 '21 at 9:37
• 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)$? Oct 29 '21 at 10:21