Grover数据库搜索算法

来自计算思维百科
跳转至: 导航搜索

对于无序数据库,搜索的规模随着数据库规模的增长而成线性增长。这一问题在经典算法中需要O(N)时间才能完成整个搜索过程。1996年Grover提出量子搜索算法,将搜索问题完成的时间缩小到步,对经典问题起到了二次加速的作用。

Grover算法适用于解决在无序数据库中搜索某一个特定数据的问题。在经典计算机中,对待这类问题只能一个一个的搜索数据库中的数据,直到找到为止,通常需要N/2次查询才能以1/2的概率找到需要的数据。而Grove算法利用量子并行性,每一次查询可以同时检查所有的数据,并使用黑箱技术对目标数据进行标识,这样重复后,就可以1/2概率找到。再多重复操作几次,就可以接近于1的概率找到特定的数据。现实中的许多问题,如最短路径问题、图的着色问题、排序问题及密码的穷举攻击问题等,都可以利用Grover算法进行求解。

Grover算法是目前最经典的量子算法之一,然而它也存在着某些缺陷。比如当要搜索的目标数超过数据库中记录总数的1/4时,Grover算法搜索成功率迅速下降。当目标数超过数据库记录的一半时,算法几乎失效。