量子科技中心_量科网

格罗弗算法是量子算法的基石，在预言机查询复杂度方面具有严格最优性。虽然完全搜索问题无法进一步改进，但在部分搜索问题中（即只需确定包含目标项的区块），可以牺牲准确度以换取速度。目前已知最优秀的量子部分搜索算法是格罗弗-拉达克里希南-科雷平（GRK）算法，其最优性长期被猜想但未获证明。本研究证明了GRK算法在大区块极限下的最优性：将部分搜索建模为时间最优控制问题，运用庞特里亚金极大值原理推导切换函数动力学，建立正则极值的bang-bang结构，并排除非最优切换模式。最终证明最优正则极值具有“全局-局部-全局”的三段式结构，从而为GRK算法在预言机查询复杂度上的渐进最优性提供了控制理论证明。