具有高概率的整数分解量子算法

摘要

本文基于量子Fourier变换给出了一个新的整数分解量子算法,通过利用多次量子Fourier变换和变量代换,使得r变成相位因子(r是从模N整数环中所选元素的阶),进而可使非零的非目标态的几率幅变为零,算法成功的概率大于3/4,高于Shor整数分解量子算法,且不再依赖于,的大小(Shor算法成功的概率依赖于r的大小),同时还将新算法的资源消耗情况与Shor算法进行了对比.%In this paper, based on the quantum Fourier transform, we give a new quantum algorithm for prime factorization.The algorithm tumns 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 O.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 Shot's algorithm.