On the Complexity of Shor's Algorithm for Factorization
Zhengjun Cao, Lihua Liu · 2009
The complexity analysis of Shor's quantum algorithm for factorization consists of: 1) The probability p that we see any particular state\c, xk(mod n)) with {rc}q¿ r/2 is at least 1/3r2. 2) There are ¿(r) possible values of c, and r possible values of xk(mod n). 3) The success probability is at least ¿(r) · r · 1/3r2. That is, the inventor views p as the joint probability P(X = c, Y = xk(mod n)). In this paper, we show that the argument for the estimation of P(X = c, Y = xk(mod n)) is not sound. Therefore, the problem that Shor's algorithm takes polynomial time remains open.