量子算法与量子估算实验-化学学论文论文关键词:量子算法量子估算量子比特纠缠论文摘要:本文介绍了量子估算纠缠和量子比特的基本概念,系统论述了几种主要的量子算法:Shor算法———大数质因子分解的量子算法;搜索———无序数据库的搜索;Hogg搜索———高度结构化搜索。在对量子估算基本理论和量子算法有一定认识的基础上,进一步介绍了在量子估算实验方面起重要作用的二种体系:核磁共振、腔与原子体系。编辑。:,,,.,-,-,-earch.2rithm,,2.:量子估算是量子化学与计算机科学交汇而生的一门新兴学科。
它的出现实质上是量子化学学向物质、能量和信息这三大领地的最后一块信息领域的挺进。一、量子估算的基本理论1、纠缠1935年,首先给出了纠缠态的定义:由空间分离的两个子系统构成的纯态,假若系统波函数不能分解为两个子系统波函数的乘积,这么这样的波函数表示的态叫做两个粒子的纠缠量子态。1935年,,和Rosen首先讨论了一个具体的两粒子纠缠量子态。在这个知名的实验中,两粒子的纠缠量子态为:|Ψ〉=?a,bδ(a+b-c0)|a|b〉其中a,b分别为粒子1和粒子2的位置或动量,C0为常数。这个纠缠态的一个最显著的特点是:其中任何一个子系统的数学量的观测值(位置或动量)都是不确定的。并且,倘若其中的一个子系统的数学量的观测值处于一个确定的值,这么我们就可以确定另外一个子系统的相应化学量观测值。2、量子比特量子比特有微观体系表征,如原子、核载流子或光子等。|1>和|0>可以由原子的两个基态来表示,也可以由核载流子或光子的不同极化方向来表征。与精典比特明显不同的是,量子比特|1>和|0>之间存在着许多中间态,即|1>和|0>的不同迭加态,比如12(|0>+|1>)表示一个两子比特同时储存着0和1。
因而,对于位数相同的n个比特,量子比特可以储存2n倍的精典比特所能储存的信息。对于两个量子比特的体系,其完备基由四个布尔态|00>、|01>、|10>和|11>组成。考虑它们之间的迭加,我们可以发觉,|10>+|11>=|1>(|0>+|1>),这是由两个量子比特构成的直积空间。而|11>+|00>或|01>+|10>则不能再写成直积方式。前面这些情况就是上面提及的纠缠。对于一个处于纠缠状态的体系,我们不能准确地强调其中某一个量子比特是处于|1>还是|0>。更通常的纠缠态是处于2n个布尔态的n个精典比特组成的迭加态。|Ψ〉=?11„1x=00„0Cx|x〉其中Cx可以是复数而且满足?x|Cx|2=1。当Cx=12n时,称为等幅迭加态。这些等幅迭加态在以下要介绍的各量子算法中常常被用作初态。从上式也能看出,|Ψ>是一个2n维的空间中的一个单位矢量。它所在空间的维数是随n呈指数型下降,这显著区别于精典体系中随n呈线性下降的态空间。在一个孤立的量子体系中量子物理学下载,对态的操作应是幺正的、可逆的。因而,我们构造的量子逻辑门也应满足这个特点。二、量子算法1、Shor算法———大数质因子分解的量子算法用精典计算机来进行大数质因子分解,随着N的减小,所需比特数(即显存)是呈指数倍的下降。
根据组合物理理论,当估算规模随着问题的难度呈方程型下降时,该问题为P()问题。对于P问题,我们在有限的时间内总能找到办法求得它的解。对于我们在有限的时间内不可能找到办法求得解的问题称之为NP(Non-)问题。目前世界上应用最广也是最成功的加密方式-公开秘钥RSA系统的核心思想就是借助大数在有限时间内不可有效质因子化这一推论。1995年,P.W.Shor提出一种量子算法,能将这一知名的NP问题化为P问题,矛头直指RSA方式,因而在全球掀起了量子估算的研究热浪。在Shor算法中,找寻一个大数的质因子问题被转化为找寻其余因子函数的周期。只要该周期被找到,但是为一个质数,这么借助剩余定律,能够得到该大数的质因子。给定整数N,选定一个与N互质的数a(a不难看出,fa,N(x)的变化是有规律的,其变化周期为r=4。晓得了这个周期,就可以借助儿子定律:设A=ar/2+1,B=ar/2-1,其中r必须为奇数,且ar/2mod(N)?1。求出A、B以后,再分别求A、N和B、N的最大公素数(gcd)。设C=gcd(A,N),D=gcd(B,N)这么一定有C×D=N,即N被成功地质因子化。
Shor算法的关键在于求出大数N的余因子函数的周期r。不过,因为余因子函数的周期r不能在量子估算中被有效测出,因而在Shor算法中需利用量子离散傅立叶变换,将余因子函数的周期换成另一个可测的周期。2、搜索:无序数据库的搜索提出了一种算法:借助量子态的纠缠特点和量子并行估算原理,可以用最多n步的搜索找寻到所需项。算法的思想极为简单,可用一句话“振幅平均后翻转”来概括。具体说来是以下几个基本步骤:?初态的制备。运用守门员处于态|0>和|1>的各量子比特转化为等幅迭加态。?设数据库为T[1,2,,N]共,n项。设其中满足我们要求的那一项标记为A。于是在T中搜索A类似于求解一个单调函数的根。运用量子并行估算可以将A所在态的相位旋转180?,其余各态保持不变。即当T[i]=A时,降低一个相位eiπ。?相对各态的振幅的平均值作翻转。这一操作由幺正矩阵k1,k2„knD完成,其表达式为Dij=2/N,Dij=-1+2/N。?以上??两步可以反复进行,每进行一次,称为一次搜索。可以证明,最多只需搜索N次,便能以小于0.5的机率找到我们要找的数据项。
算法提出以后,导致了众人极大的兴趣。算法中的翻转方式除了被证明是最优化的搜索方法量子物理学下载,并且也是抗干扰能力极强的方式。3、Hogg搜索:高度结构化搜索上面介绍过的NP问题中有一类名为可满足性问题(m,简称SAT问题)。一个典型的SAT问题是包括有n个变量的一个逻辑公式,要求给与其中每位变量一个形参使逻辑公式为真。物理上已证明,解决SAT问题的代价是随着变量数的降低而呈指数型下降。但是对于个别简单的情况,人们可以借助问题中具有的规则结构来迅速确切地搜索出问题的解。比如对于1-SAT问题,用精典试探法进行搜索,找出解的代价为最多需用n步。对于量子估算而言,因为能进行量子并行估算,因此可以仅以一步的代价找出1-SAT问题的解。下边以有m个逻辑谓词的1-SAT问题为例。与搜索相像,我们先在n个量子比特上制备一个等幅迭加态作为初始态,即|Ψ〉=2-n/2?n-1s=0|S〉。另外,我们需设计好两种幺正操作R和U,其中R为对角矩阵,其归一化对角元为Rss=2cos[(2c-1)π/4]m=质数icm=质数。(3.3.1)式中的c(0(3.3.2)其中d称为距离,d=d(r,s)=|r|+|s|-2|r?s|,其中|r|和|s|分别表示r字节串和s字节串中富含比特为1的个数。
|r?s|表示r和s中共同富含比特为1的个数。对于以上1-SAT问题,其实有m个变量是约束的,而剩余的n-m个非约束的变量则对应于2n-m个解。对于1-SAT问题,用Hogg算法能决定性地一步找到解。假如通过一步逻辑操作难以明晰地发觉解,则意味着该问题无解。不难看出,Hogg搜索的效率远低于上节介绍的搜索。这两种搜索的差异在于,Hogg搜索借助了数据库的结构信息,从而能将一个NP问题转化为P问题。而算法解决不了NP问题,它相对于精典搜索只是增强了搜索效率。Hogg搜索的另一个优势在于具有强的抗消相干能力。因为它的逻辑步数少,因此消相干效应对其影响十分小。三、量子估算实验与量子估算理论方面的急速进展相比,量子估算的实验进展则要慢得多。本章主要介绍二种体系:核磁共振和腔与原子体系。1、核磁共振(NMR)核磁共振技术是目前在量子估算领域使用最为频繁的实验手段。运用这一技术手段,操作作用在1023数目级的分子系综的载流子态上,通过检测,得到这种分子的平均载流子态。其实每位分子的载流子都可能不尽相同,但通过spin-e2cho技术可以按我们的意愿改变某些分子的载流子方向。
因为核磁共振体系实质上是一个宏观系综,因此外部环境对它的消相干的影响极小。且样品的核载流子处于近独立的状态,几乎不受电子和分子的热运动的干扰。并且,宏观系综原则上没有量子特点,只有纯粹的量子系综才具有量子纯态的特点。只有当它被制备到一个特殊状态—赝纯态时,能够完成量子估算的工作。下边举例介绍实现两量子比特的搜索的实验。实验中所用样品为C-13核素标记的乙酸HCCL3。实验中用碳和氢的核载流子来标记|1>和|0>,其中13C的中心共振频度约为,1H的中心共振频度约为。实验体系的哈氏量为H=2π+PH,所以各步骤如搜索所介绍的那样。比较实验和理论,可以发觉实验中存在一些偏差。这种偏差主要来自磁场和射频场的不均匀、初始时间的校准和讯号衰减等。2、腔与原子体系腔量子电动热学(C-QED)体系是另外一种可以进行量子估算的量子系统。腔量子电动热学体系之所以可以实现对两位量子信息进行处理量子系统,一个重要诱因就是腔中的幅射场与原子具有很强的非线性互相作用,这些互相作用的演变引起腔场和原子体系的本征态处于纠缠态。腔量子电动热学体系包含光腔和微波腔。
这儿我们主要介绍微波腔体系中应用原子与微波腔互相作用实现的条件量子相拉门(QPG)。条件量子相拉门(QPG)须要对两量子位的如下变换:|a,b〉?exp(i,|b>分别代表两量子位的基矢|0>或|1>,而δa,1,δb,1为一般的克隆尼克符号。条件量子相拉门(QPG)在两个量子态都处在|1>时,形成一个=|0>或1个光子的腔场|a>=|1>而,目标量子位是原子的两个基态|i>(定义|b>=|0>)和|g>(定义为|b>=|1>)。实验中应用的Rb原子的基态不仅目标量子位两个原子的基态|i>和|g>以外,还包括一个相关的基态|e>。三个相关的原子态分别代表Rb原子的主量子数n=51(|e>),n=50(|g>)和n=49(|i>)。原子的基态|e>和|g>与微波腔场发生共振互相作用,而原子基态|g>和|i>之间通过另外的微波场形成耦合。当原子处于基态|i>或则腔场处于|0>,原子与腔场的系统状态不发生变化,而当原子腔场的初始处于|g,1>态时,控制原子的速率使原子|g>与|e>量子态在腔场中经历一个2π的拉比振荡,|g,1>态演变为-|g,1>=exp(πi)|g,1>。
因此系统的演变可以描述为:|a,b〉?exp(iπδa,1δb,1)|a,b〉这个过程实际实现了相移为π的条件量子相拉门(QPG)。参考文献:?L.Isaac,G.NEil,K.Mark.[J].Phys.Rev.Lett.1998,80:3408-3411.?A.著,丁存生,单炜娟译.私钥密码学[M].上海:国防学院出版社,1998?M.R.Garey,D.S..[M]:P-.:,1997?J.I.Cirac,.-[J].Phys.Rev.A.1994,50:R4441-R4444.?R..[J].Phys.Rev.A,1998