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=偶数ic m=奇数。(3.3.1)式中的c(0<c<m)为赋值的不相容数。U rs=22(n21)/2cos[(n-m+1-2)dπ/4] m=偶数2-n/2eπi(n-m)/4(-j)d m=奇数
(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-SAT问题,显然有m个变量是约束的,而剩余的n-m个非约束的变量则对应于2n-m个解。对于1-SAT问题,用Hogg算法能决定性地一步找到解。如果通过一步逻辑操作未能明确地发现解,则意味着该
问题无解。不难看出,Hogg搜索的效率远高于上节介绍的Grover搜索。这两种搜索的差别在于,Hogg搜索利用了数据库的结构信息,因而能将一个NP问题转化为P问题。而Grover算法解决不了N P问题,它相对于经典搜索只是提高了搜索效率。Hogg搜索的另一个优势在于具有强的抗消相干能力。由于它的逻辑步数少,因而消相干效应对其影响非常小。
三、量子计算实验
与量子计算理论方面的飞速进展相比,量子计算的实验进展则要慢得多。本章主要介绍二种体系:核磁共振和腔与原子体系。
1、核磁共振(NMR)
核磁共振技术是目前在量子计算领域使用最为频繁的实验手段。运用这一技术手段,操作作用在1023数量级的分子系综的自旋态上,通过测量,得到这些分子的平均自旋态。虽然每个分子的自旋都可能不尽相同,但通过spin-e2cho技术可以按我们的意愿改变个别分子的自旋方向。由于核磁共振体系实质上是一个宏观系综,因而外部环境对它的消相干的影响极小。且样品的核自旋处于近独立的状态,几乎不受电子和分子的热运动的干扰。但是,宏观系综原则上没有量子特性,只有纯粹的量子系综才具有量子纯态的特征。只有当它被制备到一个特殊状态—赝纯态时,才能完成量子计算的工作。下面举例介绍实现两量子比特的Grover搜索的实验。实验中所用样品为C-13同位素标记的氯仿HCCL3。实验中用碳和氢的核自旋来标记|1>和|0>,其中13C的中心共振频率约为125MHz,1H的中心共振频率约为500M Hz。实验体系的哈氏量为H=2πnhJ ICZ IHZ+PH<IH<+PC<IC<+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
