On the Complezity of Shors Algorithm for Factorization

摘要：

The complexity analysis of Shors quantum algorithM for factorization consists of: 1)The probability p that we see any particular statec, xk (modn)) with rcq≤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 (modn)). 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 Shors algorithm takes polynomial time remains open.

关键词： factorization Shors algorithm quantum register

作者: Zhengjun Cao Lihua Liu

作者单位: Department of Mathematics, Shanghai University Departement Dinformatique, Universite Libre de Bruxe Department of Mathematics, Shanghai Maritime University

会议类型: 国际会议

会议名称: Second International Symposium on Information Science and Engineering(第二届信息科学与工程国际会议)

会议地点: 上海

会议语种:英文

页码: 164-168

在线出版日期: 2009-12-26（万方平台首次上网日期，不代表论文的发表时间）