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

发布时间：2024-02-28 08:54

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

【文章页数】：5 页

【部分图文】：

图1sin(2mθ)关于m的图像，其中θ=10-3,mq≤m≤10mq

然而，笔者发现sin(2mθ)<0.91并不正确。如图1所示，以θ=10-3为例，画出了m在mq和10mq之间取值时，sin(2mθ)关于m的图像，从中可以发现sin(2mθ)呈现出周期性并且可以超过0.91。事实上，文献[13]给出错误结论的原因是误将m≥mq的条件当作了m=m....

图2sin(2mθ)关于θ的图像，其中0<θ<π/2,m=mq

事实上，文献[13]给出错误结论的原因是误将m≥mq的条件当作了m=mq。如图2所示，给出m=mq条件下sin(2mθ)关于θ的图像，显示sin(2mθ)<0.91。然而对于试错算法，m随着试验次数而指数增大，要求m=mq是不合理的。下面给出正确的分析结果。对于任意的θ∈(0，π....

图3最优参数copt(蓝色实线)关于平均成功率下界Pmlb的图像，子图对应着0.2275≤Pmlb≤0.295，其中绿色点虚线和红色虚线分别对应Pmlb=0.25和0.2725

图3画出了最优参数copt关于算法平均成功率下界Pmlb的图像，从中可以看出，如果文献[13]所给的平均成功率下界Pmlb=0.2725是正确的，那么算法的最优参数应该是copt=1.1577，因此文献[13]所给的参数c的取值(8/7)并不是其所声称的平均成功率下界(0.272....

图4Younes算法(实线)与Boyer算法(虚线)期望迭代次数上界的比较

第2节的结果表明Younes算法正确的平均成功率下界是Pmlb=0.25，此时算法的最优参数取值是copt=8/7，将Pmlb和copt代入到第3节给出的Younes算法正确的期望迭代次数上界Ecub的表达式，可得Ecub=8mq(注，并非文献[13]给出的6.466mq)。图4....

本文编号：3913635