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

$\endgroup$
3
  • $\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 '20 at 19:36
  • 1
    $\begingroup$ because those two things cancel. $\endgroup$
    – DaftWullie
    Aug 29 '20 at 6:55
  • $\begingroup$ Really, thank you! $\endgroup$
    – Quarzo
    Aug 29 '20 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.