量子计算(二十二):Grover算法

时间:2023-01-17 16:54:42

量子计算(二十二):Grover算法

文章目录

Grover算法

一、什么是搜索算法 

二、怎么实现Grover搜索算法


Grover算法

一、什么是搜索算法 

举一个简单的例子,在下班的高峰期,要从公司回到家里,开车走怎样的路线才能够耗时最短呢?最简单的想法,当然是把所有可能的路线一次一次的计算,根据路况计算每条路线所消耗的时间,最终可以得到用时最短的路线,即为最决路线,这样依次的将每一种路线计算出来,最终对比得到最短路线。搜索的速度与总路线数N相关,记为ON),而采用量子搜索算法,则可以以O(sqrt(N))的速度进行搜索,要远快于传统的搜索算法。

量子计算(二十二):Grover算法

二、怎么实现Grover搜索算法

首先,先化简一下搜索模型,将所有数据存在数据库中,假设有n个量子比特,用来记录数据库中的每一个数据的索引,一共可以表示2个数据,记为N个;希望搜索得到的数据有M个,为了表示一个数据是否是搜索的结果,建立一个函数:

量子计算(二十二):Grover算法

其中x0为搜索目标的索引值,也即是说,当搜索到目标时,函数值fx)值为1,如果搜索的结果不是目标时,f(x)值为0。

假设有一个量子Oracle可以识别搜索问题的解,是别的结果通过Oracle的一个量子比特给出。可以将Oracle定义为:

量子计算(二十二):Grover算法
其中|q〉是一个结果寄存器,⊕是二进制加法。通过Oracle可以实现,当搜索的索引为目标结果时,结果寄存器翻转;反之,结果寄存器值不变;从而可以通过判断结果寄存器的值,来确定搜索的对象是否为目标值。

Oracle对量子态的具体操作是什么样的呢?同D-J算法相似,先将初态制备在量子计算(二十二):Grover算法态上,量子计算(二十二):Grover算法为查询寄存器,|1〉为结果寄存器。经过Hardmard门操作后,可以将查询寄存器的量子态,变为所有结果的叠加态;也就是说,经过了Hardmard 门,就可以得到所有结果的索引,而结果寄存器则变为量子计算(二十二):Grover算法,再使其通过Oracle,可以对每一个索引都进行一次检验,如果是目标结果,则将答案寄存器的量子态进行0、1翻转,即答案寄存器变为:

量子计算(二十二):Grover算法
而查询寄存器不变;但当检验的索引不是结果时,寄存器均不发生改变。因此,Oracle可以换一种表示方式:

量子计算(二十二):Grover算法

其中,|x〉是查询寄存器的等额叠加态中的一种情况。

如上述所知,Oracle的作用,是通过改变了解的相位,标记了搜索问题的解。

现在,将搜索问题的解通过相位标记区分出来,那么如何能够将量子态的未态变已标记出的态呢?

将问题换一种思路进行考虑,当查询寄存器由初态经过Hardmard门后,会变为所有可能情况的等额善加态;也就是说,它包含着所有搜索问题的解与非搜索问题的解。可以将这个态记为:

量子计算(二十二):Grover算法

将所有非搜索问题的解定义为一个量子态|α〉,其中量子计算(二十二):Grover算法代表着x上所有非搜索问题的解的和,记为:

量子计算(二十二):Grover算法

显然,|β〉为最终的量子态,而且|α〉和|β〉相互正交。利用简单的代数运算,就可以将初态|ψ〉重新表示为:

量子计算(二十二):Grover算法

初始态被搜索问题的解的集合和非搜索问题的解的集合重新定义,也即是说,初态属于|α〉与|β〉张成的空间。因此,可以用平面向量来表示这三个量子态,如下图所示:

量子计算(二十二):Grover算法

那么,Oracle作用在新的表示方法下的初态会产生怎样的影响呢?Oracle的作用是用负号标记搜索问题的解,所以,相当于将|β〉内每一个态前均增加一个负号,将所有的负号提取出来,可以得到:

量子计算(二十二):Grover算法

对应在平面向量中,相当于将|ψ〉做关于|α〉轴的对称,但仅有这一种操作是无法将量子态从|ψ〉变为|β〉,还需要另一种对称操作。

第二种对称操作,是将量子态关于|ψ〉对称的操作,这个操作由三个部分构成:

  1. 将量子态经过一个Hardmard门;
  2. 对量子态进行一个相位变换,将量子计算(二十二):Grover算法态的系数保持不变,将其他的量子态的系数增加一个负号,相当于量子计算(二十二):Grover算法西变换算子;
  3. 再经过一个Hardmard门。

这三步操作的数学表述为:

量子计算(二十二):Grover算法

上述过程涉及到复杂的量子力学知识,这三部分的操作,只是为了实现将量子态关于|ψ〉对称。如果想了解为什么这三步操作可以实现,可以阅读关于量子计算相关书籍进一步理解。

前面介绍的两种对称操作,合在一起称为一次Grover迭代。假设初态|ψ〉与|α〉可以表示为:

量子计算(二十二):Grover算法

很容易得到:

量子计算(二十二):Grover算法

可以从几何图像上看到,每一次Grover选代,可以使量子态逆时针旋转,经历了k次Grover送代,末态的量子态为:

量子计算(二十二):Grover算法

因此,经过多次选代操作,总可以使末态在|β〉态上概率很大,满足精确度的要求。经过严格的数学推导,可证明,选代的次数R满足:

量子计算(二十二):Grover算法

参考路线图:

量子计算(二十二):Grover算法 


  • ????博客主页:https://lansonli.blog.csdn.net
  • ????欢迎点赞 ???? 收藏 ⭐留言 ???? 如有错误敬请指正!
  • ????本文由 Lansonli 原创,首发于 CSDN博客????
  • ????停下休息的时候不要忘了别人还在奔跑,希望大家抓紧时间学习,全力奔赴更美好的生活✨