（微电子学与固体电子学专业论文）基于遗传算法的量子可逆逻辑电路综合方法研究.pdf

基于遗传算法的量子可逆逻辑电路综合方法研究 摘要 随着集成电路的集成度越来越高，电子器件的内部量子效应越来越明显，制 造计算机的传统方法在提高集成度上越来越力不从心；集成电路能耗导致计算机 芯片发热，也影响了芯片集成度的进一步提高。量子逻辑电路实现都是可逆操作， 不存在热耗散，从理论上解决了芯片发热问题，而且其计算能力较传统电路有巨 大提高，因此引起了人们极大的兴趣。本文阐述的重点是量子电路的可逆逻辑综 合问题。 量子可逆逻辑电路综合主要是研究在给定的量子门和量子电路的约束条件 及限制下，找到最小或较小的量子代价电路实现所需电路逻辑功能。本文介绍了 现在对此方面的研究现状和成果，探索了量子电路综合方法的规律，并提出一种 将遗传算法应用于量子可逆逻辑电路综合的新方法。这个方法将量子逻辑门的功 能用矩阵的数学模型表示，用遗传算法作全局搜索工具，实现了合成、优化同步 进行，在实验中取得了良好效果，展示了此方法在高阶量子电路综合问题上的应 用前景。 本文详细介绍了量子逻辑门的计算原理和遗传算法应用在量子电路综合问 题上的实现方法以及考虑物理实现、完备性、不同量子门代价和算法性能各方面 建立门库的过程。在三阶、四阶电路综合实验中，分析了新方法的性能，此方法 很好的利用了遗传算法在全局搜索中的强大功能，并巧妙的将量子可逆电路的消 去规则加入算法实现中对算法做出改进，用实验数据体现了此方法的可调试性 强，适用性和实用性高的特点。 关键词：可逆逻辑；量子电路；综合；遗传算法 r e s e a r c ho ft h eq u a n t u mr e v e r s i b l el o g i cc i r c u i t ss y n t h e s i s b a s e do ng e n e t i c a l g o r i t h m a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi ct e c h n o l o g y , c l a s s i c a lm e t h o do fp r o d u c eh a s l i t t l ea b i l i t yt or i s ei n t e g r a t i o nm a s t e r i n g t h ee n e r g yl o s so fi n t e g r a t e dc i r c u i tc a u s e t h eh e a tg e n e r a t e df r o mc o m p u t e rc h i p s i td e l a y st h ei n c r e a s eo fc h i pi n t e g r a t i o nl e v e l t h eo p e r a t i o no fq u a n t u ml o g i c a lc i r c u i ti sr e v e r s i b l e i td o e sn o th a v eh e a tg e n e r a t i n g p r o b l e m ，s oc a r ls e t t l et h eh e a tg e n e r a t e df r o mc h i p sf r o mt h e o r y a n di t h a sf a s t e r c o m p u t es p e e dw h i c hi st h eo t h e rr e a s o nm a k e sp e o p l eg i v em o r e a n dm o r ea t t e n t i o n s t ot h i sd o m a i n t h i sp a p e re x p a t i a t e so ns y n t h e s i so fq u a n t u mr e v e r s i b l el o g i cc i r c u i t s s y n t h e s i so fq u a n t u mr e v e r s i b l el o g i cc i r c u i t sm e a n st oa u t o m a t i c a l l yc o n s t r u c t d e s i r e dq u a n t u mr e v e r s i b l el o g i cc i r c u i tw i t hm i n i m a lq u a n t u mc o s t t h i sp a p e r i n t r o d u c e st h ec u r r e n ts i t u a t i o na n dp r o d u c t i o no ft h er e s e a r c ho fs y n t h e s i so f q u a n t u mr e v e r s i b l el o g i cc i r c u i t sa n di t sr u l e s w ep r e s e n t an e wm e t h o dt os y n t h e s i z e q u a n t u mr e v e r s i b l el o g i c c i r c u i t sb a s e do ng e n e t i ca l g o r i t h m t h ef u n c t i o no f q u a n t u ml o g i cg a t e si se x p r e s s e di nt e r m so f m a t r i x t h e nw eu s eg e n e t i ca l g o r i t h ma s s e a r c ht o o lt os y n t h e s i sr e v e r s i b l el o g i cc i r c u i t s t h i sm e t h o dg o tg o o dp e r f o r m a n c e w h i c hp r o v e sab r i g h ta p p l i c a t i o np r o s p e c ti ns y n t h e s i so fh ig h o r d e rq u a n t u m c i r c u i t s t h i sp a p e ri n t r o d u c e st h ec a l c u l a t i o np r i n c i p l eo fq u a n t u ml o g i cg a t e sa n d h o w t os y n t h e s i z eq u a n t u mr e v e r s i b l el o g i cc i r c u i t sw i t hg e n e t i ca l g o r i t h m t h ep r o c e s so f f o u n d a t i o ng a t el i b r a r ys h o u l dc o n s i d e rp h y s i c a lr e a l i z a t i o n ，i n t e g r i t y , p e r f o r m a n c e a n dd i f f e r e n tq u a n t u mc o s to fd i f f e r e n tg a t e s t h en e ws y n t h e s i sa l g o r i t h mi sa n a l y z e d i nt h r e e o r d e ra n df o u r - o r d e rc i r c u i te x p e r i m e n t s ，w h i c hu t i l i z ep o w e r f u ls e a r c h f u n c t i o no fg e n e t i ca l g o r i t h ma n di si m p r o v e db ya d d i n gr e m o v er u l ei n e x p e r i m e n t a l r e s u l t sd e m o n s t r a t et h a tt h ea l g o r i t h mh a sg o o dp r a c t i c a b i l i t y , a p p l i c a b i l i t ya n dd e b u g a b i l i t y k e y w o r d ：r e v e r s i b l el o g i c ；q u a n t u mc i r c u i t s ；s y n t h e s i s ；g e n e t i ca l g o r i t h m 插图清单 图2 1 控制非门“9 i 虱2 2 控南0 一控韦0u 门1 0 图2 - 3t o f f o li 门1 0 图2 43 3 可逆逻辑电路示例_ 1 3 图2 - 5 量子线位不相邻的t o f 门1 4 图2 6 结构调整示意图1 4 图2 7 最终调整电路图1 4 图3 - 1 后向合成法举例1 7 图3 - 2 双向合成法举例“1 7 图3 - 3m a s l o v 模板”l8 图3 4 模板优化应用示例”1 9 图3 5r m 展开式法举例2 0 图4 1 遗传算法的迭代过程2 4 图4 2 交叉示意图”2 6 图4 3 变异操作示意图”2 7 图4 4 三阶完整t o f 门库“2 8 图5 1 三阶程序运行结果曲线3 3 图5 2 三阶实验最优结果电路3 4 图5 3 四阶门库”3 5 图5 4 四阶程序运行结果曲线3 5 图5 5 四阶实验最优结果电路3 6 图5 - 6 适应度为一4 的局部最优电路一3 7 图5 - 7 适应度为一5 的局部最优电路一3 7 表格清单 表2 - 1 图2 - 4 电路真值表1 3 表5 一l 算法性能分析比较3 6 表5 - 2 加入消去规则后的实验结果分析3 7 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金自巴王些太堂 或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文储签名：彳、气 签字日期沙了年归加日 学位论文版权使用授权书 本学位论文作者完全了解盒魍三些态堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权盟 王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： ， 才、屯 签字日期：, o 。7 年f 月沙日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日期了7 年钐月弦日 电话： 邮编： 致谢 本论文在选题和研究过程中受到解光军教授的悉心指导。解老师不仅 学识渊博、治学严谨，而且待人诚恳，诲人不倦。解老师不仅授我以文， 而且教我做人。他对科学严谨认真的态度和高尚的品德，是我学习的榜样。 这两年多来从解老师那里学到的知识必将使我终身受益。衷心感谢导师的 培养、支持和教诲! 两年多来，老师们不仅在学业上给予我精心的指导， 而且在思想、生活方面给予我无微不至的关怀，在此谨向他们致以诚挚的 谢意和崇高的敬意! 感谢合肥工业大学量子智能信息处理实验室的各位同学，在一起奋斗 的日子让人难忘! 感谢我的师兄范海秋，肖晗等，他们在我学习的过程中给予很多指导 和帮助。感谢我的同学程心，赵亮，张亚南，程从俊所给予的帮助! 感谢 量子组的彭斐，吴天吴在我完成论文的过程中所给予的帮助! 特别感谢我的父母赐予了我生命，对我一直无微不至的关怀与照顾! 你们对我的养育之恩，我终生无以回报! 感谢文中引用过文献的所有作者们，感谢所有关心、支持和帮助过我 的老师、同学和朋友! 乐亮 2 0 0 9 年4 月 第一章引言 1 1 研究背景 从2 0 世纪6 0 年代开始，摩尔定律在几十年的时间里都是近似成立的，然 而，大多数观察家预期这将在2 1 世纪的前2 0 年内结束：当电子器件越做越小 的时候，其内部量子效应也越来越明显，制造计算机的传统方法在进一步提高 集成度上越来越显得力不从心；与此同时，集成电路能耗会导致计算机芯片发 热，这点也影响了芯片集成度的进一步提高。集成电路功耗主要来自于计算 过程中的不可逆操作，例如，对于两个比特的异或操作，只有一个比特的输出。 这个过程中损失了一个自由度，这正是一个不可逆操作，而损失掉的自由度就 转化为热量耗散掉了。所以消除能耗的关键就是寻找可逆操作替代计算过程中 的不可逆操作。 量子计算就是基于量子力学而非经典物理学的思想进行的计算，量子计算 中每一步操作都可以用一个幺正变换来表示，因而每一个操作都是可逆的。量 子计算机不丢失输入信息，不存在热耗散，从理论上解决了芯片的热耗问题。 量子计算机可以等效为一个量子图灵机。量子图灵机是一个抽象的数学模 型，理论上己证明，量子图灵机可以等价为一个量子逻辑电路。类似于经典计 算机是由包含连线与逻辑门的电路构建而成，量子计算机是由包含连线和量子 逻辑门级联形成、处理量子信息的量子电路建造的。 量子计算和量子信息技术是迅猛发展的新兴学科。由于它潜在的巨大实际应 用价值和重大的科学理论意义，正引起越来越多的关注。量子电路可逆逻辑优化 问题是量子可逆逻辑综合的重要组成部分。量子可逆逻辑综合又是量子计算和量 子信息技术研究不可或缺的内容。量子计算机中，信息的基本操作元件是量子逻 辑门，量子比特是信息的载体，量子比特的信息经量子逻辑门操作处理后，最后 得到计算结果。所有的量子逻辑门都是可逆操作，量子逻辑门不带有信息的擦除 操作( 输入信息的丢失) ，在理论上也就不存在热耗散的极限，从而杜绝了经典 计算机从根本上无法解决的热耗散严重影响器件正常功能的问题。不导致信息丢 失的设计称为可逆的。b e n n e t t 证明了只要组成可逆的门网络，做到能量零损耗是 可能的。l a n d a u r 证明了要使得电路中的能量无消耗使用可逆门是必要的，但不 是充分的。因此，可逆性将成为未来电路设计的基本特性。在未来诸多具有可逆 性质的研究和应用中，量子可逆计算都将扮演着重要的角色。 在最近几十年中，已经提出了多种可逆的量子逻辑门。关于这些量子逻辑门 已经有诸多相关研究，且大部分文献的作者都带有物理、数学、逻辑或计算机科 学理论的研究背景。要使用可逆逻辑门，需要设计可逆电路，即需要进行可逆逻 辑电路的综合。近年来，随着对量子计算研究的不断深入，以及量子可逆逻辑在 诸多现代科学领域的重要应用，许多国家对量子可逆逻辑综合也逐渐重视起来。 美国、德国、加拿大、荷兰、韩国等国家的一些组织和个人，对该研究予以高度 重视。量子可逆逻辑的研究涉及到数学、物理学、信息科学等基础学科，并在一 些现代科学如集成电路技术、光电技术、纳米技术和热力学等领域中也有着重要 应用。量子门的逻辑综合，是随着近些年量子信息技术和集成电路技术发展的需 求才被真正给予重视，量子电路可逆逻辑综合方面的研究尚处于很不完善的发展 阶段。 1 2 研究现状 量子电路可逆逻辑综合，主要研究在给定的量子门和量子电路的约束条件及 限制下，使量子可逆逻辑电路的代价最小；研究接近最优化量子代价或为非最优 量子代价提速的量子电路可逆逻辑综合理论和方法；研究接近最优化的可逆逻辑 电路生成方法。量子电路可逆逻辑综合包含合成和优化两个方面，量子可逆电路 的合成是指，通过给定一个可逆逻辑函数的输入、输出值，计算机能够通过先观 的算法得到实现该函数功能的可逆逻辑电路。然而，各种合成法得到的量子可逆 逻辑电路往往不是电路代价最小的最优电路，一般意义上，量子可逆电路的代价 是指量子电路中逻辑门的数量。为了得到最优电路，相应的，出现了量子可逆逻 辑电路的优化技术，其思想是能够在不改变可逆电路函数功能的条件下，对电路 进行重组、替换，达到减少电路逻辑门数量的目的，从而降低了量子可逆电路的 代价。现在也有些方法，将合成与优化这两个过程同时进行，而且已成为综合方 法的主流。 一个1 1 位输入、1 1 位输出且包含k 个量子可逆逻辑门的量子电路称为长度为k 的n x n 规模的量子电路。量子电路的合成不同于使用不可逆门的经典电路合成方 法，一些经典电路特有的概念在量子电路中通常不出现。首先，量子电路不允许 出现回路，即从电路的一部分到另一部分的反馈，也就是说量子电路是无环路的。 其次经典电路允许连线汇合，即所谓的扇入操作，此为不可逆操作，因此在量子 电路中不允许出现扇入。同样，对于扇出，即产生一比特的多个拷贝在量子电路 也是不允许的，事实上量子力学禁止量子比特的复制，扇出操作是不可能的。因 此，在量子电路中只有采用量子可逆逻辑门级联的合成方式。 常用的量子逻辑门有t o 娲l i 门n 儿矧和f r e d k i n i - 副。目前大部分的合成方法采 用t o 肺1 i 门合成量子电路，有以下一些方法： 穷举法心3 制，其思想是对于给定的函数功能以及可供选择的门类型，按照电 路长度的增加，依次生成所有可能电路，直至找到实现函数功能的电路为止。由 于穷举法是根据电路长度从小到大寻找电路的，所以它得到的电路必定是代价最 小的电路，也就是最优电路，但是同时也是最耗时间的方法。 探索法，类似于穷举法，它根据给定的函数功能，带有目的性的选择逻辑门， 2 不断试探性的生成电路，直至找到实现该函数功能的电路。这类方法的特点是通 过相应的参数变化决定选择何种逻辑门进行电路合成，如通过测量汉明距离、二 进制共享决策图等。实际上它是穷举法的改进，通过一些约束条件缩小了电路的 穷举范围，减少了搜索次数。 基于真值表的变化法n 钔幢羽，根据给定的输入、输出值，通过电路的变化规则， 选择相应的逻辑门，逐步将输出值变化为输入值，直至输出值和输入值一致为止。 基于p p r m ( p o s i t i v e - p o l a r i t yr e e d m u l l e r ) n 2 】【2 朝表达式的变化法，它是将函数 的输出、输入值转换为p p r m 表达式关系，再通过因式分解的方法将输出的p p r m 表达式转化为输入的p p r m 表达式，完成电路的合成。 此外还有一些具有某些限制的合成法，这类方法并不是具有实际意义的电路 合成法，它只能应用于某些特殊条件下的电路合成。例如用t o f f o l i 逻辑门执行一 个异或的乘积和操作的方法，它要求生成的电路中至少有一个输入是常量，并且 没有垃圾输出。 通过各种合成方法合成电路，除了穷举法得到的必定是最优电路，其它方法 往往得到的不是最优电路，这使得电路优化技术成为另一个研究重点。量子可逆 电路的优化目标是保持电路函数功能不变，尽可能地减少电路的代价( 逻辑门数 量) 。目前的优化技术主要以模板技术为主。 模板是一个实现恒等函数功能的电路。模板优化技术实质上是两个等价电路 间的替换。模板优化技术的核心思想是：在待优化电路中，找到一个同模板部分 门序列一致的门序列，若这个门序列的长度大于模板长度的一半，则可以用模板 的剩余门序列替换当前电路中的这部分门序列，从而减少电路逻辑门数量，达到 电路优化的目标。 1 3 研究目标与内容 目前，虽然量子可逆电路的合成和优化研究取得了一定的成果，但是相关的 电路合成方法和优化技术还存在一定缺陷，而且大部分研究停留在3 阶电路的综 合上，还有很大研究空间。 本实验室量子小组的研究目标是完善现有方法，探索新的方法，使电路综合 向着解决更高阶问题，综合更有效率的方向发展。本人的任务是通过对现有方法 的研究，探索电路综合规律，寻找新的综合方法。 本文主要阐述了现有的综合方法原理和优缺点，提出了一种新的将遗传算法 应用于量子可逆逻辑电路综合的方法，并对起性能作了实验分析。全文分为六章。 第一章主要介绍研究背景和研究任务；第二章介绍量子信息与量子电路的基本内 容；第三章介绍了几类现有综合方法和优缺点；第四章介绍了遗传算法原理和其 应用于量子电路综合的方法；第五章介绍了通过实验对新方法的性能分析；第六 章为全文总结，并对以后的工作做出展望。 2 1 量子信息 第二章量子信息与量子电路 量子逻辑与经典逻辑最大的区别在于“信息”本身概念上的不同。在经典 信息理论中，信息量的基本单位是比特( b i t ) ，信息以比特形式存储，物理上是 电压信号，数学上是布尔值。一个比特给出经典二值系统一个取值的信息量， 这个信息是确定并且具有决定论意义的。然而在量子信息理论中，量子信息的 基本单位是量子比特( q u b i t ) ，信息以量子态的形式存在。就目前的研究来说， 虽然一个量子比特也是指一个双态系统，但是不同于经典比特的二值系统，这 里的“双态 是指两个可区分的线性独立的态，具体的微观实体可以是半自旋 粒子系统( 如电子) 不同的自旋态，也可以是光子的水平或竖直不同的极化态。 对于半自旋粒子系统( 如电子) ，这两个独立态常记为1 个) 和lj ，) ( 以1 个) 表示自 旋向上态，i 山) 表示自旋向下态) ；对于光子系统，这两个独立态常记为i h ) 和l $ ) ( 以l h ) 表示水平极化态，以f $ ) 表示竖直极化态) ；然而事实上，当从这些具 体的物理实体中抽象到布尔逻辑计算领域后，研究人员使用i o ) 和1 1 ) 来一般性 地表示这样两个独立态。以这两个独立态为基矢，张起一个二维复矢量空间， 所以也可以说一个q u b i t 就是一个二维h i l b e r t 空间。 在量子信息学中，用作量子位物理实现的一个重要双态系统就是光子系统。 在量子力学中，光场或者一般电磁辐射场是由一个一个光子组成的。光子的能 量e 和动量卢通过p l a n c k 常数h 分别与光场的圆频率国、波矢k 联系着： e = h c o( 2 - 1 ) 一一 p = h k( 2 - 2 ) 光子的静止质量为零，运动速度为光速c ，光子沿波矢方向有自旋角动量h 。 对应着经典电磁波的左旋圆极化波和右旋圆极化波，存在有左旋圆极化和右旋 圆极化两种光子态，假如分别用1 0 ) 和1 1 ) 表示，前者沿波矢方向自旋角动量投 影为+ 壳，后者为一壳。光子可以处在1 0 ) 和1 1 ) 的叠加态： 1 1 x ) = ( 1 1 ) 一1 0 ) ) ( 2 3 ) f f y ) = 去( 1 1 ) + 1 0 ) ) ( 2 4 ) 二 这两个式子分别表示光子沿x 方向和y 方向的两种线极化态，这里假设光 子沿z 方向传播。 一个量子比特可以处于它的两个独立态的线性叠加态上，用l y ) 来表示这个 叠加态。一个量子位的纯态可以用两个实参数表征： 4 i y ) = a 1 0 ) + 6 f 1 ) ( 2 5 ) 其中a 和b 是两个复数，包含四个实参数，但是由于其模要满足归一化条 件k 1 2 + b 1 2 ：1 ，其总位相是没有可观测物理效应的，可以略去，再用一个实参 数表示它们的相对位相就够了。若a = l ，b = 0 或a = 0 ，b = l ，叠加态i y ) 蜕化为i o ) 或 1 1 ) 。对于态1 0 ) 或f 1 ) ，当执行一个投影到基 o ) ，f 1 ) 上的测量时，其中任何一个 或者以概率1 出现，或者根本不出现。测量也不会改变这个态，换而言之，这 些态表现出和经典态相似的性质。由于这个原因，有时称它们为经典态。但当 量子位处在一般性的i y ) = 口 o ) + b1 ) 描述态时，执行投影到基 o ) ， 1 ) 上的测量， 将以概率h 2 得到态1 0 ) ，以概率衅得到1 1 ) ，且测量结果将扰动这个态，测量之 后l y ) 被制备在一个新态上。如果没有态l y ) 制备的知识，凭一次测量不能定出 其中的a 和b ，从而不可能完全确定这个态。 量子比特能够以叠加态的形式存在，这个特点使得量子比特在其所能够表 达的信息量的数量上大大优于经典比特。在经典信息系统中，n 个比特只能够 代表2 ”个不同的状态；而在量子信息系统中，n 个量子比特能够代表的不同的 状态的数量与这2 ”个态所能叠加出的态的数目是一致的。 对于有两个量子位的量子比特对，它有4 个互相正交的态，它的布尔基底 态可以表示为：o o ) ，1 0 1 ) ，1 1 0 ) ，1 1 1 ) 。当然这两个量子比特也可以处在其4 个基 底态任何可能的线性叠加态上，它的一般态可以表示为： i 杪) _ a 1 0 0 ) + b 1 0 1 ) - t - c 1 1 0 ) + d 1 1 1 ) ( 2 6 ) 在这里，值得注意的是这两个量子比特之间的关系，它们是相互纠缠 ( e n t a n g l e m e n t ) 在一起的，或者称它们处于量子纠缠态上。在数学上，研究人员 使用张量积( 即k r o n e c k e r 积) 来描述它们的这个特点。作为一个例子，请考 虑一对量子比特，假设它们分别处于y 。= a l i o ) + b 。1 1 ) 和y ：= a2 i o ) + b ：1 1 ) 态上。 当把这两个量子比特表示为一个态时，y ，态是其基本量子比特所有可能的组合 的线性叠加态，即： y 】2 = 少】 y 2 = ( 口，i o ) + b 。| 1 ) ) o ( 口：i o ) + b ：1 1 ) ) - a 。口：j o o ) + 口，b ：j 0 1 ) + 口2 b 。i l o ) + b 。b ：1 1 1 ) ( 2 7 ) 其中符号。代表张量相乘。 一般地，n 个q u b i t 的态张起一个2 ”维h i l b e r t 空间，存在2 ”个相互正交的 态。通常取2 “个基底态为f f ) ，i 是一个n 位二迸制数。1 1 个量子位的一般态可以 表示成这2 ”个基底态的线性叠加： 2 “一1 i5 c ， - - - g i f ) ( 2 8 ) 其中g 是叠加系数。 量子力学通过张量积把2 4 个单独的状态向量相互结合起来，张量运算使得 量子比特状态背后蕴涵大规模并行计算的方法，因为叠加态渺) 同时存储了2 “ 个二进制数，其中每个c f 都是复数且满足 副2 = ， ( 2 - 9 ) 2 2 量子计算与量子逻辑门 经典计算机用电子电路作计算。电子电路是由线性元件( 如导线、电阻和电 容器) 和非线性元件( 如二极管和三极管) 构造而成。线性元件独立地改变输入信 号，而非线性元件则使经过它的输入信号发生相互作用。电路通过以极高的速 度反复完成若干简单的线性和非线性任务来进行计算。使信息位发生翻转，是 “非 ( n o t ) 的逻辑操作：即1 变为0 或0 变为1 。另一个操作是“复制”( c o p y ) ， 也就是使第二个数据位的值与第一个相同，这两个操作被称为线性操作。对两 个数据位作“与”( a n d ) 运算，则是非线性的逻辑操作：如果两个输入位均为1 ， 则使第三位也等于l ，其它任何一种情况均使第三位等于0 。在这种情况下，输 出取决于输入之间的某种相互作用。执行这些操作的器件称为逻辑门。如果一 台数字计算机有线性逻辑门，如n o t 门和c o p y 门，也有非线性逻辑门，如a n d 门，则它可以完成任何一种逻辑或算术任务。量子计算是通过量子逻辑门来实 现的，量子逻辑门是量子计算机的最基本的构造单元之一。它有两种相互作用 的量子位：控制位和目标位，控制位保持不变，但它的状态决定目标位的演化。 如果控制位是0 ，则目标位不发生任何改变，如果控制位是1 ，则目标位将经历 一个确定的变换。量子逻辑门与经典逻辑门具有本质上的不同，经典逻辑门输 入态和输出态中的每一位都是经典信息( 0 或1 ) ，不能输入叠加态，其变换形式 为0 1 。一般情况下经典逻辑门的操作是不可逆过程，而量子逻辑门的输入态和 输出态是量子信息( 量子位0 或1 ) ，并且输入态和输出分态可以是量子位的叠加 态n 1 。如果控制位是0 和l 的叠加态，量子逻辑门的输出则是缠绕的态，也就是 说，在个非分离的态中，两个量子位相关性很强。输入态的叠加和输出态的 缠绕是量子逻辑门区别经典逻辑门的基本特征。这一基本特征说明量子计算为 计算容量提供了更广阔前景。量子逻辑门作用于输入量用一个么正算符u 来描 述，由于u 存在逆矩阵，所以量子逻辑门能进行可逆运算。 在量子逻辑电路中，对量子位进行幺正操作的基本元件称为量子逻辑门 ( q u a n t u ml o g i cg a t e ) ，量子信息经过各个量子逻辑门时，依据门功能发生变换。 从数学的观点，量子逻辑f - 1 x 寸量子信息的操作可以用一个幺正矩阵m 来表示， 幺正变换的一个重要特点就是这些变换都是可逆的，即每个量子逻辑门也是可 6 逆的。若干个量子逻辑门的排列，组成了一个可逆逻辑电路，这个电路实现了 某个可逆逻辑函数功能。量子逻辑门通过幺正变换实现了一个可逆函数，这就 是利用量子力学构建可逆逻辑电路的实验基础。量子逻辑门不带有信息的擦除 操作( 输入信息的丢失) ，在理论上也就不存在热耗散的极限，从而杜绝了经典 计算机从根本上无法解决的热耗散严重影响器件正常功能的问题。d e u t s c h 最早 考虑了用量子逻辑门来构造计算机的问题，他发现几乎所有的三比特量子逻辑 门都是通用逻辑门。所谓通用逻辑门是指，通过该逻辑门的级联，能够以任意 精度逼近任何一个幺正操作。后来，有一些研究人员发展了d e u t s c h 的结论， 最终d c u t s c h 和l l o y d 各自独立地证明了几乎所有的二比特量子逻辑门都是通 用的，这里“几乎 是说，二比特通用量子逻辑门的集合是所有二比特逻辑门 集合的一个稠密子集。 量子逻辑门按照它作用的量子位的数目可分为一位门、二位门和三位门。 b a r e n c o 等人证明，一个二比特的异或门与对一比特进行任意操作的量子门可构 成一个通用量子逻辑门集合。所有的三位以上的量子逻辑门都可由一位和两位 逻辑门组合起来实现其功能。因此，量子逻辑门在物理上实现的关键是基本的一 位和二位量子门的实现。相对来说，一位逻辑门在实验上比较容易实现，现在 的不少实验方案都集中于制造量子异或门。量子异或门和经典异或门非常类似， 有2 个输入比特：控制比特和受控比特。当控制比特处于微观粒子上能级( 激 发态) 时，受控比特态发生反转。用c 1 2 表示量子异或操作，其中1 、2 分别代 表控制和受控比特，则有 i ，2 1 ) l 托2 ) 1 三 i ，z 1 ) i ，z l o ，z 2 ) ( 2 1 0 ) ，-， 式中，n l 、1 2 取值0 或1 ，0 表示模相加。 其它量子逻辑门的操作都可以像这样用其对量子位的h i l b e r t 空间基矢的作 用定义。如果一个幺正操作演化基矢态为： 0 ) - - + 1 0 1 ) ，7h 。， ( 2 - 1 1 ) 1 ) 一e i e o t l l ) 这个幺正操作就是一个位r 。记基矢l o ) = ( ，1 1 ) = ( o ) ，这个门操作就 可以用个幺正矩阵 特( ( 2 - 1 2 ) 表示，其中0 = c o t 。容易验证p p ) i o ) = i o ) ，p ( o ) i i = e 够1 1 ) ，所以这个门操作 还可以用投影算子形式表示为 尸( p ) = l o 和ll 的相对位相万。 定义y 操作为y = z x ，注意到 及= ( 三瑞鞘州 所以y 操作可以用矩阵表示为： y = z ( ；苫) = z 仃， 8 ) ) ) ) 8 9 o 1 1 1 2 2 一 一 一 一 2 2 2 2 ( ( ( ( 其中盯y 是p a u l i 矩阵n 1 。 另一个重要的位门是h a d a m a r d 门，它的作用可表示为 h = 焉1 0 0 ) + 1 1 ) x o o ) 一1 ) x 1 ( 2 2 2 ) 二 t to ) = 去0 0 ) + 1 1 ) ) v 砷) = 万1 。) 一1 1 ) ) ( 2 - 2 3 ) 片j 矩阵表不为： 日= 拭廿击伍+ z ) 2 4 ， 这正是从仃：表象到o x 表象的基矢变换矩阵。 ( 2 ) 两位门 作用到两个量子位上的所有可能的幺正操作中一个最有意义的子集是 i o ) ( o l 圆，+ 1 1 ) ( 1 l u ( 2 2 5 ) 其中，i 是一个量子位的恒等操作，u 是另外一个一位门。这样的两位门称 为控制uf - j ( c o n t r o lu g a t e ) ，第一量子位称为控制位，第二量子位称为受控位 ( 或者靶位) 。控制u 门对靶位作用i 或者u ，决定于控制位处于l o ) 态还是f 1 ) 态。 例如控制非门的作用是 1 0 0 ) j1 0 0 ) 1 0 1 ) 寸1 0 1 ) f 1 0 ) j | 1 1 ) 1 1 1 ) j 1 0 ) ( 2 - 2 6 ) 当且仅当第一量子位处于1 1 ) 态时，才取第二量子位的逻辑非。 控制非门可以用图2 - 1 表示，其中a 、b 表示0 或1 ，口0b 表示模相加， 即0 + 0 = 0 ，1 + 0 - - 0 + 1 = 1 ，1 + 1 = 0 。 ，一 图2 - 1 控制非门 9 毫ob 两量子位的态矢空间的基底可以由一个量子位基矢直积构造 o o ) = ，l0 1 ) = ki ，1 1 0 ) = l vi ，1 11 ) = 在这组基下，控制非门的作用可以用矩阵表示为： r= 、- n o t 10 01 0 o 0 o o 0 o o o1 10 ( 2 - 2 7 ) ( 2 2 8 ) 另一种重要的两位门是s w a p 门，它用于实现两个量子位上量子信息的交 换，即： 用矩阵表示就是： s = 10 0 0 o1 0 o 0o 10 0 o o1 ( 2 - 2 9 ) ( 2 3 0 ) ( 3 ) 三位门 三位量子门中重要的一个就是3 位控制一控制u 门n 3 ，即当且仅当第l 、第 2 位都处在态 l 时，才对第三量子位执行u 变换。它的线路图如图2 - 2 所示。 ，。、 图2 2 控审0 一控俸0u 门 、 图2 3t o f f o l i 门 1 0 a b c o 曲 嘞吣吣岭吣埘吣吣 叫叫叫叫 吣d吣岭唧吣哪m 特别取u 为逻辑非，就得到了图2 - 3 所示的经典的t o f f o l i 门。t o f f o l i 证明了t o f f o l i 门对经典计算是通用的。t o f f o l i 门的作用是： 这个门的矩阵【1 1 表示是： t = 0 0 0 ) 寸1 0 0 0 ) 0 0 1 ) 一1 0 0 1 ) 0 1 0 ) 寸1 0 1 0 ) ， 0 1 1 ) _ 1 0 1 1 ) ， 1 0 0 )1 0 0 ) 1 0 1 ) - - - 1 1 0 1 ) 1 1 0 ) 一f 1 1 1 ) 1 11 ) 一1 11 0 ) f i o o o ) - - 争1 0 0 0 ) 0 1 0 ) 专1 0 1 0 ) i1 0 0 ) 专1 1 0 0 ) 【i l l o ) 寸f l l l ) ( 2 - 3 1 ) ( 2 - 3 2 ) ( 2 - 3 3 ) 这个门输出的第三位是前两位a n d 给出实现a n d 操作的另一种形式。 另一种重要的三位门是f r e d k i n 门，它的第一位是控制位，第二位和第三位 是工作比特位。f r e d k i n 门的作用是，当其控制位为1 1 ) 时，它的工作比特位上的 量子信息发生交换；当其控制位为1 0 ) 时，f r e d k i n 门不发生作用，即： 0 o o o o o 1 o o o 0 0 o 0 o 1 o 0 o o 0 1 o o 0 o 0 o l o o 0 o 0 o 1 0 0 o o o 0 1 o 0 o 0 0 0 1 0 0 o 0 o o 1 0 0 o o 0 o o f r e d k i n 门的矩阵表示是： 0 0 0 ) 一f 0 0 0 ) 0 0 1 ) - - 专t 0 0 1 ) 0 1 0 ) _ 1 0 1 0 ) 0 1 1 ) 一1 0 1 1 ) 1 0 0 ) 一1 1 0 0 ) 1 0 1 ) 一f 1 1 0 ) 1 1 0 ) _ 1 1 0 1 ) 1 1 1 ) 一1 1 1 1 ) 同样，当初始第3 位制备在l o ) 态时， 0 0 0 寸 ， 0 1 0 _ ， 1 0 0 ) - 9 , i ， 110 ) _ i 则有 0 0 0 ) 0 1 0 ) 1 0 0 ) 1 0 1 ) ( 2 - 3 4 ) ( 2 3 5 ) ( 2 3 6 ) 这个门输出的第三位是前两位a n d 给出实现a n d 操作的又一种形式。 也可以把初始第2 位制备在1 1 ) 态时，则有 0 1 0 ) _ l0 1 0 ) ， o l1 ) _ f 0 11 ) 1 1 0 ) 寸1 1 0 1 ) 1 11 ) 一1 11 1 ) ( 2 - 3 7 ) 这个门输出的第三位是第一位和第三位o r 的结果，这就给出实现0 r 操作 的一种形式。 从上文中可以看到，其实任何经典运算都可在量子门上实现。只要对经典 门稍加改造，则经典门也变成可逆的了，所有不可逆经典计算机都可改造为可逆 机。因为量子态的演化是可逆的，量子计算机必是可逆机，量子门能执行一切 1 2 o 0 o 0 o o 0 1 o o o o o 1 o o 0 o o o o 0 1 0 o o 0 0 1 0 o 0 o o o 1 0 o o o 0 0 1 o 0 0 o o o 1 o o 0 o o o 1 0 o o o 0 o 0 经典操作： ( 1 ) “非 运算：可直接在单量子位x 门上实现。 ( 2 ) “异或”运算：可在双量子位“可控非”门上实现。 ( 3 ) “与 运算：可在三量子位门- t o m i 门上实现。量子t o m i 门前两位 是控制位，第三位是目标位。 ( 4 ) “或 运算：可在三量子位1 7 - - f r e a k i n 门上实现。量子f r e d k i n 门第一 位是控制位，后两位是目标位。 当然，除此而外，量子门还能执行特有的量子运算。 2 3 量子电路 量子电路是由若干量子逻辑门级联构成，它是对量子信息作一系列幺正变 换以实现电路功能。量子可逆逻辑电路具有以下特点：输入线数与输出线数 相等；没有扇出与扇入；没有反馈；电路分层级联，有时为保证电路可逆 性需要人为添加一些辅助位，即没有用的数据位。一个1 1 位输入、l q 位输出的量 子电路，称为n x n 规模的量子电路。图2 - 4 为一个实验用例的电路图，其功能 函数可表示为f ( 0 ，1 ，2 ，3 ，4 ，5 ，6 ，7 ) = ( 2 ，6 ，o ，1 ，7 ，3 ，5 ，4 ) ，其真值表如表2 1 。 l23 ， 一r 、 l f 图2 - 43 3 可逆逻辑电路示例 表2 - 1 图2 4 电路真值表 a o b o e o 输 入 输 出 ( cba ) 2cba ( c 0b oa o ) 2 c 0b oa 0 00o02o10 10o16110 201o00o0 301110ol 4l0 0711l 51013011 61105l01 7ll14 100 可逆电路的量子代价是指它所有量子门的量子代价的总和，而量子门的量子 代价是指这个门为了实现其可逆函数功能所需要完成的基本的量子操作的量子 代价的总和。不同量子门的量子代价不同。