加权量子搜索算法及其相位匹配条件研究

摘要：

目前的Grover算法在无序数据库中搜索多个目标时,得到不同目标的几率是相等的,不考虑各个目标重要程度的差异;并且当目标数超过数据库记录总数的四分之一时,搜索到目标的几率迅速下降,当目标数超过记录总数的一半时,算法失效.针对这两个问题,首先提出一种基于加权目标的搜索算法.根据各子目标的重要程度,为每个子目标赋予一个权系数.应用这些权系数将多个子目标表示成一个量子叠加态,这样可使得到每个子目标的几率等于其自身的权系数;其次,提出自适应相位匹配条件,该条件中两次相位旋转的方向相反,大小根据目标量子叠加态和系统初始状态的内积决定.当该内积大于等于((3-√5)/8)1/2时,至多只需两步搜索,即可以恒等于1的几率得到搜索目标.实验表明,算法及其相位匹配条件是有效的.

关键词：量子计算、量子搜索、Grover算法、加权目标、相位匹配

所属期刊栏目：25

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金60773065

在线出版日期：2008-12-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：623-630