量子算法与量子计算实验

论文关键词:量子算法量子计算量子比特纠缠

论文摘要:本文介绍了量子计算纠缠和量子比特的基本概念，系统阐述了几种主要的量子算法:Shor算法———大数质因子分解的量子算法;Grover搜索———无序数据库的搜索;Hogg搜索———高度结构化搜索。在对量子计算基本理论和量子算法有一定认识的基础上，进一步介绍了在量子计算实验方面起重要作用的二种体系:核磁共振、腔与原子体系。

Abstract:In this thesis，several basic conceptions of quantum computation are introduced，such as entanglement，quantum bit.Several kinds of main quantum algorit hms are illustrated，such as Shor algorit hm-t he quantum algorit hm for factoring，Grover search-t he search for t he disordering database，Hogg search-high structurization search.On t he basis of knowledge of basic t heories of quantum computation computing and quantum algo 2 rit hm，two kinds of systems which play important role in t he experiment of quantum computation was introduced，Nuclear magnetic resonance and cavi 2 ty atom system. Key words:Quantum algorithmQuantum computationQuantum bitEntanglement 量子计算是量子物理与计算机科学交汇而生的一门新兴学科。它的出现实质上是量子物理学向物质、能量和信息这三大领地的最后一块信息领域的进军。

一、量子计算的基本理论 1、纠缠 1935年，Schr dinger首先给出了纠缠态的定义:由空间分离的两个子系统构成的纯态，如果系统波函数不能分解为两个子系统波函数的乘积，那么这样的波函数表示的态称作两个粒子的纠缠量子态。1935年，Einstein，Podolsky和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维的Hilbert空间中的一个单位矢量。它所在空间的维数是随n呈指数型增长，这明显区别于经典体系中随n呈线性增长的态空间。在一个孤立的量子体系中，对态的操作应是幺正的、可逆的。因此，我们构造的量子逻辑门也应满足这个特征。

二、量子算法 1、Shor算法———大数质因子分解的量子算法 用经典计算机来进行大数质因子分解，随着N的增大，所需比特数(即内存)是呈指数倍的增长。按照组合数学理论，当计算规模随着问题的难度呈多项式型增长时，该问题为P(Polynomial)问题。对于P问题，我们在有限的时间内总能找到办法求得它的解。对于我们在有限的时间内不可能找到办法求得解的问题称之为NP(Non-Polynomial)问题。目前世界上应用最广也是最成功的加密方法-公开密钥RSA系统的核心思想就是利用大数在有限时间内不可有效质因子化这一结论。1995年，P.W.Shor提出一种量子算法，能将这一著名的NP问题化为P问题，矛头直指RSA方法，从而在全球掀起了量子计算的研究热浪。在Shor算法中，寻找一个大数的质因子问题被转化为寻找其余因子函数的周期。只要该周期被找到，并且为一个偶数，那么利用剩余定理，就能得到该大数的质因子。给定整数N，选取一个与N互质的数a(a不难看出，fa，N(x)的变化是有规律的，其变化周期为r=4。知道了这个周期，就可以利用孙子定理:设A=ar/2+1，B=a r/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、Grover搜索:无序数据库的搜索 Grover提出了一种算法:利用量子态的纠缠特性和量子并行计算原理，可以用最多n步的搜索寻找到所需项。Grover算法的思想极为简单，可用一句话“振幅平均后翻转”来概括。具体说来是以下几个基本步骤: ①初态的制备。运用Hadamard门将处于态|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的几率找到我们要找的数据项。Grover算法提出之后，引起了众人极大的兴趣。Grover算法中的翻转方法不仅被证明是最优化的搜索方式，而且也是抗干扰能力极强的方法。

3、Hogg搜索:高度结构化搜索 前面介绍过的NP问题中有一类名为可满足性问题(Satisfiability Problem，简称SA T问题)。一个典型的SA T问题是包括有n个变量的一个逻辑公式，要求给予其中每个变量一个赋值使逻辑公式为真。数学上已证明，解决SAT问题的代价是随着变量数的增加而呈指数型增长。然而对于某些简单的情况，人们可以利用问题中具有的规则结构来迅速准确地搜索出问题的解。例如对于1-SAT问题，用经典试探法进行搜索，找出解的代价为最多需用n步。对于量子计算而言，由于能进行量子并行计算，因而可以仅以一步的代价找出1-SAT问题的解。下面以有m个逻辑子句的1-SAT问题为例。与Grover搜索相似，我们先在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称为Hamming距离，d=d(r，s)=|r|+|s|-2|r∧s|，其中|r|和|s|分别表示r字节串和s字节串中含有比特为1的个数。|r∧s|表示r和s中共同含有比特为1的个数。

三、量子计算实验 与量子计算理论方面的飞速进展相比，量子计算的实验进展则要慢得多。本章主要介绍二种体系:核磁共振和腔与原子体系。 1、核磁共振(NMR) 核磁共振技术是目前在量子计算领域使用最为频繁的实验手段。运用这一技术手段，操作作用在1023数量级的分子系综的自旋态上，通过测量，得到这些分子的平均自旋态。虽然每个分子的自旋都可能不尽相同，但通过spin-e2cho技术可以按我们的意愿改变个别分子的自旋方向。由于核磁共振体系实质上是一个宏观系综，因而外部环境对它的消相干的影响极小。且样品的核自旋处于近独立的状态，几乎不受电子和分子的热运动的干扰。但是，宏观系综原则上没有量子特性，只有纯粹的量子系综才具有量子纯态的特征。只有当它被制备到一个特殊状态—赝纯态时，才能完成量子计算的工作。下面举例介绍实现两量子比特的Grover搜索的实验。实验中所用样品为C-13同位素标记的氯仿HCCL3。实验中用碳和氢的核自旋来标记|1>和|0>，其中13C的中心共振频率约为125MHz，1H的中心共振频率约为500M Hz。实验体系的哈氏量为H=2πnhJ ICZ IHZ+PH<+PC<+Henv其中第一项是13C与1H的自旋自旋耦合的相互作用项，J为耦合强度。第二项和第三项分别为1H、13C与磁场的耦合。磁场包括静磁场和射频脉冲场两部分，其中射频脉冲场用来从外部操纵核自旋的状态。第四项为环境造成的消相干项，与前面几项比较，Henv十分小，可以忽略不计。实验中设要搜索的项为|11>，所以各步骤如Grover搜索所介绍的那样。比较实验和理论，可以发现实验中存在一些误差。这些误差主要来自磁场和射频场的不均匀、初始时间的校正和信号衰减等。 2、腔与原子体系 腔量子电动力学(C-QED)体系是另外一种可以进行量子计算的量子系统。腔量子电动力学体系之所以可以实现对两位量子信息进行处理量子系统，一个重要原因就是腔中的辐射场与原子具有很强的非线性相互作用，这种相互作用的演化导致腔场和原子体系的本征态处于纠缠态。腔量子电动力学体系包含光腔和微波腔。这里我们主要介绍微波腔体系中应用Rydberg原子与微波腔相互作用实现的条件量子相移门(QPG)。条件量子相移门(QPG)需要对两量子位的如下变换: |a，b〉→ex p(i<δa，1δb，1)|a，b〉其中|a>，|b>分别代表两量子位的基矢|0>或|1>，而δa，1，δb，1为通常的克隆尼克符号。条件量子相移门(QPG)在两个量子态都处在|1>时，产生一个<角相移，而在其他情况下均保持不变。由于其他任何操作可以应用条件量子相移门(QPG)和单个量子位的旋转来实现，因而，条件量子相移门(QPG)是一个通用量子逻辑门。我们这里介绍的条件量子相移门(QPG)是用包含0个光子或1个光子的腔场和单个Rydberg原子作为量子位来实现的。控制量子位是0个光子腔场|a>=|0>或1个光子的腔场|a>=|1>而，目标量子位是Rydberg原子的两个能级|i>(定义|b>=|0>)和|g>(定义为|b>=|1>)。 实验中应用的Rb原子的能级除了目标量子位两个Ry2dberg原子的能级|i>和|g>以外，还包括一个相关的能级|e>。三个相关的Rydberg原子态分别代表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〉→ex p(iπδa，1δ b，1)|a，b〉这个过程实际实现了相移为π的条件量子相移门(Q P G)。

参考文献: ①L.Isaac，G.Neil，K.Mark.Experimental Implemen2tation of Fast Quantum Searching[J].Phys.Rev.Lett.1998， 80:3408-3411. ②A.Salomaa著，丁存生，单炜娟译.公钥密码学[M].北京:国防大学出版社，1998 ③M.R.Garey，D.S.Johnson.Computers and in2tractability[M]:A Guide to t he t heory of N P-Completeness. San Francisco:Freeman Press，1997 ④J.I.Cirac，Parkins.Schemes for atomic-state tele2portation[J].Phys.Rev.A.1994，50:R4441-R4444. ⑤R.Schack.Using a quantum computer to investigatequantum chaos[J].Phys.Rev.A，1998