Phase estimation algorithm: Modulo part in Nielsen and Chuang

Question

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.

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.