求根问题的量子计算算法  

Quantum Mechanical Algorithms for Solving Root Finding Problem

作　　者：孙国栋[1] 苏盛辉[1] 徐茂智[1,2] 

机构地区：[1]北京工业大学计算机学院,北京100124 [2]北京大学数学科学学院,北京100871

出　　处：《北京工业大学学报》2015年第3期366-371,共6页Journal of Beijing University of Technology

基　　金：国家"973"计划重点资助项目(2007CB311100);国家"863"计划资助项目(2009AA01Z441)

摘　　要：求根问题是计算数论中的一个困难性问题,为了提高求根问题的求解效率和扩大量子计算的应用范围,对求根问题进行了量子算法的分析.在两大量子算法Shor算法和Grover算法的基础上,提出了2种解决求根问题的量子算法RF-Shor算法和RF-Grover算法.经分析,RF-Shor算法需要多项式规模的量子门资源,能以接近1的概率求出求根问题的所有解.在没有使用任何可提高搜索效率的经典策略的情况下,RF-Grover算法能在O(M/k)步内以至少1/2的概率求出求根问题k个解中的一个解.Root finding problem is a hard problem in computational number theory. To improve the efficiency of solving the problem and expand the scope of applications of quantum computing,the quantum algorithms for solving the root finding problem are analyzed in this paper. Based on the two important quantum algorithms—Shor＇s algorithm and Grover＇s algorithm, two quantum mechanical algorithms are proposed to solve the root finding problem,which are named RF-Shor algorithm and RFGrover algorithm. According to the analysis,the RF-Shor algorithm can find all the solutions to the root finding problem with a probability closed to 100%,with a consumption of polynomial quantum gates; the RF-Grover algorithm does not involve any classical method to improve the search efficiency and one of the k solutions to the root finding problem can be obtained in O（M/k） steps with a probability of at least50%.

关 键 词：量子算法 求根问题 Shor算法 GROVER算法 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]