I'm trying to figure out the Shor's factoring algorithm. References i've been using wikipedia page, the book Quantum Computer Science by David Mermin and the orignal paper(1996) By Peter Shor. I understand the basics of this algorithm, but wanted to know the details about the math working behind it. Now While reading through the paper i was unable to understand few things, they are:-

  • In page 17, the probability[equation 5.7 & 5.8] was changed from summation to integral by introducing a error term in big-O notation and stating that $\{rc\}_q$ is small enough. Now my question is how it is done? I know that O(.) can be used to quantify algorithmic complexities. $$ \Biggl|\frac{1}{q} \sum_{b=0}^{\left \lfloor \frac{ q-k-1}{r}\right \rfloor}\exp{(2i\pi b \{rc\}_q/q})\Biggr|^2$$ $$ \frac{1}{q} \int_0^{\left \lfloor \frac{ q-k-1}{r}\right \rfloor} \exp{(2i\pi b \{rc\}_q/q})db + O\Biggl(\frac{\left \lfloor \frac{ q-k-1}{r}\right \rfloor}{q}(\exp{(2i\pi b \{rc\}_q/q})-1) \Biggr)$$ Also it said

If $|\{rc\}_q| ≤ \frac{r}{2}$, the error term in the above expression is easily seen to be bounded by O(1/q).

I could not understand how the above statement is true?

  • In page 18

this probability is thus asymptotically bounded below by $\frac{4}{\pi^2r^2}$, and so is at least $\frac{1}{3r^2}$ for sufficiently large n.

I get the $\frac{4}{\pi^2r^2}$ part and how it is coming into picture, but what i dont get is $\frac{1}{3r^2}$,
How it is at least $\frac{1}{3r^2}$ for large n?

  • Also i was wondering if it is possible to get the condition $|\frac{c}{q} - \frac{d}{r}| \le \frac{1}{2q}$ from the probability calculated from the actual summation that is $$P(c) = \frac{1}{q^2} \frac{\sin^2{(\frac{\pi mrc}{q})}}{\sin^2{(\frac{\pi rc}{q})}}$$ Where $m\approx \frac{Q}{r}$.

It would be really helpful if anybody can help me clear my doubts. Thanks in advance!!

  • $\begingroup$ it would be great if you could also try to specify what is the actual question in the question's title $\endgroup$ – glS Oct 12 '20 at 21:22
  • $\begingroup$ @gls there three parts in the whole question,as you can see. Including in the title will be messy. $\endgroup$ – Saptarshi Sahoo Oct 13 '20 at 5:36
  • 2
    $\begingroup$ and that's a problem in itself. You should ask a single question per post. Multiple questions in the same post make the question of low reusability $\endgroup$ – glS Oct 13 '20 at 12:59
  • $\begingroup$ Please obey gIS and split your question into 3 separate questions, or your question will surely be closed and quite possibly will be deleted. $\endgroup$ – user1271772 Oct 18 '20 at 19:08
  1. The Big-O notation $O(\cdot)$ is commonly used to describe algorithmic complexity classes, but it is a general notation used in math to denote asymptotic behavior of functions and sequences. It is convenient to use when you don't want / don't care to keep track of constants. In this context, what the big-O notation means in that equation, is that the value of the sum and the value of the integral are equal, up to an error which depends linearly on what it is inside the $O(\cdot)$. There is nothing special going on here, this is the usual approximation of an integral by Riemann sums. (Reading the paper, I believe that the author is only approximating the sum with the integral, so he is not considering the absolute-value-squared yet. He will do it later in the proof).

  2. This is again a statement about asymptotic behavior of functions. $4/\pi^2$ is roughly $0.4...$, which is larger than $1/3$. The probability is bounded from below by this quantity, but only asymptotically: it could be smaller at first, but sufficiently large $n$ is cannot go below that threshold, and therefore it cannot also go below $1/3r^2$.

  3. I am not quite sure what your third question is.

  • $\begingroup$ Thank you so much for your explanation. The third point means that if you calculate the probability given by the summation form, then we will get the $P(c)$. Now as you know the inequality I've given their is derived from the integral ( details can be found in the paper). So I was asking if it is possible to derive the same inequality from the P(c) ? $\endgroup$ – Saptarshi Sahoo Oct 12 '20 at 18:23

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