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

举报
Lansonli 发表于 2023/01/27 10:09:07 2023/01/27
【摘要】 Grover算法一、什么是搜索算法 举一个简单的例子,在下班的高峰期,要从公司回到家里,开车走怎样的路线才能够耗时最短呢?最简单的想法,当然是把所有可能的路线一次一次的计算,根据路况计算每条路线所消耗的时间,最终可以得到用时最短的路线,即为最决路线,这样依次的将每一种路线计算出来,最终对比得到最短路线。搜索的速度与总路线数N相关,记为O(N),而采用量子搜索算法,则可以以O(sqrt(N))...

Grover算法

一、什么是搜索算法

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

二、怎么实现Grover搜索算法

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

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

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

Oracle对量子态的具体操作是什么样的呢?同D-J算法相似,先将初态制备在

态上,

​编辑为查询寄存器,|1〉为结果寄存器。经过Hardmard门操作后,可以将查询寄存器的量子态,变为所有结果的叠加态;也就是说,经过了Hardmard 门,就可以得到所有结果的索引,而结果寄存器则变为

,再使其通过Oracle,可以对每一个索引都进行一次检验,如果是目标结果,则将答案寄存器的量子态进行0、1翻转,即答案寄存器变为:

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

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

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

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

将所有非搜索问题的解定义为一个量子态|α〉,其中

代表着x上所有非搜索问题的解的和,记为:

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

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

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

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

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

  1. 将量子态经过一个Hardmard门;
  2. 对量子态进行一个相位变换,将

态的系数保持不变,将其他的量子态的系数增加一个负号,相当于

西变换算子;

  1. 再经过一个Hardmard门。

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

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

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

很容易得到:

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

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

参考路线图:

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。