改进的Grover量子搜索算法

Improved Grover's quantum searching algorithm

通过分析发现,经典的Grover算法在目标项个数为总搜索项个数的一半时迭代会失效,为此提出一种扩大搜索空间的改进Grover算法1,该算法在目标项个数未知的情况下自适应的调整迭代次数,可以有效避免算法失效;此外针对Grover算法在多次迭代后目标解的概率仍有可能达不到1的情况,提出了改进的Grover算法2。当目标项个数M和待搜索项个数N已知时,针对M/N>1/4的情况,对量子位进行了扩充,在一定情况下该算法只需迭代一次即可以100%的概率得到目标解。

Noting that the classical Grover's algorithm will fail when the number of targets is half of the total number of searches,an improved Grover algorithm 1 was proposed in this paper to enlarge the search space.In the case of unknown number of objects,this algorithm can adjust iteration times adaptively and avoid the failure of the algorithm effectively.In addition,in view of the probability of the target item smaller than 1 by using Grover algorithm after multiple iterations,an improved Grover algorithm 2 was proposed.When the number M of target items and the number N of items to be searched are known,the qubit was extended under M/N>1/4,and the algorithm under certain condition needs only one iteration to obtain the target solution with probability 1.