5 of 8

# What is complexity of order-finding (classically) and success probability of Shor's algorithm?

I’m recently studying the Shor’s algorithm and got confused about the matter of complexity.

What I have read through that Shor’s algorithm reduce the factorization problem to order-finding problem or period of modular exponentiation sequence of some random x such that 1 < x N.

I have no problem about the idea of an algorithm. But wondering that if Shor’s algorithm creates such a sequence by repeated squaring which is can an efficient way classically

In my understand the efficient mean that the complexity of algorithm is polynomial in time of a problem.

So if there is efficient way to do create the sequence classically, then can we just add a little check if we have encountered $$x^{r} = 1 mod N$$ or not during the creating process it should not increase complexity to be exponential-time right? Why bothering Quantum Fourier transform at all ?

Or I miss understand its in some way.

And the next question is when one what to obtain a period from measurement result by using an continued fraction approximation. By consider an example of N = 21 and random number to construct a modular exponentiation sequence is x = 2 from (Shor's Algorithm for Factoring Large Integers)1 then this paper state that

There are six possible result after measuring the state after quantum Fourier transform which is

0 return period —> fail , 85 return period —> 6 , 171 return period —> 3 , 256 return period —> 2 , 341 return period —> 3 , 427 return period —> 6

Which the expect result should be 6

It can be see that the probability that the algorithm successfully return the right answer in the first run is around 33%

But the paper state that if the measurement return third to fifth possibly result (171,256,341) that is a factor of a period ($$r = r_{1}r_{2}$$) you can use $$2^r mod 21$$ be a new $$x$$ to run an algorithm again which there is some probability of return other factor of period ($$r_{2}$$) so the sum-up probability of successfully return period r is around 61% (in paper is 55% but I tried calculate myself is 61%, sorry if any mistake)

So the second question is which way is more efficient or right way to do this, either run algorithm again with new random $$x$$ or to correct the period with $$x = 2^{r_{1}} mod N$$

And what is probability of return the right answer for other $$N$$ and $$x$$ of Shor’s algorithm in either way and maybe proof of such a probability.