While trying to understand Shor's algorithm, I encountered this formula:

$p(y) = \frac{1}{2^nm}\big|\sum^{m-1}_{k=0}e^{2\pi ikry/2^n}\big|^2$. Now for $y=j2^n/r+\epsilon$, according to my textbook, the probability $p(y)$ can be simplified to $p(j2^n/r+\epsilon)=\frac{1}{2^nm}\frac{sin^2(\pi \epsilon mr/2^n)}{sin^2(\pi\epsilon r/2^n)}$ using the geometric series. I know that $sin x = \frac{e^{ix} - e^{-ix}}{2i}$ but I only get to this result:

$p(j2^n/r+\epsilon)=\frac{1}{2^nm}\big|\sum^{m-1}_{k=0}e^{2\pi ikr\epsilon/2^n}=\frac{1}{2^nm}\big|\frac{e^{2\pi imr\epsilon/2^n}-1} {e^{2\pi ir\epsilon /2^n}-1}\big|^2 = \frac{1}{2^nm}\big|\frac{e^{2\pi mr i\epsilon/2^{n+1}}(e^{2\pi i\epsilon mr /2^{n+1}}-e^{-2\pi mr i \epsilon /2^{n+1}})} {e^{2\pi ir\epsilon/2^{n+1}}(e^{2\pi ir\epsilon /2^{n+1}}-e^{-2\pi ir\epsilon /2^{n+1}})}\big|^2=\frac{1}{2^nm}\frac{\sin^2(\pi \epsilon mr /2^{n+1})}{\sin^2(\pi \epsilon r /2^{n+1})}$.

The problem is the $2^{n+1}$ as opposed to $2^n$ in the textbook.

  • $\begingroup$ also the fractions get quite unreadable here. Any tips on latex formatting? $\endgroup$ – jvdh Jan 29 at 14:19
  • $\begingroup$ okay, that was just a simple error of not seeing the 2 in front of the $\pi$, lol. how should I proceed when I have answered my own question? $\endgroup$ – jvdh Jan 30 at 5:38

Your Answer

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

Browse other questions tagged or ask your own question.