In the order finding circuit, why is the equal superposition of the controlled unitary eigenstates the $|1\rangle$ state?

Question

In Nielsen and Chuang's "Quantum Computation and Quantum Information" when the quantum order finding process is being presented (specifically page 227, equation 5.44) we are told that by "clever observation" we can see that $$ \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} |u_s\rangle = |1\rangle \tag{5.44} $$ Can someone explain how this we arrive at this statement? Thank you in advance!

Answer 1

$\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\xkmodn}{\ket{x^k \ mod \, N}}$By definition, $$\ket{u_s} = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1} e^{-2\pi i \frac{sk}{r}}\xkmodn$$.

Thus,

$$\begin{split} \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\ket{u_s} &= \frac{1}{r} \sum_{s=0}^{r-1} \sum_{k=0}^{r-1} e^{-2\pi i \frac{sk}{r}} \xkmodn \\ &= \frac{1}{r} \sum_{k=0}^{r-1} \sum_{s=0}^{r-1} e^{-2\pi i \frac{sk}{r}} \xkmodn \\ &= \frac{1}{r} \sum_{k=0} \sum_{s=0}^{r-1} e^{-2\pi i \frac{sk}{r}} \xkmodn + \frac{1}{r} \sum_{k=1}^{r-1} \sum_{s=0}^{r-1} e^{-2\pi i \frac{sk}{r}} \xkmodn \\ &= \frac{1}{r} \sum_{s=0}^{r-1} \ket{1} + \frac{1}{r} \sum_{k=1}^{r-1} \frac{1-e^{-2\pi i k}}{1-e^{-2\pi i \frac{k}{r}}} \xkmodn \\ &= \ket{1} + \frac{1}{r} \sum_{k=1}^{r-1} \frac{1-e^{-2\pi i k}}{1-e^{-2\pi i \frac{k}{r}}} \xkmodn \end{split}$$ Note that $e^{-2\pi i k}$ will always evaluate to $1$ when $k$ is an integer (which it is). Furthermore, we are not in danger of a divide by zero, as $e^{-2\pi i \frac{k}{r}}$ will never evaluate to $1$ because of $\frac{k}{r}$. Thus, the right term will evaluate to zero, leaving us with $$\frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \ket{u_s} = \ket{1}$$.

Answer 2

You can check that the eigenvectors of the unitary $U$ have the form $$|u_s\rangle=\frac{1}{\sqrt{r}}\sum_{t=0}^{r-1}\omega^{-st}|x^t\rangle,$$ for each $s\in \{1,\ldots,r\}$ with eigenvalues $\omega^s$ where $\omega=e^{2\pi/r}$ and $x\in \mathbb{Z}_N$.

The key observation required to see that (5.44) is true is that $\omega^0=1$ and that for all other $t\in \{1,\ldots,r-1\}$ $$\sum_{s=1}^{r-1}\omega^{-st}=0.$$ (You can prove this with a geometric series argument or learning more about the roots of unity).

Then expanding we see that \begin{align*} \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|u_s\rangle&=\frac{1}{r}\sum_{s=0}^{r-1}\sum_{t=0}^{r-1}\omega^{-st}|x^t\rangle\\ &=\frac{1}{r}\sum_{t=0}^{r-1}\left(\sum_{s=0}^{r-1}\omega^{-st}\right)|x^t\rangle\\ &=\frac{1}{r}\left(r|1\rangle+\sum_{t=1}^{r-1}\left(\sum_{s=0}^{r-1}\omega^{-st}\right)|x^t\rangle\right)\\ &=\frac{1}{r}\left(r|1\rangle+\sum_{t=1}^{r-1}\left(0\right)|x^t\rangle\right)\\ &=|1\rangle. \end{align*} Where in the second line we have swapped the order of summation, and in the third line we have separated the $t=0$ term from the $1\leq t\leq r-1$ terms.