3
$\begingroup$

I'm studying Shor algorithm. This is a demostration about the eigenvectors and eigenvalues of $U_a$ gate:

Can somebody explain me from the third step to the last?

$\endgroup$
3
$\begingroup$

You have the state $$ \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}e^{-2\pi i\frac{k}{r}(s+1)}|a^{s+1}\text{ mod }N\rangle. $$ Perform a change of variable $p=s+1$ so this simply reads $$ \frac{1}{\sqrt{r}}\sum_{p=1}^{r}e^{-2\pi i\frac{k}{r}p}|a^p\text{ mod }N\rangle. $$ Now consider for a moment that $p=r$ term, $$ e^{-2\pi i\frac{k}{r}r}|a^r\text{ mod }N\rangle=|a^r\text{ mod }N\rangle. $$ By definition, $a^r\equiv 1\text{ mod }N$, which we could also write as $a^0$. Hence, this term is exactly the same as using $p=0$ instead. Thus, the state has become $$ \frac{1}{\sqrt{r}}\sum_{p=0}^{r-1}e^{-2\pi i\frac{k}{r}p}|a^p\text{ mod }N\rangle, $$ which is $|w_k\rangle$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much! I forgot to add more details (Next time I should write "from the second step") : why at start there's this exponantial (positive) outside the summation and why the "s" in the exponational inside summation became "(s+1)" ? $\endgroup$ – Quarzo Aug 28 at 19:36
  • 1
    $\begingroup$ because those two things cancel. $\endgroup$ – DaftWullie Aug 29 at 6:55
  • $\begingroup$ Really, thank you! $\endgroup$ – Quarzo Aug 29 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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