【作者】 金文梁；

【导师】 陈向东；

【作者基本信息】 西南交通大学 ， 计算机应用技术， 2011， 博士

【摘要】 在一个大型无序数据库中,与任何经典的搜索算法相比较而言,原先的Grover量子搜索算法能以平方根的加速找到唯一的目标态。并且该算法已经被证明为最优的。迄今为止主要是从以下的方面对该量子搜索算法进行了扩展：(1)假设有多个目标态；(2)以任意的酉变换来代替Walsh-Hadamard变换；(3)引入了概率幅扩大的思想；(4)通过并行的量子计算方式来进一步降低搜索次数；(5)以任意的相位旋转代替反方向的相位旋转；(6)初始态是任意的复概率幅分布,而不再是等概率幅分布；(7)讨论了任意的纠缠初始态。为保证以100%的概率找到一个目标态,许多研究工作者给出了不同形式的精确的相位公式。自然要问一个目标元素的叠加态或者唯一的目标态是否只能在搜索空间只限制在二维复子空间中才能以100%的最大成功概率被找到。对任意的3×3酉矩阵而言,为使得复杂的计算得到充分的简化并得到数学上易处理的结果,可考虑运用下面的性质和技巧：1)一个厄米矩阵的特征值都是实数且对应于该厄米矩阵的不同特征值的特征矢量是互相正交的；2)由于对易性,两个厄米矩阵共同拥有的规格化正交矢量完全集可能存在；3)假设存在两个厄米矩阵共同拥有的规格化正交矢量完全集。那么,如果属于其中之一的厄米矩阵的某个特征值是简并的,则该特征值的简并度应通过另一个厄米矩阵来予以消除。利用上述性质,我们证明了在三维复子空间中,只要偏离角不等于零那么无论给定什么样的初始态,都不能以100%的概率找到一个目标元素的叠加态或唯一的目标态。通过利用将一个3×3酉矩阵分解为两个相互对易的厄米矩阵和指数矩阵的性质这两种不同的方法,进一步论证了如果在一个无序数据库中总的目标态和非目标态的个数充分大,那么对应于两个相同相位旋转角的情形,找到唯一目标态的最大成功概率近似地等于一个偏离角的余弦函数的平方。另一方面,由于一个量子系统将不可避免地受到不可预知的微扰影响,我们得出了以前文献中所报道的Grover量子搜索算法的实验实现实际上是在三维复子空间中完成的结论。同时,利用指数矩阵的性质表明了在一个二维复子空间中,对于任意给定的初始态,倘若满足多相位匹配方程那么就能以较大的成功概率找到唯一的目标态。本文按照任意的初始态、任意的酉变换和任意的相位旋转角的方式以具体的数据实例严格核实了上述结论。更多还原

【Abstract】 The original Grover’s quantum search algorithm goes quadratically faster than any possible classical counterpart for searching a single desired state in a large unsorted database and it was shown to be optimal. So far, several generalizations of the original Grover’s algorithm have been developed from different aspects by some modifications mainly resulted from(1) dealing with the case of more than one desired state;(2) substituting almost any unitary transformation for the Walsh-Hadamard transformation, which is used in the original setting;(3) introduction of the concept of amplitude amplification;(4) further speedup for repeated quantum search by means of quantum computations in parallel;(5) the phase inversion being replaced by arbitrary phase rotations;(6) allowing for an arbitrary complex initial amplitude distribution, instead of the uniform initial amplitude distribution;(7) investigating the case of an arbitrarily entangled initial state. To guarantee that a desired state can be found with certainty, many researchers gave their different forms of accurate phase formulae. It is natural to ask whether a superposition of desired states or a unique desired state can be found with certainty only under the circumstances that the search space is confined to the two-dimensional complex subspace. To render the manipulation of complicated computations substantially simple and to obtain mathematically tractable results for any3×3unitary matrix, we consider the following properties and techniques.1) The eigenvalues of a Hermitian matrix are all real and the eigenvectors of a Hermitian matrix corresponding to different eigenvalues must be orthogonal to each other;2) Due to commutativity, a complete set of common orthonormal eigenvectors shared by two Hermitian matrices possibly exists;3) Suppose that there exists a complete set of common orthonormal eigenvectors shared by two Hermitian matrices. Then, if some eigenvalue belonging to one Hermitian matrix is degenerate, the degeneracy of this eigenvalue should be lifted through combining the other Hermitian matrix. Using the above properties, we prove that no matter what the initial superposition may be, neither a superposition of desired states nor a unique desired state can be found with certainty in a three-dimensional complex subspace, provided that a deflection angle is not exactly equal to zero. By using two different methods of dividing a3×3unitary matrix into two Hermitian matrices, which are commutative one another, and of the properties of the matrix exponential, we further demonstrate that if the total number of the desired and undesired states in an unsorted database is sufficiently large, then corresponding to the case of identical rotation angles, the maximum success probability of finding a unique desired state is approximately equal to the square of the cosine function of a deflection angle.On the other hand, due to the fact that a quantum system will inevitably be influenced by some unpredictable perturbations, we thereby conclude that the experimental realizations of Grover quantum search algorithm previously reported in the literature were, in fact, achieved in a three-dimensional complex subspace. Meanwhile, by utilizing the properties of the matrix exponential, we also showed that in a two-dimensional complex subspace, a unique desired state can be found with high success probability provided the multiphase matching equation is satisfied for any given initial superposition.The above results were rigorously verified by concrete numerical examples in terms of arbitrary initial superposition, arbitrary unitary transformation and arbitrary phase rotation angles in this paper.更多还原