量子搜索算法在数据库中的应用

4.4.2 Grover算法与传统搜索算法在数据库应用中的比较

 

那么如果是传统的搜索算法呢？传统的搜索算法例如比较法，就是拿一个确定的数去和这样的一个数据库的数据逐个比较，如果是相等的那么才为真，否则为假。那么如果使用了传统的数据搜索算法那么可能一次得到数据，也可能是2，3，4次，所以平均起来是2次。那么大家一定会想这样Grover算法的优势又在那里呢，很容易想像如果是一个庞大的数据库呢？要从有着100万个号码的电话本中找出某个指定号码，该电话本是以姓名为顺序编排的。经典方法是一个个找，平均要找50万次，才能以1／2几率找到所要电话号码。 G rover的量子算法是每查询一次可以同时检查所有100万个号码。由于100万量子比特处于叠加态，量子干涉的效应会使前次的结果影响到下一次的量子操作，这种干涉生成的操作运算重复1000次后，获得正确答案的几率为1／2。但若再多重复操作几次，那么找到所需电话号码的几率接近于1。

传统搜索算法主要是要克服由解空间过大而导致的需要搜索的路径过多的问题,因此经典搜索策略的核心特征为:设法减少实际搜索空间,当然同时也要考虑挖掘利用结构信息时付出的代价.而量子算法面临的主要问题是解集的振幅太小,因此量子搜索算法策略的核心是:如何迅速地使振幅向解集集中,同时考虑变换的实现复杂性和鲁棒性.也就是说,传统搜索算法考虑的是如何避免在无效路径上进行搜索,而对量子算法来说,搜索所有的路径不是困难所在.量子算法寻求的是如何减少、消除非解路径上的振幅,并把它转移到解路径上来.

打一个比方.搜索算法解决问题就像看一幅巨大的图画并从中找出目标来.传统的方法就好像一个近视的人,为了看清图,不得不离图很近,所以每次只能看到一个(或几个)点.因此为了在“有生之年”看到目标点,他不得不利用结构信息跳跃着选择注视点.而量子算法好像站在远处了望的人,他可以同时看到整幅图画.可惜他看到的只是一幅模糊的图画,为了看清目标,他不得不设法把目标的“颜色”加浓,同时使其他点的颜色变谈.从而使目标更清晰、更突出.这里,“颜色”的深浅就相当于振幅的大小.

 

4.5 Grover算法的评价

 

4.5.1优点

 

(1) 由于没有使用具体问题的特殊结构信息,因此它实际上为这类问题的解决提供了一个普适的框架,是一种通用的算法.算法本身体现了一种重要的思想。

(2) 已经证明,对于无序数据集的搜索问题,如果忽略常系数,则Grover的算法属于最优的算法之一。

(3) Grover算法的另一个重要优点是实现比较简单。算法中的Walsh-Hadamard变换和选择性旋转变换U、条件相移矩阵的实现相对量子傅里叶变换来说要简单得多。一个幺正变换一般是通过基本的量子逻辑门来逼近的(极少数的由特殊的设备实现)。因此量子逻辑门阵列的复杂性反映了算法的复杂性。这也涉及到量子算法设计的一个原则,即算法应尽量容易实现。例如,在Grover算法中D变换可由个基本量子逻辑门实现。Grover算法在小规模的量子系统中得到了验证。在后面,我们把逻辑电路的规模及其实现的复杂性称为幺正变换的实现复杂性。

(4) 量子系统要与外界环境耦合,极不稳定,消相干是指数级的,因此量子力学计算机对外界扰动是极其敏感的。这样一来,在存在大量噪音的环境中要想使系统正常工作,就更需要考虑算法的鲁棒性。Grover指出,对某些扰动,他的量子搜索算法可以具有一定的鲁棒性。龙桂鲁则指出,算法步骤(a)中目标矢量的旋转角度为180°是算法具有某种鲁棒性的保证。另外,Grover的算法还可以通过在一个原子上多个Rydberg态的叠加来实现。这种方法不需要利用纠缠态,据称具有良好的鲁棒性。