量子搜索算法的多相位关系研究

Investigation of Multiphase Relationship for Quantum Search Algorithm

假设给定一个总数为N的无序数据库,极其复杂的计算使得几乎不可能建立一个精确的数学公式来描述这个结论:在二维复子空间中,对于一个等幅分布的初始态,存在两个定义在实数域上的相位旋转角集合以使得唯一的目标态能以100%的成功概率找到;文中采取了一种近似的计算方法,通过归纳法推导出了多相位匹配方程.倘若其中一个相位旋转角集合中的元素个数j相对于N(N足够大)较小,则该方程就能保证唯一的目标态以较高的成功概率找到.接着,通过文中推导出的一个递推关系式,对任意给定的j>2,分析了Long算法的计算复杂性.最后,通过一些数值模拟的实例进一步验证了多相位匹配方程的有效性.

Suppose we are given an unsorted database of size N.Whereas the extremely complicated calculations make it almost impossible to establish a precise mathematical formulation to describe the conclusion that for a uniform initial amplitude distribution,there exist two sets of the phase rotation angles defined in the real domain such that a unique desired state can be found with certainty in a two-dimensional complex subspace,we resorted to an approximate computational method for simplifying the calculations and thus derived the multiphase matching equation by induction.This equation guarantees that a unique desired state can be found with high success probability provided the number j of elements in one of the sets of the phase rotation angles is relatively small compared to N（N is sufficiently large）.In this case,for any given j2,we analyze the computational complexity of Long algorithm by exploiting a recurrence relation derived in this paper.Finally,we further verify the validity of the multiphase matching equation by some examples of numerical simulation.