部分扩散与试错混合量子搜索算法的性能和最优参数分析

Performance and Optimal Parameters Analysis of the Hybrid Partial Diffusion and Trail-and-Error Quantum Search Algorithm

Younes等人基于试错方法,将已知目标解比例(λ)情形下的部分扩散量子搜索算法推广到未知λ情形,解决了原始的试错算法不能适用于目标解比例全区间(λ∈(0,1])的问题,并指出算法的平均成功率和期望迭代次数存在优势。通过对Younes算法严格分析,指出该算法的平均成功率下界和期望迭代次数上界存在错误,且算法的参数最优取值问题被忽视。给出了Younes算法正确的性能分析以及算法最优参数关于平均成功率下界的解析函数式。结果表明,Younes算法的平均成功率和期望迭代次数并不优于原始的试错算法。文章工作为未知目标解比例情形下基于试错方法的量子搜索算法的研究提供重要指导。

Based on the trial-and-error method,Younes et al.extended the partial diffusion quantum search algorithm in the case of known fraction(λ)of target items to the case of unknownλ,which solved the problem that the original trial-and-error algorithm cannot be applied to the entire range ofλ∈(0,1],and claimed the advantages in average success probability and expected number of iterations of their algorithm.Through rigorous analysis of Younes algorithm,this paper points out the errors in the lower bound of average success probability and the upper bound of expected number of iterations,and the problem that optimal value of the algorithm parameter is ignored.Furthermore,the correct performance analysis of Younes algorithm,as well as the analytical optimal parameters as a function of the lower bound of average success probability are given.Results show that the average success probability and expected number of iterations of the Younes algorithm are not superior to the original trial-and-error algorithm.This paper provides an important guidance for the research of quantum search algorithms based on trial-and-error method in the case of unknownλ.