求根问题的量子计算算法

Quantum Mechanical Algorithms for Solving Root Finding Problem

求根问题是计算数论中的一个困难性问题,为了提高求根问题的求解效率和扩大量子计算的应用范围,对求根问题进行了量子算法的分析.在两大量子算法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%.