Quantum Algorithm for Prime Factorization with High Probability
Zhong Pu-Cha · Dianzi xuebao · 2011
In this paper,based on the quantum Fourier transform,we give a new quantum algorithm for prime factorization.The algorithm turns r to be phase factor under repeated application of Fourier transform and variate transform,where r is the order of a selective element in the ring of integers modulo N.Furthermore the amplitude of the non-target states except zero state is modified to be 0.Our algorithm′s success probability,which is more than 3/4 and higher than Shor′s algorithm,doesn′t depend on the size of r other than Shor′s algorithm.Meanwhile,we present a comparison of the required resource between the new algorithm and Shor′s algorithm.