一种改进的量子搜索算法

An Improved Quantum Searching Algorithm

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.