2
$\begingroup$

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!

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for pointing towards where to prove the second equation, I appreciate your help! $\endgroup$ Jun 5, 2022 at 4:15

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.