（理论物理专业论文）量子随机行走搜索算法研究.pdf

摘要 量子随机行走搜索算法研究 摘要 量子计算与量子信息的研究可以追溯到几十年前，但真正弓i 起广泛关注是在 2 0 世纪9 0 年代中期。这期间发现了s h o r 快速因子分解算法和g r o v e r 搜索算法， 这两类算法展示了量子计算机从根本上超越经典计算机的计算能力。近年来，量 子随机行走正逐渐开始引起人们重视，这是因为方面，量子随机行走可以看作 是经典随机行走在量子系统上的一种自然推广，另一方面，量子随机行走能够应 用于构造有效的量子算法。 本文首先介绍量子随机行走和一种基于量子随机行走的搜索算法，即量子随 机行走搜索算法，它与g r o v e r 搜索算法有着相同的搜索速度。接着我们研究了两 种噪声模型对该算法的影响。在第一种噪声模型中我们假设算法执行时，控制随 机行走方向的量子硬币在算符作用下进行的相位翻转操作含有一定的误差，即相 位噪声，我们研究了这种相位噪声对搜索算法产生的影响。早先人们已经研究了 这种相位噪声对于g r o v e r 搜索算法的影响，我们通过比较发现，两种搜索算法在 对相位噪声的响应上有着相同和不同之处。在第二种模型中我们主要研究了白噪 声对于量子随机行走搜索算法的影响。由于在真实环境中搜索算法执行的每一步 都会因为与周围环境相互作用而出现退相干效应，它会使存储在量子计算机中的 量子态几率幅发生涨落，从而改变最后的输出结果。我们将这种效应模型化为算 法每一步执行过程中量予态上出现的高斯白噪声，我们通过计算机模拟研究了它 对算法的影响，并与g r o v e r 搜索算法进行了比较。 本文的工作有助于进一步了解量子随机行走搜索算法与g r o v e r 搜索算法之间 的区别和差异，并对量子搜索算法的实际应用有定的理论指导意义。 关键词：量子计算，量予搜索算法，量子随机行走 a b s t r a c t i n v e s t i g a t i o n so nq u a l l t l j mr a n d o m w a l ks e a r c h a l g o r i m m a b s 仃a c t t h es m d i e so fq u a n t u mc o m p u t a t i o na n dq u i n f b 衄a t i o nc a nb e 廿a c e db a c k t os e v e r a ld e c a d e sa g o al a r g ep r o g r e s so c c u r r e di n 也em i d d l eo f9 0 s ，2 0 t 量lc e n t u m d u r i n gw h i c hs h o r sf 如ta l g o r i t h mf o rf a c t o r i n ga 1 1 dg r o v e rs e a r c ha l g o r i m mw e r c f o u n d t h o s et w ok j n d so fa l g o r i m ms u g g e s tt h a t ，i n d e e d ，q u 鼬咖mc o m p u t e r sm i g h t h a v ec o m p u t a t i o n a lp o w e r se x c e e d i n g 也o s eo fc l a s s i c a lc o m p m e r s i nr e c e my e a r s ，m e q 咖t u mr a l l d o m w a l k ( q r w ) i sr e c e i v i n gs i 弘墒c a n ta 札e n t i o n ，b e c a u s ei ti san a t u r a l g e n e r a l i z a t i o no fc l a s s i c a lr a n d o mw a l k st oq u 龇血l ms y 咖m s ，a n db e c a u s eq u 乏m t u m r a n d o mw a l k sc o u l db eu s e f u l i nc o n s t m c t i n ge m c i e n tq u a i l t u ma l g o r i t s i n t h j sp a p e r ，w ei n v e s t i g a t eaq u a n t u ms e a r c ha l g o r i 也mb a s e do nt 王”q u a m u m r a n d o m w a l k ，i e ，t h eq 啪t u mr a n d o m w a l ks e a r c ha 1 9 0 r i 也m ，w h j c hh a sn e a r l y 也e s 啪es p e e da st h eg m v e rs e a r c ha l g o r i t n e n ，w es t u d yh o wv a r i e t i e so fn o i s ea 鼠c t s u c ha l g o r i 廿m 1 w es e tu pt w od m r e n tn o i s em o d e l s f i r s t ，w ca s s 啪et h a t 也e o v e r d i f r u s i o no p e r a t o ru s e di nt h ea l g o r 甜皿i sn o t 印p l i e dp e r f e c t l y i e ，t h e r ei san o i s ei n p h a s ei n v e r s i o n s a si sw e l lk i l o w n ，a n yp h a s ei n v e r s i o n0 p e r a t i o ni si 叫) e r f e c t ，s ot l l e r e i sa nu n c e r t a i n t y w es t u d yt h ee f ! f e c to fs u c hp h a s en o i s ea t l dd e m o n s 饿n eh o wi ta c t s o nt h er e s u l to ft h es e a r c ha l g o r i t h m t h ec o r r e s p o r l d i n gw o r ko fg a t ei m p e r f e c t i o ni n m eg r o v e rs e a r c ha l g o r i t h mh a sb e e na l r e a d ys t u d i e d n e v e r t h e l e s s ，o u rs t u d i e ss h o w n o t a b l ed i 行e r e n c e s ，a sw e l la ss i m i l a r i t i e s ，i nt h er e s p o n s eo f 也et w oa l g o r i t h m st on o i s e s e c o n d ，w ei n v e s t i g a t e 血ew h i t en o i s ei nm eq r ws e a r c ha l g o r i t h 1 1 1a n ys e a r c h a l g o r i t 胁，d e c o h e r e n c ew i l lo c c l l ri ne a c hs t e p ，a n d 也e r e f o r ei tm a yi n e v i t a _ b l ya l t e rt h e p r o b a b i l i t i e so ft h es t a t e si nt h ef i n a lo u t p u t w bm o d e ls u c hk i n do fn o i s eb ya s s 啪i n g t h a t i ne a c hs t e po ft h ea l g o r i t ，a 、v h i t eo rg a u s s i a nn o i s em o d i 丘e s 也es t a t eo f 也e w h o l ed a 协b a s e w es h o w 也ec o r r e s p o n d i n gn u r n 嘶c a lc a l c u l a t i o n sa n da n a l y t i c a l a p p r o x i m a t i o n s o u rw o r k sa r eu s e f u lt om a k ea p r o f o u n dc o m p a r i s o nb e 晰e e n 也eg r o v e rs e a r c h a l g o r i m ma n dt h eq r ws e a r c ha l g o r i ，a n d 盯eh e l p f u lf o ri n v e s t i g a t i n gt h e 印p l i c a t i o no f t h eq u a n t u ms e a r c ha 1 9 0 r i t 1 1 k e yw o r d s ：q u a n t mc o m p u t e ，q u a i l t i l ms e a r c ha l g o 珊吼，q u a l l t u mr 孤d o mw a l k n i 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成 果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表 或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作 了明确说明并表示谢意。 作者签名： 蕉整日期：缱2 ：i 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学 位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要汇编出版。 保密的学位论文在解密后适用本规定。 学位论文作者签名：巷结 导师签名： 日期：2 鲤：f 马雷 日期：迎：旦- 7 第一章引言 第一章引言 量子计算是2 0 世纪两大科学成就量子力学和计算科学结合的产物。 量子力学诞生于2 0 世纪初，当时物理学遇到了一系列危机，包括黑体辐射、原子 线状光谱等问题在物理解释上遇到的困难。起初这些问题是通过在经典物理学中 附加特别的假设来解决，但随着人们对原子和辐射更好的了解，这些“治标”性 的解释越来越让人困惑。经过四分之一世纪的搜索，到2 0 世纪2 0 年代中期，最 终导致了量子力学这一现代理论的创立。量子力学一出现就成为近代科学不可缺 少的一部分，如今它已经被广泛应用于包括原子结构、恒星聚变、超导体、d n a 结构和自然界基本粒子等的几乎所有方面，是整个近代物理学的基础。 当代计算机的理论基础是t u r i n g 1 1 ，c h u r c h 口增人在三十年代提出的关于可计 算函数和不可计算函数之区分的一些纯数学的命题。其核心是通用1 砒i n g 机理论， 即用t u r i n g 机可模拟任何计算过程。在t u r i n g 的理论结果发表后不久，世界上的 第一台电子计算机应运而生了。到1 9 4 7 年晶体管发明之后，计算机硬件的能力开 始以惊人的速度成长，以至1 9 6 5 年g o r d o nm o o r e 把这种成长概括为m 0 0 r e 律 即计算机的能力以固定的速率成长，大约每两年增长一倍。从2 0 世纪6 0 年代开 始，m o o r e 律在几十年时间里都近似成立，然而大多数观察家认为：由于当电子器 件越做越小时，它的功能开始受到量子效应的干扰，因而m 0 0 r e 律很可能在2 1 世 纪的阿2 0 年内结束。针对m o o r e 律最终将失效的问题，一个可能的解决办法是采 用不同的计算模式，量子计算理论就是这类模式的一种。 量子计算机从速度上对经典计算机有本质的超越，许多在经典计算机中无法 “有效”解决的问题在量子计算机下能得到有效解决。这里的“有效”、“非有效” 是根据算法复杂性理论从数学上精确定义的。粗略的说，有效算法解决问题需要 的时闯是问题规模的多项式；相反，非有效算法需要超多项式( 典型情况是指数) 时间。1 9 8 5 年，d a v i dd e u t s c h 提出了一个量予算法，用来说明量子计算机确实可 能从计算能力上超过那些经典计算机【3 1 。随后十年内许多人努力改进d e u t s c h 令人 瞩目的初步结果，这些努力到1 9 9 4 年p e t e rs h o r 展示两个极其重要的问题寻 找质数因子问题和解决所谓离散对数问题可以用量子计算机有效解决时达到 第一章引言 顶点。这方面研究受到广泛关注的原因是人们仍相信这两个问题在经典计算机上 没有有效解法。s h o r 的结果是量子计算机比t u r i n g 机，甚至概率t i l r i n g 机更为强 大的有力证据。量子计算机功能强大的进一步的证据出现在1 9 9 6 年，l o vg r o v e r 证明另一个重要问题在没有结构的搜索空间上进行搜索的问题在量子计 算机上可以被加速。虽然g r o v e r 搜索算法没有达到s h o r 算法那样明显的加速，但 搜索方法的广泛适用性引起人们对g t 0 v e r 搜索算法相当的关注。 量子随机行走算法是近几年来开始为人们所注意的另一种量子算法。由于经 典的随机行走在许多计算问题中都有应用，人们希望能够将它应用到量子计算机 上。本文主要研究量子随机行走在量子搜索算法中的应用。我们首先介绍算法复 杂度理论以及量子算法的一些特性和主要的分类。然后我们引入了量子随机行走 的基本概念并给出了若干模型，如一维直线及环上量子随机行走，它们是目前实 验上唯一能用多种物理系统( 离子阱、腔量子电动力学以及光晶格) 实现的量子 随机行走。接着，我们讨论基于量子随机行走的搜索算法量子随机行走搜索 算法，它与g r o v e r 搜索算法类似，也是一个调用o r a c l e 的量子搜索算法，并且与 g r o v e r 搜索算法有着相同的速度，即仅仅调用o r a c l e o i 次就能够搜索项数 据集，因而这种算法在无序搜索中也是最优的。 由于在实际实验中环境噪声的影响和量子逻辑操作的不精确性会使算法的可 靠度大大下降，在本文接下来的部分中，我们将讨论噪声和误差给量子随机行走 搜索算法带来的影响。我们主要考虑两种噪声，第一种是算法执行过程中控制随 机行走方向的量子硬币在算符作用下进行相位翻转操作时引入的误差效应，即相 位噪声，第二种是实验过程中系统和环境热库作用给存储在量子计算机中的量子 态带来的随机白噪声。我们将通过数值模拟来观察这两类噪声对量子随机行走搜 索算法的影响，并将这些结果与g r o v e r 搜索算法下受同类噪声影响的结果进行对 比，分析这两种搜索算法在对抗不同类型噪声时的优劣特性。 第二章量子算法概论 第二章量子算法概论 2 1 算法复杂性理论 计算理论所研究的一个十分基本的问题是：什么是可计算的和它们能够怎样 被有效率地计算。算法复杂性理论对包括经典和量子计算问题的各种计算问题的 难度进行了分类【4 】。最重要的两个复杂类分别称为p 和n p 类。如果一个判定性问 题的复杂度是该问题的一个实例的规模竹的多项式函数，则我们说这种可以在多 项式时间内解决的判定性问题属于p 类问题。所有p 类问题在经典计算机上大都 可以快速求解。另一些问题很难找到多项式时间的算法( 或许根本不存在) ，但是 我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答 案是否正确。这种可以在多项式时间内验证一个解是否正确的问题称为n p 问题。 例如整数门的素因子问题，到目前为止，还不知道在经典计算机上求解此问题的 快速方法，这暗示它不在p 类中。另一方面，如果知道矽是n 的因子，我们可以 通过p 去除行来很快检查其正确性，于是这类问题属于n p 类。 很清楚p 类是n p 类的子集，因为能求解意味着必然能检验可能的解。尚不清 楚是否存在不属于p 类的n p 问题，但大多数研究者相信n p 包含不属于p 的问题。 特别地。n p 类中有一个重要的子集类- n p c ( n p c o m p i e t e ) 问题。n p c 问题 存在着一个令人惊讶的性质，即如果一个n p c 问题存在多项式时间的算法，则所 有的n p 问题都可以在多项式时间内求解，即p _ n p 成立! 这是因为，每一个n p c 问题可以在多项式时阳j 内转化成任何一个n p 问题。因此我们一般认为n p c 问题 是难解的问题，它不太可能存在一个多项式时间的算法。 量子计算机通过恰当的量子算法能够在多项式时间内解决一些经典计算机需 要指数时间去解决的n p 问题，例如因子分解问题( 注意，还不知道因子分解问题 是否为n p c ，否则我们就知道如何用量子计算机有效求解所有n p 问题了) ，也能 提高某些经典算法的效率，例如遍历搜索问题。量子计算机上解n p 问题的一个办 法是利用量子并行机制来并行搜索问题的所有可能解。量子并行性是量子算法的 一个基本特征，目前还不清楚它是否可以快速求解n p 类的所有问题。 第二章量子算法概论 2 2 量子并行性 量子算法是相对于经典算法而言的，它最本质的特征就是充分利用了量子态 的叠加性和相干性，以及量子比特之间的纠缠性，它是量子力学直接进入算法理 论的产物。下面我们首先简单介绍什么是量子并行性。 考虑初态为l 工，y ) 的双量子位量子计算机，设，( z ) ： 0 ，1 ) 一 o ，1 ) 是具有单比特定 义域和值域的函数。在量子计算机上，计算该函数的一个简便办法是通过适当的 逻辑门序列把这个状态变换为i x ，y o 厂( z ) ) ，这里。表示模2 加。第一个寄存器称 为数掘寄存器，第二个寄存器称为目标寄存器，映射i x ，y ) _ i x ，y o ，( z ) ) 叫做u r ， 容易证明它是酉的。若y = o ，则第二个量子位的终态就是，( x ) 的值。考虑图2 1 的线路，数据寄存器中是叠加态0 0 ) + 1 1 ) ) 2 ，这可以由h a d 蛐a r d 门作用到i o ) 上 得到，于是应用 ，得到状态 j o ，( o ) ) + i l ，( 1 ) ) f 一 ( 2 1 ) 注意在这个状态中同时包含了厂( 0 ) 和厂( 1 ) ，这是利用了量子计算机处于不同状态 的叠加态的能力，用单个，( z ) 线路来同时计算多个x 的函数值。它不同于经典的 并行计算，那里是用多重，( z ) 电路同时运行。 l o ) + 1 1 ) 2 l o ) 图2l 吲时计算，( 0 ) 和，( 1 ) 的量子电路，【，是把输入l x ，) 变成l 五y o ，0 ) ) 利用h a d 跚a r d 变换( 有时又称为w a l s h h a d 锄a r d 变换) ，这个过程很容易推 广到任意数目的量子位上的函数。该变换就是n 个h a d a m a r d 门同时作用到胛个量 子比特上，当 = 2 ，初态全为1 0 ) 的情况，输出是 ( 掣 ( 掣 i 刚掣 协 更一般地，n 个量子位上的h a d 锄a r d 变换从全l o ) 出发，可以得到 绍二章量子算法概论 去j x ) ( 2 3 ) 歹r 7 ”j 其中求和是对x 的所有可能值。可见h a d 呦a r d 变换产生了所有计算机基态的等权 叠加态，而且它的效率非常高，仅用n 个门就产生了2 ”个状态的叠加。 可以采用下述方法进行n 比特输入x 和单比特输出，( x ) 函数的量子并行计算。 制备月+ 1 量子位的状态l o ) “l o ) ，对前n 位应用h a d a m a r d 变换，并连续实现u ，的 量子线路，这就产生了状态 赤莓m ( x ) ) 刚) 表面上似乎只进行一次厂计算，量子并行性却使，的所有可能值被同时计算出来。 然而，这种并行性不是直接就能起到显著作用的。对于单量子位，测量状态会得 到i o ，厂( o ) ) 或i l ，( 1 ) ) 中的一个，而对于一个量子位，测量状态i x ，( z ) ) 也类似地 只给出对某个单个x 的，( x ) 值。经典计算机很容易可以做到这点。为了真正有用， 量子计算机要求的不仅仅是量子并行性；它要求比从叠加态l x ，( x ) ) 中得到一个 ，( x ) 值更高的信息提取能力。 下面我们以d e u t s c h 算法【3 l 为例，说明量子算法怎样有效利用量子并行性超越 经典算法。如图2 2 所示，我们用h a d 锄a r d 门把初态为i o ) 的第一量子位变为叠加 态0 0 ) + 1 1 ) ) j ，把初态为1 1 ) 的第二量子位变为0 0 ) 一1 1 ) ) j 。输入状态 i ) = 1 0 1 ) ( 2 5 ) 通过两个h a d a m a r d 门后给出 _ 掣 掣 ( 2 6 ) 由于u ，作用到l x ) 0 0 ) 一1 1 ) ) j 上可得状态( _ 1 ) m 卜) 0 0 ) 一1 1 ) ) 辱，i ) 经过u 作 用后可能出现两种情况： y ：) = ，( o ) = ，( 1 ) ( 2 7 ) 厂( o ) 厂( 1 )啪一啪一 h 万h 万 扣一一 n 兰n v h 万h 西 扣一舾一 捃= 章量子算法概论 最后h a d a f n a r d 门作用在第一量子比特上，导致 y ，) = 印， 掣 ， 坤， 掣 ， ，( 0 ) = ，( 1 ) 厂( o ) ，( 1 ) ( 2 8 ) 注意到当，( o ) = 厂( 1 ) 时，( 0 ) o ，( 1 ) 为o ，其他情况为l ，该结果又可以写为 l 虬) 嘲0 ) 。，( 1 ) ) 业掣 ( 2 9 ) l y j 这样，通过测量第一量子比特，我们可以确定，( 0 ) 0 ，( 1 ) 。量子线路可以让我们 仅用对厂( z ) 的一次计算，就能够确定，( x ) 的全局性质，即，( 0 ) 0 ，( 1 ) 。这个过程 比所有可能的经典设备都要快，因为经典设备至少要两次计算。 o ) 1 ) xx斗 u ， y y o 厂( x ) 木木 圜22 实现d e u t s c h 算法的量子线路 这个例予使量子并行性与经典随机化算法的差别凸显出来，简单地说，可以 认为状态i o ) | 厂( o ) ) + 厂( 1 ) ) 非常接近于以l 2 概率得到，( o ) 、以1 2 概率得到，( 1 ) 的经典概率计算机。差别在于经典计算机上这两中选择总是相互排斥的，而在量 子计算机上两种选择却可以通过相互干涉而给出函数厂( x ) 的某些全局性质。具体 算法是像在d e u t s c h 算法中那样，利用如h a d 跏a r d 门那样的装置对不同选择进行 重新组合。许多量子算法设计的本质在于，精心选择函数和最终变换，以便有效 地确定有关函数的有用全局信息，而经典计算机上无法快速得到。 2 3 量子计算的优越性 量子算法的核心就是研究如何处理量子并行计算，使得以般向刚概率测量到 我们所期望的计算结果。已知有三类量子算法优于经典算法【5 】：第一类是基于 f o u r i e r 变换的量子算法，s h o r 的因子分解算法和离散对数算法闻就是这类算法的 第二章量子算法概论 例子。第二类是量子搜索算法，g r o v e r 搜索算法【7 1 和量子随机行走搜索算法【8 】是这 一类算法的代表。第三类算法是量子仿真，用量子计算机模拟量子系统，这个思 想最早是由f e y 咖a n 提出的吼下面简述这些算法，并综述关于量子计算机计算 能力的已知或推测的结果。 1 基于f o u r i e r 变换的量子算法 离散f o u r i e r 变换通常被视为元复数集合，x 。到复数集合乩，蜥一。的 变换，定义如下： nz 去p 2 州”0 ( 3 o )n 5 而缶矿1 “”。0 ( 3 。0 j 这个变换在近代科学的许多分支中有无数的应用。用量子线路实现的f o u r i e r 变换 可以看作式( 3 o ) 的一种向量形式。定义线性变换u ，它作用在计算基 i ，) ( o 2 “一1 ) 上可以得至0 l ) 呻赤荟删2 “】2 ) ( 3 - 1 ) 可以验证该变换是酉的。如果u 作用到叠加态上，则有 跏，_ 古誓陆驴归心，= 鼢) z ， 用于d e u t s c h 算法的h a d a m a r d 变换是一类广义f o u r i e r 变换的特例。 量子计算机可以非常迅速地计算2 “个复向量的f o 嘣e r 变换。在经典情形，快 速f o u r i e r 变换大约需要l o g ( ) = 托2 4 步完成= 2 ”个数的f o 、l r i e r 变换。在量子 计算机上，f o u r i e r 变换可以用约l 0 9 2 ( i v ) = n 2 完成，指数量级节省了计算步数。虽 然我们无法从测量中直接得到这些结果( 因为如果测量输出状态，每个量子位都 坍缩到i o ) 或j 1 ) 状态，我们就无法直接知道变换的结果n ) ，但某些被认为经典计 算机无法有效求解的问题确实可以利用量子f o u r i e r 变换来有效求解。这些问题包 括d e u t s c h 问题、求阶问题，s h o r 的离散对数和因子分解算法。 2 量子搜索算法 量子搜索算法是完全不同类型的算法，其基本原理由g r o v e r 发现。量子搜索 算法需要解决的问题是：给定大小为的搜索空间，没有关于它结构信息的先验 知识，希望找到这个搜索空间中的满足已知性质的一个元素。找到一个满足条件 第二章量子算法概论 的元素需要多久? 这是一个求解困难而验证容易的问题。经典情形，这个问题需 要大约次操作，但量子搜索算法可以用大约次操作解决。量子搜索算法只 提供了二次加速，不如基于量子f o 谢e r 变换的算法的指数加速令人印象深刻，但 是当非常大时，量子搜索算法的优越性就能显示出来。0 r o v e r 搜索算法和量子 随机行走搜索算法都是提供呻加速的量子算法，后面我们还将看到，这两 种搜索算法的相同点与不同点。可以证明，对基于o r a c l e 调用的量子算法，这种 二次加速的量子算法是最优的【1 0 1 。 量子搜索算法用途广泛，它的巨大功效来源于我们没有对搜索问题假定任何 特别的结构。我们可以利用它来加速n p 类问题的求解，例如h 锄i l t o n 圈问题。 这种算法在解决经典难题方面的应用要比基于量子f o l l r i e r 变换的算法更广。 弓量子仿真 模拟自然发生的量子力学系统是量子计算机擅长而经典计算机却难于完成的 任务。经典计算机难以模拟量子系统是因为描述量子系统需要的复数个数往往随 系统规模的增大呈指数性。一般地，存储具有竹个不同元素的系统的量子状态需 要大概c ”比特经典计算机内存，这里c 是依赖于被模拟系统细节和模拟精度的常 数。与之对照，量子计算机可以用砌量子位进行模拟，i 也是以来与被模拟系统 细节的常数。这使量子计算机可以有效模拟被认为在经典计算机上不能模拟的量 子力学系统。但是当我们实施测量时，一个砌量子位的模拟将坍缩为一个确定状 态。在波函数中的c ”比特的隐含信息不能全部访问。因此，量子仿真的关键仍然 是研究如何有效抽取期望答案的系统化方法。 2 4 量子算法的物理实现 量子计算机以其量子并行计算的优越性为未来计算机的发展开拓了新的方 向。目前，人们提出的量子计算机物理实现的方案主要有：以离子作为信息载体 的离子阱方案；以光子作为信息载体的光学光子计算机方案，光学腔量子电动力 学( c q e d ) 方案；以自旋作为信息载体的核磁共振( n m r ) 方案，量子点方案； 以电子作为信息载体的基于j o s 印h s o n 结的超导体方案等。部分量子算法已经在上 述几个物理系统中得到实现，其中包括d e u t s c kj o z s a 算法，量子求阶算法，s h o r 的因子分解算法和g r o v e r 搜索算法。利用核磁共振技术，c h 啪g 、v 觚d e r s y p e n 值二耄量子算法概论 和z h o u 首先实现了d e u t s c h j o z s a 算法 ，诎e u c h j 通过线性光学器件和单光子探 测技术也实现了该算法【川。基于量子f o 嘶e r 变换的量子求阶算法在2 0 0 0 年由i b m 公司和斯坦福大学的研究小组通过核磁共振实现【1 引，2 0 0 1 年，该小组通过控制含 5 个氟原子和2 个碳原子的新型分子又实现了s h o r 因子分解算法【1 4 】。g r o v e r 搜索 算法最早由c h u a i l g 、g e r s h e n f e l d 和k u b i n e c 利用核磁共振实现1 1 5 】。同年，j o n e s 、 m o s c a 和h a n s e n 在小分子上也实现了d e u t s c h 算法【1 6 】和( v e r 搜索算法【1 7 1 。k w i a t 、 m i t c h e l l 、s c h w i n d t 和w h i t e 曾利用线性光学器件构造出g r o v e r 搜索算法的光学仿 真过程，但是这种方案当规模增大时需要指数多的资源。2 0 0 2 年，s c u l l y 和 z u b a i r y 提议使用电磁感应透明( e i t ) 介质实现g r o v e r 搜索算法【1 9 。由于e i t 系 统具有抑制介质对透射光的吸收，同时显著增强介质的非线性效应等特点，因此 能够实现光束在极小损耗的情况下获得较大的相位翻转，目前己成为实现光学量 子计算的又一热门方案【2 0 2 1 ，22 1 。 目前已经实现的量子计算还仅限于几个量子位，很多量子算法的优越性无法 得到体现。这是由于退相干效应，还有其他的噪声来源和不完美因素，例如量子 逻辑操作的不精确等，使得大规模量子计算难以实现。以成功展示七个比特量子 计算的核磁共振方案为例，一由于核磁共振体系实质上是一个宏观系综，只有当它 被制各到一个特殊状态赝纯态时，其行为才与纯粹的量子系综完全一样，从 而能完成量子计算。赝纯态并非真的纯态。其极化率不仅不足1 0 4 ，而且随麓体系 规模的增加会呈指数型的衰减。体系中的选择性激发造成的频率空间的拥挤也将 随着体系规模的增大而越来越明显，这将严重制约量予计算的有效进行。另一方 面，人们对核磁共振方案是否进行了真正的量子计算仍存在着争议。这是因为 c a v e s 等【2 驯对n m r 实验的理论研究证明，所有的n m r 实验都没有产生量子计算 需要的量子纠缠，因而只是模拟了经典计算，而不是真正的量子计算。 尽管目前的实验都只是在少数几个量予位上进行的，而且很多实验手段是具 有宏观系综特征的核磁共振，但对于量子计算的研究已经使我们重新认真思考了 诸如纠缠、退相干等问题。它将带给我们更多新的思维方式。 第三章量子随机行走与量子随机行走搜索算法 第三章量子随机行走与量子随机行走搜索算法 3 1 经典随机行走 经典随机行走是量子随机行走的基础，它可以用图g ( 矿，e ) 来表示，其中矿是 顶点集，e 是边集。每一条边可以用它所连接的点表示，即p = ( v ，v 。) 。当“，吒) e 且( k ，) e 时，我们说这个图是无向的。经典随机行走的一个重要参量是( 独立 于时间的) 变换矩阵m ，矩阵元m 。表示从顶点v j 到顶点v ，的跃迁几率。只有当一 对顶点通过一条边连通时这个几率不为0 ，即 m “o i f r p = 卜，v ，j e e ( 3 1 ) 著m 的非零矩阵元可以表示为鸩= l 吐，则称这个行走是无偏的，其中4 是顶点 v 的度( 即与顶点q 关联的边的数目) 。若图上所有顶点都有相同的度( 印，则称这 个图是正则的。在某一时刻r ，经典随机行走的状态由各顶点v y 的几率分布 p ( v ，f ) 描述。这个几率分布在每次变换矩阵m 作用后都会发生相应的变化， ，( v ，r ) = m 尸( v ，0 )( 3 2 ) 着g 是连通的，即任意两个顶点通过一系列边都相互连接，则行走将趋于稳定分 布n ，且这个分布不依赖于初态尸( v ，o ) 。若g 是正则的，则每个顶点的稳定分布 是均衡的。随机行走稳定分布的收敛性质可以通过膣兮删做聊投f ，培r f 历e ) 来描述， 其定义如下， 彳：、= m i n 扩i v f 丁：i j p ( v ，) 一厅i j ， 7 ：1 l 莉一九 坑。时将有较大 的峰值位置的偏移。我们对f 。的曲线进行了拟合，得到以下表达式 k 。= 1 彳每 ( 4 2 9 ) 、8 + 艿2 其中j v = 2 ”，代表数据库的大小 第四章相位嗓声对量子随机行走搜索算法的影响 | 芏| 43 仅甫系统跌差( 模型i ) 情况下气。达到最大时的循环次数f v s 数据库容量一= 1 0 9 2 ，o ”代表 占= 0 0 1 ” 代表占= 0 0 0 l ，”o 叶表占= o 0 0 叭，点线、虚线和实线分别是用( 4 2 9 ) 式拟合的结果 接着我们研究相位噪声对搜索成功几率只。的影响。图4 4 给出了在给定噪声 大小情况下找到目标态的最大几率四。与数据库容量”= 1 0 9 ：| v 之间的关系。仍旧 使用模型i ，在每一次改变数据库大小之后我们将算法循环相应的f 。次，得到p 伽 的最大值。从图中可以看到，当”较大时找到目标态的最大几率呈指数下降，这 说明：当误差不可避免地存在时，数据库的大小必须受到限制，否则搜索将会有 很大几率失败。黜可以用以下表达式拟合 学= 羔 其中咒为无噪声情况下找到目标态的几率。( 4 3 0 ) 式说明当v 斗o 。，只有占= 0 搜 索才能成功。 第四章相位噪声对量子随机行走搜索算法的影响 幽44 模型1 情况下找到h 标态的最大几率v s 数据库容量一= l 0 9 2 ，”o ”代表艿= 0 0 1 ，”代表 d = o 0 0 1 ”o 叶表艿；0 0 0 0 1 ，点线、虚线和实线分别是用( 43 0 ) 式拟合的结果 在实际实验中，除了系统误差外，往往还存在着随机误差，然而我们不可能 对所有这些误差做出精确的估计。因此在搜索时通常人们还是会取，次循环，此 时发现目标念的几率很有可能没有达到最大值。下面我们对这种情况进行模拟， 每次搜索我们均取扣，。图4 5 4 7 给出了竹= 6 ，7 ，8 ( 即数据库大小为 = 6 4 ，1 2 8 ，2 5 6 ) 时找到目标态的凡率随误差增长的变化情况。在这三个图中我们 用了三种不同的模型：图4 5 是仅含系统误差的情况，每次循环j 是一个常数( 模 型i ) ；图4 6 是仅含随机误差的情况，即每次循环占是一个平均值瓦= o 、标准偏 差为s 的高斯分靠随机数( 模型i i ) ；而图4 7 兼有两种误差，即每次循环5 是平 均值民0 、标准偏差为s 的高额分布随机数( 模型i i i ) 。对于图4 。6 和4 7 ，由于 其随机性，图中的每条曲线我们都进行了2 0 0 次模拟并取平均。从图4 5 q 7 中可 以看到，数据库容量n 越大，算法对相位噪声也越敏感。比较图4 5 与4 6 可以发 现，系统误差对于算法的影响比单纯的随机误差要大得多，而图4 7 得到的几率除 了部分涨落外几乎与图4 5 一致。这说明在实际实验中，除了对数据库的大小作出 限制外，更应注意系统误差的控制。 苎些童塑垡堕兰翌苎三堕垫堡耋丝塞墨婆堕整堕 图45j _ ：面三条舳线，模型i 情况下拽到目标态的几率v s 系统误差占；下面三条是相应的找到非目标态的几 牢的最人值 | 星| 4 6 l 。曲三条f l 线模型| l 情况下找到目标态的几牢v s 随机误差的标准偏差j t 随机误差的平均值皖= o 下衄三条足拥随的找到1 卜口标态的几率的最大值 第删章槌堡堡! 壁茎至堕塑堑枣垄壅墨鲨竺矍堕 凰47j ：厩三条曲线t 模型i i i 情况下找到目标态的几率v s 误差平均值坑，其标准偏差为j = o 1 ；下面三 条是相心的找到非目标态的几率的擐犬值 最后我们对搜索结果的分辨率作一个分析。这里，分辨率定义为找到目标态 的几率与找到非目标态的几率的最大值之差【3 8 】 j p = 只。一m a ) ( 怛，b ，p ) ( 4 3 1 ) 在实际实验中，这个分辨率也十分重要。例如在核磁共振实验中，最后结果的测 量是通过层析成像口6 】来完成的，它通过一个梯度脉冲来读取末态密度矩阵 p ( f ) = i f f ，( 唠渺( f ) i 的所有对角元，因此只要有足够的分辨率，在算法执行完毕以 后我们可以发现找到目标态的几率要远高于其它态，这意昧着算法仍然是成功的。 图4 5 4 6 也给出了与找到目标态对应的非目标态的几率的最大值，裉据它们的间 隙我们也能看到相应的分辨率的变化情况，例如在图4 5 n = 8 的情况下，当系统误 差从o 加2 5 ，发现目标态的几率从0 4 3 4 5 下降到0 0 1 4 1 ，而相应的分辨率由o 3 7 4 5 下降到o 0 0 8 3 。随着误差的增大，分辨率的下降速度要略慢于找到目标态的几率 的下降速度。 这一节我们对相位噪声的影响作了数值分析，我们发现随着占的增大，找到目 标态的几率的最大值及算法的最佳循环次数都会减小，其中系统误差对搜索的影 响要大于随机误差。在实际的实验中，相位翻转时伴随的各种误差是不可避免的。 例如，在核磁共振实验中，误差可能来自于不同辐射频率的脉冲信号，而在相干 原子系统构成的相位门中，失谐萤的偏差和激光强度的涨落也都会导致误差的产 生。在算法实施之前，我们应当先对这些误差进行相应的估计，并据此对数据库 第网章相位噪声对量子随机行走搜索算法的影响 的容量作出适当限制。以确保搜索的成功进行。 4 3 与g r o v e r 搜索算法的比较 这一节我们将量子随机行走搜索算法对相位噪声的响应和g v e r 搜索算法作 一个比较。f 如甜一章所说的，这两个算法在o r a c l e 调用中都用到了g r o v e r 扩散 算符g ，其中在g r o v e r 搜索算法中，g 算符是应用到整个数据库空间的( 相当于 随机行走中的格点空间) ，而量子随机行走搜索算法中的g 算符是作为硬币翻转算 符应用在硬币空间的，因此当相位噪声引入到这两个g 算符中时，算法的响应会 有类似的地方，也会有所不同。 首先我们仍然来看最佳循环次数r 的改变情况。在c 胁v e r 搜索算法中，相 位噪声对最佳循环次数的影响可以表示为【3 7 】 盘2 赢 哪2 ) 2 、4 + 艿2 比较( 4 2 9 ) 式，两者在形式上非常相似，( 4 1 3 2 ) 式的转折点位置大约在* 2 2 “2 ， 相位噪声对f ：。的影响要相对明显一些。 | 璺| 48 g r 0 v e r 搜索算法模型i 情巩下找到目标态的最大几率焉。v s 数据库容量h = 1 0 9 2 ，点线、虚线和实 线分别代表占= o 0 1 、占= 0 0 0 i 、占= o 0 0 0 1 对于搜索成功的最大几率，g m v e r 搜索算法也与量子随机行走搜索算法类似。 当数据库的容量肝较大时找到目标态的最大几率将呈指数下降，图4 8 是与图4 4 对应的g r o v c r 搜索算法下找到目标态的最大几率盛与数据库容量”= l o g ：之间 第叫章相位噪声对量子随机行走搜索算法的影响 的关系，5 分别为o o l ，o 0 0 1 ，o 0 0 0 l 。最大几率毪与数据库大小和相位噪声的 关系可表示为 踹，2 志 ( 4 3 2 ) 上式与( 4 _ 3 0 ) 式比较，形式上仍很相似。但必须注意的是在无噪声情况下，g r o v e r 搜索算法找到目标态的几率接近与l ，而量子随机行走搜索算法找到目标态的几率 只接近于1 2 。 图49 ( a ) v = 2 5 6 、占= o 2 5 时量子随机行走搜索算法找到各个格点的几率其中目标态位于第p 十格点 ( b ) = 2 5 6 、占= o 时拽到并个格点的几率 下面我们来讨论相位噪声对两个算法分辨率的影响，这也是两个算法对相位 噪声的响应的一个明显不同之处。对于g r o v e r 搜索算法，由于占的引入，所有找 到非目标态的几率都将会提高，仅目标态被找到的几率减少，因此随着噪声的增 加，其分辨率的下降速度要比找到目标态的几率的下降速度更快。而在量子随机 行走搜索算法中，由于作为硬币翻转算符的g 仅作用在m 维硬币空间，因此当占增 大，只有与目标态不相邻的态被找到的几率会提高，而目标态以及与它相邻的态 第姆章 相位噪声对量子随机行走搜索算法的影响 被找到的几率都会减少，见图4 9 ，因此分辨率下降的速度比找到目标态的几率的 下降速度慢，这也是为什么图4 5 4 7 中找到非目标态的几率的最大值下降的原因。 就分辨率而言，量子随机行走搜索算法抵御相位噪声的能力比g