（光学专业论文）基于双量子点分子实现deutschjozsa算法的研究.pdf

a s t u d y o f i m p l e m e n t i n g t h e d e u t s c h - j o z s a a l g o r i t h mw i t h d o u b l e q u a n t u m d o tm o l e c u l e s at h e s i s s u b m i t t e dt ot h ed e p a r t m e n to fp h y s i c s a n d t h ec o m m i t t e eo ng r a d u a t es t u d yo fe a s tc h i n an o r m a lu n i v e r s i t y f o rt h ed e g r e eo fm a s t e ro fs c i e n c e b y d uq i o n g ( 510 7 0 6 0 2 0 2 5 ) s u p e r v i s e db y a s s o c i a t ep r o f e s s o rl i uj i n - m i n g a p r i l2 0 10 s h a n g h a i 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文基于双量子点分子实现d e u t s c h j o z s a 算法 的理论研究，是在华东师范大学攻读硕士学位期间，在导师的指导下进行的研究工作 及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或 撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说 明并表示谢意。 作者签名：矗立芝至 日期：五咖年月弓l 同 华东师范大学学位论文著作权使用声明 基于双量子点分子实现d e u t s c h j o z s a 算法的理论研究系本人在华东师范 大学攻读学位期间在导师指导下完成的硕士学位论文，本论文的研究成果归华东师范大 学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和 相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允许学位 论文进入华东师范大学图书馆及数据库被奄阅、借阅；同意学校将学位论文加入全国博 士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用 影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文木， 于年月f 1 解密，解密后适用上述授权。 ( ) 2 不保密，适用上述授权。 导师签名速【弛 本人签名狸这 加f 口年j ，月31 日 幸“涉密”学位论文应是已经华东师范人学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范人学研究生中请学何论文“涉密”审批表方为有效) ，未经上 述部l j 审定的学位论文均为公开学位论文。此卢明栏不填写的，默认为公开学位论文，均适用 上述授权) 。 挂速硕士学位论文答辩委员会成员名单 姓名职称单位备注 陈扬骏教授华东师范大学主席 印建平教授华东师范大学成员 杨晓华教授华东师范大学成员 摘要 摘要 量子信息学是量子力学和信息科学相结合而产生的一门新兴的交叉学科，主 要包括量子通信和量子计算两个分支。由于量子力学的量子态叠加原理和量子纠 缠等特性，量子计算机能够极快地处理某些问题，展示其具备超越经典计算机计 算能力和信息处理方面的巨大潜力。当前，量子算法在各种系统中的物理实现是 量子信息学领域的研究热点之一。其中，基于半导体量子点的固态系统，因具有 易操作和可集成的特性，己成为最有希望真j 下实现量子计算机的系统之一，受到 许多研究人员的关注。 本文提出一种利用双量子点分子体系来实现d e u t s c h j o z s a 量子算法的理论 方案。在该方案中，量子比特被编码在耦合量子点中双电子的自旋单重态 i s = 0 个j ，) 一ij ，个) ) 压和自旋三重态l 丁) = 0 个山) + l 土个) ) 压上，而且量子比特之问 的库仑相互作用可以简化为i s i n g 相互作用形式，对具体物理参量的分析表明， 本方案有望基于现有量子点分子实验技术得以实现。利用双电子自旋的单重态和 三重态编码量子比特的优点在于：可有效保护量子比特避免低频噪声，也可抑制 超精细相互作用引起的退相干。本文的研究工作对于利用量子点分子体系实现其 他复杂的量子算法来说将是重要的一步，也有利于进一步加深理解将双量子点分 子应用于量子信息处理方面的研究。 关键词：量子点分子，d e u t s c h j o z s a 算法，电子自旋态，电子电荷态，库仑相互 作用 a b s t r a c t a b s t r a c t q u a n t u mi n f o r m a t i o ns c i e n c ei san e ws u b j e c tc o m b i n i n gq u a n t u mm e c h a n i c s a n dc l a s s i c a li n f o r m a t i o nt h e o r y i tm a i n l yi n c l u d e st w ob r a n c h e s ，n a m e l y , q u a n t u m c o m m u n i c a t i o na n dq u a n t u mc o m p u t a t i o n d u et oq u a n t u ms u p e r p o s i t i o np r i n c i p l e a n de n t a n g l e m e n tp r o p e r t i e s ，q u a n t u mc o m p u t e rc a ns o l v ec e r t a i np r o b l e m sq u i c k l y c o m p a r e dw i t hi t s c l a s s i c a lc o u n t e r p a r t ，w h i c hs h o w st h a tq u a n t u mc o m p u t e rh a s p o w e r f u la b i l i t yf o rc o m p u t i n ga n di n f o r m a t i o np r o c e s s i n g a tp r e s e n t ，t h er e a l i z a t i o n o fq u a n t u ma l g o r i t h mi nd i f f e r e n tp h y s i c a ls y s t e m si so n eo ft h eh o tp r o b l e m so f q u a n t u mi n f o r m a t i o nf i e l d d u et oe a s yt om a n i p u l a t ea n di n t e g r a t e ，t h es o l i ds t a t e s y s t e mo fs e m i c o n d u c t o rq u a n t u md o ta t t r a c t sm u c ha t t e n t i o no fs c i e n t i s t sa n dh a s b e c o m eo n eo ft h em o s t p o s s i b l e c a n d i d a t e sf o ri n d e e d r e a l i z i n gq u a n t u m c o m p u t a t i o n w e p r e s e n tas c h e m ef o ri m p l e m e n t i n gt h ed e u t s c h j o z s aa l g o r i t h mw i t hd o u b l e q u a n t u md o t m o l e c u l e s i nt h es c h e m e ，q u b i ti se n c o d e do nt h es i n g l e ts t a t e i s ) = m ) 一) 压a n dt h et r i p l e ts t a t ei 丁) = m ) + ) ) 压。f 觚。一e l e c t r o n s p i ns t a t e si nd o u b l ec o u p l e dq u a n t u md o t s a n dc o u l o m bi n t e r a c t i o nb e t w e e nt w o q u b i t sc a nb ee f f e c t i v e l yr e d u c e dt o t h ef o r mo ft h ei s i n g - m o d e li n t e r a c t i o n i ti s s h o w nf r o mt h ed e f i n i t ea n a l y s e so ft h ep h y s i c a lp a r a m e t e r st h a to u rs c h e m em i g h tb e e x p e r i m e n t a l l yr e a l i z a b l ew i t ht h ep r e s e n td o u b l e d o tm o l e c u l et e c h n i q u e s e n c o d i n g q u b i t so nt h es i n g l e ts t a t ea n dt h et r i p l e ts t a t ec a np r o t e c tq u b i t sf r o ml o w f r e q u e n c y n o i s ea n ds u p p r e s st h ed o m i n a n ts o u r c eo fd e c o h e r e n c ef r o mh y p e r f i n ei n t e r a c t i o n s m o r e o v e r , t h i ss c h e m ew o u l db ea ni m p o r t a n ts t e pt o w a r dm o r ec o m p l e xq u a n t u m c o m p u t a t i o nv i ad o u b l e d o tm o l e c u l e s w eb e l i e v e t h a to u rs c h e m em a yb eh e l p f u lt o f u r t h e ru n d e r s t a n dt h ea p p l i c a t i o no fd o u b l e - d o tm o l e c u l e st oq u a n t u mi n f o r m a t i o n p r o c e s s i n g k e yw o r d s ：q u a n t u md o tm o l e c u l e ，d e u t s c h j o z s aa l g o r i t h m ，e l e c t r o n i cs p i ns t a t e ， e l e c t r o n i cc h a r g es t a t e ，c o u l o m bi n t e r a c t i o n 日录 目录 第一章绪论1 1 1 量子计算与量子信息发展简介1 1 2 量子比特6 1 3 量子逻辑门和量子线路7 第二章量子算法1 1 2 1 量子计算机上的经典计算1 l 2 2 量子并行性12 2 3d e u t s c h j o z s a 算法1 4 2 4 腔q e d 中实现d j 算法18 2 5 小结2 2 第三章半导体双量子点分子系统2 3 3 1 引言2 3 3 2 量子点2 4 3 3 双电子量子点结构2 5 3 4 在双量子点分子系统中编码量子比特2 7 3 5 双量子点系统中几种常见量子门的实现3 0 3 6 小结3 8 第四章在双量子点分子系统中实现d e u t s c h j o z s a 算法3 9 4 1 引言3 9 4 2d j 算法和双量子点分子4 0 4 3d j 算法在量子点系统中的具体实现4 4 4 4 小结一4 6 第五章总结和展望。4 7 参考文献4 9 硕士期间待发表的论文。5 3 j 致谢：! ；z i i i i 第一章绪论 第一章绪论 量子计算与量子信息的研究可以追溯到几十年前，但真正引起广泛关注的是 2 0 世纪9 0 年代中期，这期间发现了s h o r 量子因子分解算法 1 】和g r o v e r 量子搜 寻算法 2 】，这两类算法展示了量子计算机从根本上超越经典计算机计算能力和 在信息处理方面的巨大潜力。与此同时，量子计算机和量子信息处理装置在物理 实现的研究，成为继并行计算机、生物计算机等之后的非串行计算体系的又一热 点。 量子计算和量子信息对人类社会最具影响也最为惊人的发现之一是，量子计 算机能够迅速破解广泛采用的r s a 密码系统。掌握量子计算能力的制高点已成 为关系信息安全的重要课题，不少国家已纷纷丌始启动和资助相关的研究项目。 1 1 量子计算与量子信息发展简介 2 0 世纪初叶，科学经历了一场出人意料的革命，物理学遇到一系列危机。当 时的经典物理学理论预言诸如存在包含无穷能量的“紫外灾难”、电子旋转必然进 入到原子核的内部等一些不可思议的现象。起初这些问题是通过在经典物理学中 附加特别的假设来解决，但随着人们对原子和辐射更好的了解，这些尝试性的解 释越来越让人困惑。经过p g 分之一世纪的混乱，危机n 2 0 t 廿纪2 0 年代早期达到高 潮，并导致量子力学这一现代理论的创立。量子力学一出现就成为科学不町缺少 的一部分，并已有无数成功应用的例子，包括原子结构、恒星核聚变、超导体、 d n a 结构和自然界基本粒子等的几乎所有方面。 量子力学的规则很简单，但即使是专家有时也会感到违反直观。量子计算与 量子信息的先驱长期存在着让量子力学更好地被世人理解的愿望。量子力学最著 名的批判者e i n s t e i n ，直到去世都个- z h q 匕己接受他帮助发明的这个理论 3 】。几代物理 学家一直在为使量子力学作出的预言更令人满意而奋斗。量子计算与量子信息的 一个目标就是增进我们对量子力学直观上的把握，使它的预言让人更明白。例如 在2 0 世纪8 0 年代早期，人们感兴趣的一个问题足，能否通过量子效应进行超光速 的信号传递，这按照e i n s t e i n 的相对论绝对不可能。解决这一问题的关键在于能 第章绪论 否克隆未知量子状态，即复制量子态。如果克隆是可能的，那么就有可能借助量 子效应进行超光速的信号传递。尽管克隆对经典信息而言非常容易，但是在量子 力学的一般意义下不可能。这条2 0 世纪8 0 年代发现的不可克隆定理是量子计算与 量子信息的早期成果之一。此后对不可克隆定理有不少改进，我们现在已掌握了 理解量子克隆设备能力的工具，这些工具反过来也用于理解量子力学的其他方 面。 2 0 世纪7 0 年代，许多科学家丌始了对单量子系统的完全能控性的研究。在这 之前，量子力学应用的典型做法是对包含大量量子力学系统的批量样本的总体控 制，但单个量子力学系统无法单独访问。随着对单量子系统的控制有了发展，如 有了捕捉单个原子的“原子阱”，可以使得原子跟环境分离并对原子行为进行多方 面的精密探测；扫描隧道显微镜可被用于移动单个原子和按要求排列原子；以及 可以运送单电子的电子设备等，量子计算与量子信息也获得了发展，并在这个领 域有了几项令人惊喜的发现。如果将完全控制单量子系统扩展到更复杂的系统 后，我们必将会发现更多新的、意外的现象。量子计算与量子信息为试图更好地 操作单量子系统的人们提供了一系列有价值的挑战性课题，也刺激了新的实验技 术的发展，还指出了实验研究最有意义的方向。反过来，控制单量子系统也把强 大的量子力学工具运用到量子计算与量子信息中，并对其研究起着根本作用。 尽管人们有强烈的兴趣，但是，到日自仃为止，建造量子信息处理系统只取得 初步的成功。在几个量子比特上进行几十步操作的小型量子计算机代表着量子计 算的最高水平。用于长距离保密通信的量子密码术的实验原型也已出现，并在某 些世纪应用的水平上或许会被采用，但是，制造解决实际问题的大规模量子信息 处理装置的技术，仍将是物理学家和工程师未来面临的巨大挑战。 a l a nt u r i n g 在1 9 3 6 年发表的一篇令人瞩目的论文宣告了现代计算机科学的 形成。t u m g 以一种抽象的方式详细描述了我们现在所说的可编程计算机，也就 是以他的名字命名的称之为t u r i n g 机的计算模型。t u r i n g i j e 明了存在一个通用 t u r i n g 机可以模拟任何其他t u r i n g 机；进而，他宣称通用t u r i n g 机完全刻画了算法 手段所能完成的所有任务，即任何可以由硬件执行的算法有通用t u r i n g 机上的等 价算法完成一模一样的任务。这个称茭j c h u r c h t u r i n g 论题的论断断言了在某一个 物理设备上可以完成的算法和数学上严格的通用t u r i n g 机概念的等价性。这个论 2 第一章绪论 题的广泛接受为计算机科学的理论发展奠定了基础。t u r i n g 的论文发表不久，世 界上建成了第一台电子计算机。到1 9 4 7 年，当j o h nb a r d e e n 、w a l t e rb r a t t a i n 和 w i l ls h o c k l e y 发明了晶体管之后，硬件的发展j 真正起飞，从那时起，计算机硬 件的能力以惊人的速度成长，以致1 9 6 5 年g o r d o nm o o r e 把这种成长概括为 m o o r e 定律，即计算机的能力以固定的速率成长，大约每两年增加一倍。令人吃 惊的是，从2 0 世纪6 0 年代开始，m o o r e 定律在几十年时间里都近似成立，然而， 大多数观察家预期这将在2 1 世纪的f i l l 2 0 年内结束。制造计算机的的传统方法在解 决规模上的困难时丌始显得力不从心，当电子器件越做越小的时候，它的功能丌 始受到量子效应的干扰。m o o r e 定律最终失效问题的一个可能解决办法是采用不 同的计算模式。量子计算理论就是这类模式的一种，量子计算基于量子力学的思 想进行计算。虽然传统计算机可以模拟量子计算机，不可能以用一种有效的方式 去模拟。量子计算机在速度上对经典计算机有本质的超越，这种速度上的优越性 太重要了，以致许多研究着相信在经典计算机和量子计算机的能力之| h j 存在着 无法跨越的鸿沟。 量子计算机的“有效”和“非有效”模拟指的是什么? 粗略地说，有效算法解决 问题需要的时间，是问题规模的多项式；相反，非有效算法需要超多项式时问， 典型情况是指数。2 0 世纪6 0 年代术7 0 年代初，人们注意到通过t u f i n g 机模拟的其 他计算模型。某个计算模型可以有效解决的问题在t u f i n g 杉k _ 1 2 也可以有效解决， 看来t u r i n g 术j l 作为计算模型的功能不亚于任何别的计算模型。这个观点概括为加 强的c h u r c h t u r i n g 论题：任何算法过程都叮以用t u f i n g 机进行有效模拟 5 ，6 】。 对加强的c h u r c h t u f i n g 论题的一个重大挑战出现在2 0 世纪7 0 年代中期。当时 r o b e r ts o l o v a y 和v o l k e rs t r a s s e n 证明通过随机化算法可以测试一个整数是否为素 数，也就是蜕，随机性是s o l o v a y s t r a s s e n 钡1 试算法的一个实质部分。该算法并不 确定一个整数是否一定是素数或合数，相反，该算法确定一个数是素数或合数的 可能性。对s o l o v a y s t r a s s e n 测试算法进行几次重复，就可以几乎肯定一个数是素 数或合数。s o l o v a y s t r a s s e n 沏, 0 试算法提出的时候没有已知的有效确定型测试算 法，于是，好像带有随机数发生器的计算机可以有效进行计算任务，而此计算任 务在经典的确定型t u r i n g 机上无法有效进行。这个发现激励人们寻找其他随机算 法，这方面已经取得很漂亮的结果，并成为一个活跃的研究方向。 第一章绪论 随机化算法对加强的c h u r c h t u f i n g 论题形成了挑战，暗示确定型 l u t i n g 机上 有无法有效求解的有效求解问题。这个挑战可以通过对加强的c h u r c h - - t u r i n g 论 题进行修改而得到解决：任何算法过程都可以用概率t u f i n g 机进行有效模拟。但 是，这种就事论事的修改令人不安，难道没有另外一种计算模型能有效求解 t u r i n g 计算模型不能求解的问题吗? 有什么途径能使我们找到一种能保证有效 模拟其他任何计算模型的计算模型? 在这个问题的启发下，1 9 8 5 年，d a v i dd e u t s c h 提出是否可以用物理学定律推 导出任何更强的c h u r c h t u f i n g 论题的问题 4 】。没有用特定假设的方法，他试图定 义一种能够有效模拟任意物理系统的计算装置。由于量子力学是物理学的最终定 律，d e u t s c h 很自然地想到在量子力学下的计算装置。这些装置，仿照了4 9 年前 t u f i n g 机定义的机器，现代量子计算机的概念终于产生。 d e u t s c h 的量子计算机模型可以解决经典计算机甚至是概率t u f i n g 机不能解 决的问题。随后十年内许多人努力改进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 f i n g 机，甚至概率t u f i n g 机更为强大的有力证据。 量子计算机功能强大的进一步证据出现在1 9 9 5 年，l o vg r o v e r 在证明没有结 构的搜索空间上进行搜索这个问题时发现，这个问题在量子计算机上的解决可以 被加速。虽然g r o v e r 算法没有s h o r 算法那样明显的加速，但搜索方法的广泛适用 性引起人们对g r o v e r 算法相当的关注。大约在s h o r 矛i g r o v e r 算法发现的同时，许 多人致力于f e y n m a n 在19 8 2 年建议的一个想法 7 】。f e y n m a n 指出在经典计算机上 模拟量子力学系统存在本质困难，并建议在量子力学原理的基础上构造计算机以 克服那些困难。1 9 9 0 年，几个研究小组使这个思想具体化，并证明在经典计算机 上不能够有效模拟量子力学系统。量子计算机未来的一个主要应用似乎是用来模 拟那些在经典计算机上难以模拟的量子力学系统，这对科学和技术领域有深远意 义。 量子计算机的发展离不丌量子算法的完善。但是，找到好的量子算法是有困 难的。一方面，人们难以避免经典思想的影响，为设计好的量子算法，我们应利 用量子效应去达到期望的算法目的；另一方面，纯粹的量子算法也并不一定真正 4 第一章绪论 有意义，算法必须超越所有已知的经典算法。这两方面使得构造新的量子力学算 法是未来的挑战。 一般而言，我们可能会问是否可以归纳出量子计算机与经典计算机的计算能 力的差别。如果果真如此，那究竟是什么使量子计算机比经典计算机更强大? 哪 类问题用量子计算机可以有效解决，与经典计算机可有效求解问题相比怎样? 量 子信息与量子计算中一件令人激动的事情是，我们对这些问题的答案知之甚少! 更好地理解这些问题是未来的巨大挑战。 在量子信息与量子计算发展的过程中，随着该领域的发展和成熟，也伴随产 生了它自己的子研究领域。其中，最引人瞩目的就是对量子纠缠现象的研究。纠 缠现象是量子力学独特的资源，在量子计算和量子信息的很多有意义的应用上起 着关键作用。近年来，人们为更深入理解纠缠现象付出巨大的努力。纠缠现象己 被视为一种基本的自然资源，其重要性可以和能量、信息、熵以及任何其他基本 资源相比。尽管还没有纠缠现象的完整理论，但在理解这一量子力学奇特性质方 面己取得一些进展。许多研究者相信对纠缠现象性质的进一步研究会推动量子信 息与量子计算新的应用与发展。 量子计算与量子信息教我们以物理的方式思考计算，我们发现这种做法能为 信息处理和通信带来许多新的令人鼓舞的动力，计算机科学家和信息论专家有了 一个值得探索的新的内容丰富的模型。的确，从广义上说，我们学到的任何物理 理论，不仅仅是量子力学，都可以作为信息处理和通信的基础。这种探索的结果， 也许有一天会导致发明远超过当今计算和通信系统能力的信息处理装置，并带来 对整个社会正面和负面的影响。 量子计算和量子信息必然向物理学家提出许多挑战，但长远看它为物理学本 身作出何种贡献却有些微妙。我们相信就像我们学会用物理的方式思考计算一 样，我们也能够学会用计算的方式思考物理学。虽然物理学主要集中于弄清基本 物体和简单系统，自然界的很多有趣方面只会出现在事物变大和变复杂的情形 中。化学和工程在一定程度上处理这样的复杂性，但绝大多数情况用的足特定的 手法。量子计算与量子信息传达的一个信息是，新的工具可以用来跨越微小和相 对复杂事物之间的鸿沟：计算和算法为构造和理解这类系统提供了系统化的手 段。应用这些领域的思想已经丌始为物理学带来新见解，我们希望整个方向未来 第一章绪论 将会发展成一个理解物理学各个分支的富有成果的方向。 1 2 量子比特 比特是经典计算和经典信息的基本概念，量子计算与量子信思建立在类似的 概念一量子比特的基础上 5 ，6 】。经典比特可以有状态0 和1 ，量子比特的状态对 应于量子力学态i o ) 或1 1 ) ，但是跟经典比特不同的是，量子比特的状态不仅可以 落在i o ) 或1 1 ) 上，还可以是i o ) 和1 1 ) 的线性组合，一般称之为叠加态： i y ) = 口l o ) + 1 1 ) ， ( 1 2 - 1 ) 其中口和是复数，满足归一化条件川2 + l p l 2 = 1 。在测量量子比特时，我们得 到i o ) 的概率为h 2 ，得到1 1 ) 的概率为蚓2 。从几何意义上看，就是量子比特的状 态为二维复向量空i 日j 中的单位向量。一个有用的图像是把量子比特的状态用如下 的几何形式表示 l 妙) = c 。s ( 墨 i 。，+ s i n ( 墨) p 徊i ，( 1 2 - 2 ) 其中秒和妒定义t - - 维单位球面上的一个点，可以由图1 1 表示。这个球面一般 称之为b l o c h 球面，它是使单个量子比特状态可视化的有效办法。不过，这种直 观的想象足有局限的，因为目前尚不能把b l o c h 球面简单地推广到多量子比特的 情形。 图1 1量子比特在b l o c h 球面上的表示 6 第一章绪论 测量将会改变量子比特的状态，将其从l o ) 和1 1 ) 的叠加态坍缩到与测量结果 相容的特定状态，这是量子力学的基本原理之一。对量子比特的一次测量只得到 量子比特状态的- - i ：l 特信息，但是，事实上只有测量无穷多完全相同的量子比特 才能确定等式( 1 2 1 ) 中的口和。如果不进行测量，一个量子比特代表多少信 息，又如何量化信息呢? 由下面介绍的多量子比特将会看到，量子比特的状态所 隐含的信息，将随着量子比特个数的增加而呈指数上升。 考虑两个量子比特，将有四个基态，记作l o o ) ，i l o ) ，1 0 1 ) ，1 11 ) ，一对量子比特 也可以处于这四个基态的叠加，因而双量子比特的量子状态包含相应基念的复系 数，也称为幅度或概率幅。这样描述双量子比特的状态向量为 i i f ，) = a 。i o o + a 。，1 0 1 ) + o ! 。i l o ) + a 。1 11 ) ， ( 1 2 - 3 ) 类似于单量子比特的情形，测量结果为工( z = 0 0 ，0 1 ，l o 或1 1 ) 的概率为l 口，1 2 ， 测最后，双量子比特处于i x ) 状态。归一化条件为i 口o 。1 2 + k 。1 2 + k 。1 2 + k 。1 2 = 1 。 对于一个双量子比特系统，可以只测肇其中一个量子比特，比如第一个。那么， 对第一个量子比特测量得到i o ) 的概率为i 口1 2 + i 。1 2 ，而测量后的状念将变为 怍半喾掣 ( 1 2 - 4 ) v l 口o o | + l “ 测量后被因子i 口。1 2 + i 。1 2 重新归一化后，仍满足归一化条件。 更一般地，可以考虑疗量子比特系统，这个系统的基态形如 _ 恐_ ) ，并 且量子状态由2 ”个幅度所确定。任意取甩= 5 0 0 ，这个数字就超过了整个宇宙原 子的估算总数，在任何传统计算机上存储所有这些复数都是不可想象的。然而可 以肯定，即使是包含几百个原子的系统，大自然也是要处理如此大量的数据的， 因此，对量子计算机的研究是人们探索自然的必然途径。 1 3 量子逻辑门和量子线路 经典计算机的线路由连线和逻辑门构成，连线用于在线路l 、日j 传送信息，而逻 辑门负责处理信息，把信息从一种形式转换为另一种。考虑一个经典单比特逻辑 第一章绪论 门，比如，非门。非门的作用是将比特的0 、l 状态交换，0 寸1 ，1 哼0 。那么是否 可以定义量子比特的量子非门，并且满足将量子态f o ) 和f 1 ) 交换呢? 如果有，它 需要满足什么条件呢? 设量子比特处于叠加态口i o ) + 纠1 ) 上，那么量子非门的作用就是把这个叠加 态中的l o ) 和1 1 ) 交换位置而变成口1 1 ) + 纠o ) 。基于线性性质，量子非门可以方便 地用矩阵形式表示 x 三阳 3 山 同时把量子态口i o ) + 1 1 ) 写成向量形式 那么量子非门的输出就是 x 纪 ( 1 3 - 2 ) ( 1 3 3 ) 因此单量子比特的量子门口 以由2z2 矩阵给出。习b 么对于作为量子门的矩阵有什 么限制呢? 由于量子态口i o ) + 1 1 ) 以及被量予非门作用之后的量子态口l o ) + 1 1 ) 都有归一化条件的限制，实际上，表示单量子比特门的相应矩阵u 要满足的条件 是酉性( u n i t a r y ) ，即u + u = ，其中u + 是u 共轭转置，是2 x2 单位矩阵。对 非门很容易验证x + x = i 。酉性限制是对量子门的唯一限制，每个酉矩阵都定义 一个有效的量子门。 另外几个经常会用到的量子门是z 门、h a d a m a r d l 、单比特任意旋转门( r ( o ) 操作) 和两比特受控非门( c n o t f ) 。z f 的形式是 z 三 m 3 卅 它的作用是保持i o ) 不变，而翻转1 1 ) 变成一1 1 ) 。h a d 锄a r d 门的形式为 第一章绪论 它的作用是 h 三黜爿 ( 1 3 5 ) ( 1 3 - 6 ) 即，= 乏习 ”， 处于i o ) 和1 1 ) 的量子念经过r p ) 操作后将变成： 薯襟0 ：) 3 却 l 尺寸“n 私+ s 孙 、 可以决定目标比特的变换。当控制比特处于l0 ) 念时，目标比特不发生改变，但 c n o t = 10 00 、 010 0 ooo1i ( 1 3 - 9 ) l 001o j 处于l o ) 和1 1 ) 的量子念经过c n o t 门操作后将变成： 9 ( 1 3 1 0 ) 、l，、l 啪吩+ 1 1 嘭 吣 上压上厄 专 专 吣 岭 驯 驯 厂、l o d 吵吵邮州啪渺 斗 专 斗j 叫 嘭岭旷 吣吣驯驯引引列引 厂，(、，l 第一章绪论 h 变换和c n o t 操作的量子逻辑门线路如图1 2 所示：图中是c n o t 操作中的控 制比特，0 由代表相应的目标比特。 图1 2 ：( a ) h 变换门示意图；( b ) 量子控制1 f fj 示意图 利用一系列的量子门作为基本元件，我们就可以构造量子线路来完成一些有 用的量子操作。线路的读法是从左到右。每条路表示量子线路中的连线，连线不 一定对应物理上的接线，而可能对应一段时间或一个从空间的一处移动到另一处 的物理粒子，如光子。图1 3 中的线路完成的是一件简单而有用的任务，它对换 两个量子比特的状态。要明白该线路完成对换操作，需要知道这一连串门在计算 基态k b ) 上的一系列作用， 第二章量了算法 第二章量子算法 1 9 8 2 年，著名物理学家f e y n m a n 在用经典计算机来模拟量子力学系统时， 首次提出了量子计算机和量子计算的概念 7 】。直到1 9 8 5 年，d e u t s c h 描绘了量 子计算机 4 】，并预言了量子计算机的潜在能力，量子计算才被人们所认识。1 9 9 4 年s h o r 提出的量子算法 1 】，大数因子化，第一次显示出量子计算的非凡实力， 及至后来在1 9 9 6 年g r o v e r 发现的在未整理数据库寻找目标的搜索算法 2 】，都使 得量子计算和量子计算机的理论和实验研究迅猛发展起来。 本章解释如何在量子计算机上做经典计算，给出量子计算机优于经典计算机 的一些例子，并总结已知的量子算法。 2 1 量子计算机上的经典计算 物理学家们相信，我们周罔的世界，包括经典逻辑线路，最终都可以用量子 力学进行解释。量子线路不能用于经典线路的直接模拟，这是因为酉量子逻辑门 具有内在的可逆性，而许多经典逻辑门，如与非门，本质上是不可逆的。 采用一种称为t o f f o l i f 的可逆门，任何经典线路都可以等价，仅需要使用包 含可逆元件的线路代替。t o f f o l i fj 有三个输入比特和三个输出比特，如图2 1 所示。 两个控制比特不受t o f f o l i i 、 作用的影响，第三个比特是目标比特，在控制比特都 置1 时翻转，否则不变。如果连续两次应用t o f f o l i 门到一组比特，相当于 ( 口，b ，c ) 专( 口，b ，c oa b ) 寸( 口，b ，c ) ，因此t 0 仃o l i f _ 是可逆门，逆是它本身。 t o 仃o l i 门虽以经典门形式出现，却也可作为量子逻辑门实现。由定义，t o 仃o l i 门的量子逻辑实现只是按t o 仟o l i 门同样的方式置换基态。例如量子t o 行0 l i 门作用 到状态| 1l o ) 上就翻转第三量子比特，因为前两量子比特均被置位( s e t ) ，就进入 状态1 1 1 1 ) 。虽然繁琐，但不难写出这个变换的8 x 8 矩阵， 第一二章量了算法 t = 并可证明这个矩阵是酉矩阵，从而t o 筋l i 门是合法的量子门。量子t o 行o l i 门 可以像经典t o 行o l i 门那样用于模拟不可逆逻辑门，并保证量子计算机可以进行任 何经典( 确定性) 计算机能够完成的计算。 输入输出 abca b c 7 oooo00 oo1oo1 ol0ol0 ollo11 1o0100 1o l l0 l 1lo1ll 111110 a b e - 厂、 口 b c a b 图2 1t o f f o l i fj 的真值表和线路表示 2 2 量子并行性 量子并行性是许多量子算法的一个基本特征，简言之，量子并行性使量子计 算机可以同时计算函数厂( x ) 在许多不同的x 处的值。设厂g ) ： o ，1 专o ，l 是具有 一比特定义域和值域的函数。在量子计算机上，计算该函数的一个简便方法是， 考虑初态为i x ，y ) 的双量子比特的量子计算机，通过适当的逻辑门序列，可以把 1 2 o 0 0 0 0 o 1 o o 0 o o o 0 o l o 0 o o o l o o 0 o o 0 1 o o o o 0 o 1 o 0 0 0 o 0 1 o o 0 o o o 1 0 0 o o 0 0 l o 0 0 0 o o 0 第- 二章量了算法 这个状态变换为l x ，夕o ( x ) ) ，这罩。表示加法是模2 的。第一个寄存器称为数据 寄存器，第二个称为目标寄存器，映射 z ，y ) - - - ) l x ，y o 厂( x ) ) 叫做u j ，可以证明 它是酉的。若y = 0 ，则第二个量子比特的木态就是厂( x ) 的值。 如图2 2 的线路，把u ，加到计算基以外的一个输入，数据寄存器中是叠加态 0 0 ) + 1 1 ) ) 乏，这可由h a d a m a r d 门作用到l o ) 上得到。于是应用u 可得态 去吣( 。) ) + 帆1 ) ) ) ( 2 2 - 1 ) 其中，不同的项同时包含f ( o ) 和厂( 1 ) ，看起来似乎同时对石的两个值计算了 ( 石) 。与经典的并行不同，那罩多重厂( x ) 电路同时运行，利用量子计算机处于 不同状态的叠加态能力，这里的单个f ( x ) 线路用米同时计算多个x 的函数值。 xx u f yy 龟 崎 图2 2 u ，把输入的| x ，y ) 变换成x ，少。厂( x ) ) ，这是同时计算厂( o ) 和厂( 1 ) 的量子线路 利用h a d a m a r d 变换，以上过程很容易推广到任意数目的量子比特情形，于 是就可以将刀个h a d a m a r d f 同时作用到甩个量子比特上。如图2 3 所示，就足 胛= 2 ，初态全为0 的情况，输出是 ( 掣 ( 掣瑚唧巾吵川m ) 亿2 司 我们可以用h 。2 表示h a d a r n a r d 门的并行作用，圆表张量积。 a v ， i_hr 砷门 土压 第一二章量了算法 图2 3 舣鼙子比特上的h a d a m a r d 变换日。2 。 更一般地，咒重量子比特上的h a d 锄a r d 变换从全l o ) 出发，得到 i 1 协 2 ” ( 2 2 - 3 ) 其中求和是对x 的所有可能取值，并用日咖表不这个作用。可见，h a d a m a r d 变换 产生了所有计算基态的平衡叠加，而且，它的效率非常高，仅用疗个门就产生了 2 ”个状态的叠加。 可以采用下述方法进行刀比特输a x 还让单比特输出函数f ( x ) 的量子并行 计算。制备刀+ l 量子比特的状念i o ) 锄1 0 ) ，对6 订聆位应用h a d 锄a r d 变换，并连接 实现u s 的量子线路。于是就产生状态 了lx z l x ) l 厂g ” ( 2 2 - 4 ) 在某种意义上，表面上似乎只进行了一次厂计算，量子并行性却使厂的所有可能 值同时被计算出来。 2 3d e u t s c h j o z s a 算法 对图2 2 的线路稍加修改，就可以用d e u t s c h j o z s a ( d j ) 量子算法的实现来说 明量子线路如何超越经典算法。d j 算法把量子并行性和量子力学中量子叠加原 理的性质结合起来了。如果有两个量子比特，第一个处于态i o ) ，第二个处于态 1 1 ) ，对它们分别施加h a d a m a r d 门操作，那么，两个量子比特将分别处于态 1 4 辜 第二章量了算法 0 0 ) + 1 1 ) ) 互和0 0 ) 一1 1 ) ) 至上。在图2 4 所示的线路中，我们将分别分析各个步 骤产生的态。 xx 廿廿 u f 囡 ) ) 0 以 图2 4 实现d e u t s e h - j o z s a 算法的量子线路 输入状念为 i ) = 1 0 1 5 ( 2 3 - 1 ) 通过两个h a d a m a r d 门之后，给出 慨) = i 10 0 ) + 1 1 ) o )