[量子计算]量子搜索Grover算法

栏目: 编程工具 · 发布时间: 5年前

内容简介:搜索算法是最常用的一类算法了,然而传统计算机对非结构化数据的搜索其实是比较低效的。一般情况下,算法复杂度为

Post Views: 17

搜索算法是最常用的一类算法了,然而传统计算机对非结构化数据的搜索其实是比较低效的。一般情况下,算法复杂度为 \Omicron(N)N 为数据规模。而量子计算机中存在着量子搜索算法,也称为 Grover’s 算法,它的时间复杂度是 \Omicron(\sqrt N) 。听起来似乎提升不是非常大,然而在数据规模较大的情况下,量子搜索算法的优越性还是非常惊人的。例如,用Grover算法破解通用的56位加密标准(DES),只需要 2^{28} \approx2.68 * 10^{8} 步,而经典算法则需要 2^{55} \approx3.6 * 10^{16} 。如果每秒钟计算十亿次,则经典计算需要11年,而量子算法则只需要3秒钟【参考北大物理学院讲义】。

1、 Grover算法理论基础

Grover’s 算法的基本思路其实非常容易理解,而且存在非常直观的可视化解释(这一点是非常棒的!)。Grover算法的量子线路有一个重要的基本单元,也称为Grover迭代。一个完整的Grover量子线路会包含一个或者多个Grover迭代单元。Grover算法的量子线路图如下所示:

[量子计算]量子搜索Grover算法

不算测量的话,Grover算法量子线路其实也就两个部分,一个是量子态准备,另一个是多次Grover迭代。而每一次的Grover迭代,也可以分为两个部分——一部分是 U_{\omega} ,这部分是为了实现指定态的相位翻转,另一部分就是上图中所示的Grover diffusion operator,其实叫它Invasion abort mean会更贴切一些,至于为啥这样叫,稍后就知道了。

1.1、定性分析

上面很粗略地介绍了下Grover’s algorithm的整体结构,接下来就需要分析下核心部件——Grover迭代单元的工作原理了。Grover迭代单元的工作原理其实朴素,就是指定态翻转和关于平均值翻转(先关注下面几张图的右侧)。

1、首先,假设假设Grover迭代单元的输入是很多态的均匀叠加,如下图右侧所示:

[量子计算]量子搜索Grover算法

2、然后,我们可以通过 U_{\omega} 的作用,把想要搜索的态的幅值翻转过来,其他正交的态完全不变。然后可以得到下图的效果:

[量子计算]量子搜索Grover算法

3、最后,可以根据各个基态的幅值计算出均值,然后按照这个均值镜像翻转各个基态的幅值,就可以得到如下图所示的结果。

[量子计算]量子搜索Grover算法

可以直观发现,通过上面三个步骤,目标态的幅值增大了。事实上,使用Grover迭代一定次数,目标态的幅值可以比较接近1。然后进行测量,可以大概率地测量到目标态,也就是说搜索到了目标态。

1.2、定量分析

上面形象、定性地分析了Grover算法的重要步骤,接下来进行更严谨的推导。首先还是说 U_{\omega} ,这里我们记要搜索的目标态为 \omega ,则可以简单的得到 U_{\omega} 的表达式如下所示:

U_{\omega} = I – 2|\omega \rangle \langle \omega |

其实非常容易理解, |\omega \rangle 左乘以 U_{\omega} ,其幅值符号就会翻转,而其他正交向量就完全不会改变。矩阵的表达式是找到了,怎么转化成量子线路呢?其实是有技巧的,考虑如下图所示的结构。

[量子计算]量子搜索Grover算法

由于最下面的量子比特经过状态准备之后,进入了 \frac {|0\rangle-|1\rangle} {\sqrt 2} 这个态。这个态有一个特点,就是取反操作等效于幅值符号翻转。因此,只需把Oracle构造成相应的条件非门就可以。比如Toffoli gate,Toffoli gate的作用是两个控制比特全部为1的时候,翻转受控比特,其他时间不起作用。因此,Toffoli gate构成的Oracle线路就指定了 (|1\rangle)( | 1 \rangle) 这个目标态。Toffoli gate的实现线路如下图所示:

[量子计算]量子搜索Grover算法

我没仔细推导这个线路,而是参考了维基百科。

上面的分析对应于第二个步骤——按指定向量翻转,接下来就该看另一个步骤——绕均值翻转(inversion abort mean)。其实这个步骤非常容易理解,Grover diffusion operator的公式如下:

H^{\otimes n}(2|0\rangle \langle 0 | – I)H^{\otimes n} = 2|\psi\rangle \langle \psi | – I

至此,单个Grover迭代的过程都分析了,接下来就看看Grover多次迭代的过程。由于推导过程稍微比较麻烦,这里就直接给近似公式了。

| \phi_{r}\rangle \approx sin(\frac {2r} {\sqrt N})|x \rangle + \frac {cos(\frac{2n} {\sqrt N})} {\sqrt N} \sum_{i = 0 ,i !=x}^{N-1}|i \rangle

从公式可以看出来, r=[\frac {\pi}{4}\sqrt N] 的时候,测量到的概率最大(这里r是指的迭代次数)。

2、 Grover算法实践

接下来,还是在IBM量子计算平台上来做一下Grover’s algorithm的实验。这个实验里,取n=2,即实验两个两字比特。

[量子计算]量子搜索Grover算法

[量子计算]量子搜索Grover算法

这里的线路和前文描述的是一样的,Oracle是Toffoli gate构成的,因此这个线路的输出应该大概率是q[1]、q[2]都是 |1\rangle 。可能是硬件原因吧,IBM的物理硬件不让跑这个线路,所以我只能跑模拟了,结果如下,符合实验预期:

[量子计算]量子搜索Grover算法

那量子搜索算法就先写到这里了。。。

参考文献

【1】.《量子计算与量子信息》Michael A. Nielsen

【2】.《量子力学》列文.朗道

【3】.《量子力学原理》P.A.M. Dirac

【4】. IBM量子计算实验平台


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

O2O

O2O

张波 / 机械工业出版社华章公司 / 2013-2-5 / 49.00元

2012年是O2O元年,无论是成熟的传统企业、如火如荼的电子商务企业,还是以电信、银行、娱乐等为代表的与民生相关的企业,都在探索和践行O2O模式,因为O2O中孕育着极富创新性的商业模式。本书是国内首部O2O方面的著作,不仅宏观上叙述了O2O的概念、在各行业的应用情况,以及未来的发展趋势,而且还系统阐述和解读了各行业如何借助O2O来顺利实现商业模式的转型和升级;不仅极富洞察力地分析了O2O在营销、支......一起来看看 《O2O》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

MD5 加密
MD5 加密

MD5 加密工具