一种改进的量子搜索算法  

An Improved Quantum Searching Algorithm

作　　者：宋辉[1] 戴葵[1] 王志英[1] 

机构地区：[1]国防科技大学计算机学院,湖南长沙410073

出　　处：《计算机工程与科学》2002年第5期4-7,14,共5页Computer Engineering & Science

基　　金：国防科技预研基金资助项目 (98J16.0 .2KG0 14 3 )

摘　　要：Grover提出的对无序数据库进行搜索的量子算法 ,可以将搜索时间复杂度从经典计算机上的O(N)降低为O(N)。该算法显示了量子计算的强大能力 ,在量子计算研究中具有重要地位。但是 ,我们在研究Grover算法中发现Grover算法存在搜索失效等问题。本文分析了Grover算法中存在的问题 ,针对其不足之处进行了改进 ,并证明了改进后量子搜索算法的有效性。The time complexity of Grover's quantum searching algorithm is O( N ), but the algorithm's time complexity on classical computers is O( N ). It proves the strong power of quantum computers, and has important influence on quantum algorithm research. But we find that Grover's algorithm still has some problems. When the solution is not unique, this algorithm may cause failure. In this paper, we improve this quantum searching algorithm, and prove the correctness and validity of this improved searching algorithm. The improved algorithm can find solutions more efficiently than the original Grover's quantum searching algorithm.

关 键 词：搜索算法 量子计算 量子寄存器 无序数据库 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]