2
$\begingroup$

I'm reading Ronald de Wolf's lecture notes and when explaining Shor's algorithm on page 40 after applying a QFT to

$$ \frac{1}{\sqrt{m}} \sum_{j=0}^{m-1} |jr+s\rangle $$

the following expression is shown to describe the state of the first register: $$ \frac{1}{\sqrt{m}} \sum_{j=0}^{m-1} \frac{1}{\sqrt{q}} \sum_{b=0}^{q-1} e^{\frac{2\pi i(jr+s)b}{q}} |b\rangle = \frac{1}{\sqrt{mq}} \sum_{b=0}^{q-1} e^{\frac{2\pi isb}{q}} \left( \sum_{j=0}^{m-1} e^{\frac{2\pi ijr b}{q}} \right) |b\rangle $$

Soon after when looking at the case where $r$ divides $q$ it is noted that every $b$ for which $e^{\frac{2\pi ijr b}{q}}$ is $1$ the inner sum will equal $m$, resulting in these $b$ outcomes having a squared amplitude of $(m/\sqrt{mq})^2=1/r$. I don't understand at what point the $e^{\frac{2\pi isb}{q}}$ exponential got lost, I would assume that it must be 1 for all $b$ and $q$ but I don't see how.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

The amplitude for these $|b\rangle$ will be $$\left|\frac{me^{\frac{2\pi i s b}{q}}}{\sqrt{mq}} \right|^2 = \frac{1}{r}\left|e^{\frac{2\pi i s b}{q}}\right|^2 = \frac{1}{r}$$

since $|e^{ix}| = |\cos(x)+i\sin(x)| = \sqrt{\cos^2(x) + \sin^2(x)}=1$ for every $x\in \mathbb{R}$. Here $x=\frac{2\pi sb}{q}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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