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

Phase Matching in Quantum Searching Algorithm with Weighted Targets

作　　者：李盼池[1] 李士勇[1] 

机构地区：[1]哈尔滨工业大学控制科学与工程系

出　　处：《计算物理》2008年第5期623-630,共8页Chinese Journal of Computational Physics

基　　金：国家自然科学基金(No.60773065)资助项目

摘　　要：目前的Grover算法在无序数据库中搜索多个目标时,得到不同目标的几率是相等的,不考虑各个目标重要程度的差异;并且当目标数超过数据库记录总数的四分之一时,搜索到目标的几率迅速下降,当目标数超过记录总数的一半时,算法失效.针对这两个问题,首先提出一种基于加权目标的搜索算法.根据各子目标的重要程度,为每个子目标赋予一个权系数,应用这些权系数将多个子目标表示成一个量子叠加态,这样可使得到每个子目标的几率等于其自身的权系数;其次,提出自适应相位匹配条件,该条件中两次相位旋转的方向相反,大小根据目标量子叠加态和系统初始状态的内积决定.当该内积大于等于((3-5)/8)1/2时,至多只需两步搜索,即可以恒等于1的几率得到搜索目标.实验表明,算法及其相位匹配条件是有效的.As searching targets in an unordered database with Grover＇s algorithm, difference in marked items is not taken into consideration. If fraction of marked items is greater than 1/4, success probability of search decreases rapidly with increase of marked items. When the fraction of marked items is greater than 1/2, the algorithm is disabled. Aiming at above problems, an improved Grover＇s algorithm with weighted targets is proposed in which every target is assigned a weight coefficient according to its significance. With these weight coefficients, targets are represented as quantum superpositions which make probability getting target equal to its weight coefficient. An adaptive phase matching method is proposed based on weighted targets. The directions of phase rotations are contrary, and amplitudes of the two phase rotations are determined by inner-product of target quantum superposition and initial state of the system. As the inner-product is greater than （（3-√5）/8）^1/2, success probability is equal to 1 with two steps of Grover iteration at most. The improved quantum searching algorithm and the new phase matching are verified by an example.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]