（计算机软件与理论专业论文）基于真值表变换和规则优化的可逆逻辑综合算法研究.pdf

r e s e a r c ho na l g o r i t hmo fr e v e r s ib l el o gi c s y n t h e s i sb a s e do nt r a n s f o r m a t i o no ft r u t h t a b l ea n dr u l e sb a s e do p t i m i z a t i o n at h e s i ss u b m i t t e dt o s o u t h e a s tu n i v e r s i t y f o rt h ea c a d e m i cd e g r e eo fm a s t e ro fe n g i n e e r i n g b y a j lb o s u p e r v i s e db y p r o f e s s o rc h e nh a n w u s c h o o lo fc o m p u t e rs c i e n c ea n de n g i n e e r i n g s o u t h e a s tu n i v e r s i t y d e c e m b e r2 0 0 9 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：泣逮 e t 期：坐1 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 摘要 摘要 量子可逆逻辑电路的研究对于量子计算与量子信息的发展具有重要的意义，可逆性使得 量子可逆逻辑电路不仅能够应用在量子计算，而且可以应用于低功耗c m o s 、纳米技术以及 光计算等领域。可逆逻辑电路实现一个双射的可逆函数功能。量子可逆逻辑电路综合，是研 究在给定的量子门和量子电路的约束条件及限制下，找到实现所需逻辑功能的电路，且该电 路具有最小或较小的量子代价。为寻找效率更高的量子可逆逻辑电路综合算法，本文对当前 主要的综合方法和优化策略进行了研究和总结。 为实现将给定的可逆函数快速综合为相应电路，并保持其结果的最优或较优，本文提出 了一种基于真值表变换的快速综合算法。由于可逆函数与置换同构，任意置换均可表示为若 干对换的乘积，通过将可逆函数转化为一系列对换的乘积，而每个对换对应着一个门序列， 最终从对换的乘积中综合电路。 对于3 量子可逆逻辑电路，只有2 8 种对换，事先将每种对换对应的最优电路存入库中， 以生成3 量子电路综合的一个基，然后通过在该库中查找，快速生成可逆电路。对于4 量子 或n 量子( n 4 ) 的可逆电路，将待综合的可逆逻辑函数转化为对换序列，借助邻接矩阵和 广义t o f f o l i 门，再将生成的对换序列转化为相应的电路。同时，根据量子逻辑门的抵消、交 换、约化等规则，本文引入规则优化方法，最终完成快速综合算法。 以综合所有3 量子电路和综合特定4 量子电路，分别验证算法的效率。与已有的真值表 综合方法相比，效率提升了4 7 倍；与r e e d m u l l e r 方法及类模板优化法相比，效率提升了1 0 4 倍；与穷举法效率相当，但穷举法只适用于3 量子电路综合。 实验结果表明，本文的方法不但可以提高可逆逻辑综合的效率，而且结构简单，易于实 现，可以以较高的时间效率快速综合任意n 比特可逆逻辑电路，综合结果均达到或接近最优。 关键词： 可逆逻辑综合，真值表，对换，规则优化，邻接矩阵，广义t o f f o l i 门 a b s t r a c t a b s t r a c t t h er e s e a r c ho nq 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 si si m p o r t a n tt ot h ed e v e l o p m e n to fq u a n t u m c o m p u t i n ga n dq u a n t u mi n f o r m a t i o n b e c a u s eo ft h er e v e r s i b i l i t y , q u a n t u mr e v e r s i b l ec i r c u i t sc a n n o to n l yb ea p p l i e dt oq u a n t u mc o m p u t i n g , b u ta l s ot ol o wp o w e r c m o s ，n a n o t e c h n o l o g y , o p t i c a l c o m p u t i n ge t c r e v e r s i b l el o g i cc i r c u i t sr e a l i z eab i - j e c t i v er e v e r s i b l ef u n c t i o n t h es 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 ss t u d i e so nf i n d i n gac i r c u i tc o r r e s p o n d i n gt ot h eg i v e nf u n c t i o n w i t hl o w e s to rl o w e rc o s t ，u n d e rt h ec o n s t r a i n tc o n d i t i o n t of i n dt h ef a s t e ro rm o r ee f f e c t i v e s y n t h e s i sm e t h o d ，m a i ns y n t h e s i sa l g o r i t h m sa n do p t i m i z a t i o ns t r a t e g i e sa tp r e s e n th a v eb e e n s t u d i e da n ds u m m a r i z e d t or e a l i z et h es y n t h e s i so fac e r t a i nr e v e r s i b l ef u n c t i o nr a p i d l y , a n de n s u r et h er e s u l to p t i m a lo r b e t t e r , a na l g o r i t h mb a s e do nt h et r a n s f o r m a t i o no ft h et r u t ht a b l ei sp r o p o s e d ；ar e v e r s i b l ef u n c t i o n i si s o m o r p h i ct oap e r m u t a t i o n ；a na r b i t r a r yp e r m u t a t i o nc a nb ee x p r e s s e da sa p r o d u c to fa s e r i e so f s w a p p i n g ，w h i c hc a ng e n e r a t et h ec i r c u i t s f o rt h e3 - q u b i tc i r c u i t s ，t h e r ea r eo n l y2 8k i n d so fs w a p p i n ge x i s tt o t a l l yw h o s ec o r r e s p o n d i n g c i r c u i tb l o c k sa r es t o r e di n t oal i b r a r yi na d v a n c ea st h eb a s i so f3 - q u b i tc i r c u i t s r e v e r s i b l el o g i c c i r c u i t sw i l lb es y n t h e s i z e db ys e a r c h i n gi nt h el i b r a r y f o rt h e4 - q u b i to rm o r eq u b i t ss i t u a t i o n ，a s e q u e n c eo fs w a p p i n gw o u l db et u r n e dt oc o r r e s p o n d i n gc i r c u i t sd i r e c t l yt h r o u g hu s i n ga d j a c e n t m a t r i xa n dg e n e r a lt o f f o l ig a t e m e a n w h i l e ，t h er u l e sb a s e do p t i m i z i n gm e t h o di sa d d e dt of i n i s h t h e r a p i ds y n t h e s i sa l g o r i t h m ，a c c o r d i n g t ot h e p r o p e r t i e s o fl o g i c g a t e s a s c a n c e l l a t i o n ， c o m m u t a t i v ea n dr e d u c t i o n t h ee f f i c i e n c yo fa l g o r i t h m si sc h e c k e dt h r o u g ns y s t h e s i s i n ga l l 3 - q u b i ta n ds o m e4 - q u b i t c i r c u i t s c o m p a r i n gw i t he x i s t e da l g o r i t h mb a s e do nt r u t h t a b l e ，t h ee f f i c i e n c yi se n h a n c e db y4 7 t i m e s ；c o m p a r i n gw i t hr e e d m u l l e ra l g o r i t h ma n dt e m p l a t eo p t i m i z a t i o n ，t h ee f f i c i e n c yi s e n h a n c e db y1 0 4t i m e s ；t h ee f f i c i e n c yi sc l o s et om e t h o do fe x h a u s t i o n ，w h i c hc a nb eo n l yu s e df o r 3 - q u b i tc i r c u i t s t h er e s u l t so fe x p e r i m e n t ss h o wt h a tt h i sa l g o r i t h mc a ni m p r o v et h ee f f i c i e n c yo fs y n t h e s i z i n g t h er e v e r s i b l el o g i cc i r c u i t s ，w h i c hi se a s yt or e a l i z ea n dw i t hs i m p l es t r u c t u r e i tc a ns y n t h e s i z e a r b i t r a r yn q u b i tr e v e r s i b l el o g i cc i r c u i t sr a p i d l yw i t hh i g ht i m ec o m p l e x i t y , w h i c hc a na l s om a k e t h er e s u l ta c h i e v i n go rg e t t i n gc l o s e rt ot h eo p t i m a l k e yw o r d s ： r e v e r s i b l el o g i cs y n t h e s i s ，t r u t ht a b l e ，s w a p p i n g ，r u l e sb a s e do p t i m i z i n g ， a d j a c e n tm a t r i x ，g e n e r a lt o f f o l ig a t e n 1 2 1 可逆逻辑电路的综合2 1 2 2 可逆逻辑电路的优化3 1 3 论文组织3 第二章量子计算与可逆逻辑电路4 2 1 量子计算基础4 2 1 1 量子比特4 2 1 2 量子比特的存储5 2 1 3 相二1 ：1 生! ； 2 2 量子逻辑门5 2 2 1 量子逻辑6 2 2 2 受控门：7 一一 2 2 3 通用量子门8 2 2 4 广义t o 白l i 门9 2 3 可逆逻辑线路9 2 3 1 可逆逻辑电路9 2 3 2 可逆逻辑线路的代价1 0 2 4 可逆逻辑线路综合。1 0 2 4 1 可逆逻辑电路的综合规模。1 l 一。 2 4 2 可逆逻辑电路的等价表示。1 1 2 5 量子电路的物理实现1 2 第三章量子可逆电路综合算法1 4 3 1 穷举法1 4 3 2 真值表法1 5 3 3r e e d m u l l e r 方法1 7 3 3 1 经典p p r m 算法1 7 3 3 2 启发式算法1 9 3 4 群论方法1 9 3 5 多值逻辑综合2 0 3 6 ，j 、结2 1 第四章基于变换合成与规则优化的综合算法2 2 4 1 基于真值表变换的三量子电路综合算法2 2 4 1 1 概j 述。2 2 4 1 2 基于3 量子最优电路的真值表变换方法。2 2 4 1 33 量子可逆电路规则优化算法2 4 4 1 4 算法举例2 6 4 1 5 算法分析2 7 l n ， 日录 4 2 基丁二广义t o f f o l i 门的通刚算法2 7 4 2 1 概述一2 8 4 2 2 基于真值表变换的通用算法2 8 4 2 3 算法举例2 8 4 2 4 算法分析2 9 4 3 广义t o 肋l i 门电路优化2 9 4 3 1 优化算法2 9 4 3 2 优化举例3 1 第五章实验结果与分析3 2 5 1 评估基准3 2 5 2 评估方法与实验方案设计3 2 5 3 实验结果与分析3 2 第六章结束语3 4 6 1 1 ：作总结3 4 6 2 展望3 4 j 致谢3 6 参考文献3 7 附录攻读硕士学位期间完成的论文列表一4 0 i v 第一章绪论 1 1 研究背景 第一章绪论 从1 9 5 8 年世界上第一块集成电路诞生至今，世界集成电路技术与产业一直在飞速发展。这一发展过程 一直依照著名的摩尔定律一每隔1 8 个月单位体积上的品体管数量将翻芥。随着集成度的提高和电路规模 的增人，电路中单元器件尺寸不断缩小。现在，晶体管的尺寸已经进入纳米级时代，最新一l ：艺已达剑4 5 纳 米。然而，c m o s 技术的极限是2 0 纳米，一旦低丁该界限，c m o s 晶体管将不会按照当初设计时所预计的 方式f ：作，它的功能开始受到量子效应的干扰电路中的电子将遵循量子力学原理表现为波，干涉和叠 加效应将成为主导。寻找摩尔定律最终火效问题的解决方案，催生了一j 全新的学科量子信息科学。 量子信息科学并不试图超越摩尔定律，而是一种全新的信息处理方式的尝试。量子计算是基于量子力学而 ：| f 经典物理学理论进行计算较之经典的数字计算机，量子计算机在计算能力、存储能力、和现实世界的 仿真能力上将有更加出色的表现【1 11 2 j 。 在1 9 世纪7 0 年代至8 0 年代，由c h b e n n e r ，ea b e n i o f f ，d a v i dd e u t s c h 和r ef e y n m a n 等物理学家和 计算机科学家，首次提出了基于量子动力学的计算设备的设想。1 9 8 2 年，f e y n m a n 讨论了把量子力学和计算 机结合起来的可能性，并首次引入量子计算机的概念1 3 i 。他指出，量子计算机比经典计算机能更有效地模拟 量子系统，同时他建立了一个能显示如何利用鼙子系统执行计算的抽象模型。紧接着，1 9 8 5 年，d e u t s c h 4 i 声明在一般原则卜，任何物理过程都可以被量子计算机模拟，通过量子电路和通用量子计算机( 量子图灵 机) 的探讨，描述了量子计算机的一般模型，发展了量子计算理论。1 9 9 4 年，s h o r 5 j 发表了一篇影响深远的 论文，陈述了一个使用量子计算机解决一个重要的数字理论问题的方法，提出了基于量子傅立叶变换的人 数冈子分解算法一即s h o r 算法。该算法引出了计算机科学中的人数冈子分解的核心问题。s h o r 算法极人地 挑战了r s a 公共密钥系统。1 9 9 4 年，人们刚了1 6 0 0 台计算机，耗时8 个月，分解了长度为1 2 9 位的数。按照 这个速度分解1 0 0 0 位的数，需要1 0 2 5 年；而利刚s h o r 算法，则只需要几分之一秒。这一突破使得对量子计算 机的兴趣不再只局限于学术界，而是引起了全世界各领域人士的广泛关注，进入了研究高潮。 而可逆计算是量子计算机的核心，研究可逆计算涉及到计算机的能耗问题。早在上t h = 纪六十年代初， 人们就发现，不可逆计算产生的能耗会导致计算机芯片的发热，从而影响芯片的集成度、限制了经典计算 机的运行速度【6 j 。能耗产生于经典计算机计算过程的不可逆操作。冈此，具备可逆计算能力的量子计算机是 解决芯片集成度瓶颈的一种途径，并将成为下一代计算机的首选。 类似于经典逻辑fj 电路构建了经典计算机，量子计算机由量子逻辑门电路构造。量子逻辑门是量子计 算机的基本单元，从数学的观点看，每一个量子逻辑门的操作都可以用一个幺正矩阵算子米表示，该算子 实现信息的幺正变换，幺上e 变换即该变换是可逆的，也就是说，每个量子逻辑门都是可逆的。若干个量子 逻辑门的合成，组成了一个可逆逻辑电路，这个电路将实现了一个可逆逻辑函数功能。所谓可逆逻辑函数， 就是一个n 位输入和n 位输出的双射函数一它的2 “个输入中每一个输入都唯一对应一个输出。可逆逻辑 电路不仅应用在量子计算中，它同样可以应用在低功耗c m o s 、纳米技术以及光计算等领域，因此可逆逻 辑电路正在成为一个新兴的研究领域。 1 2 研究现状 目前，在量子可逆电路的综合以及电路优化方面，已经进行了许多研究，取得了一定的成果。量子可 逆逻辑电路的综合，即量子可逆逻辑电路的自动合成，是指通过给定一个可逆逻辑函数的输入输出值，计 算机能够通过相关的合成算法得到实现该函数功能的可逆逻辑电路，也称作可逆逻辑线路综合或可逆逻辑 综合。然而，各种综合方法得剑的量子可逆电路往往不是电路代价最小的电路，即最优电路。一般意义上， 量子可逆电路的代价【7 i 是通过电路中量子可逆逻辑门的数量来衡量的。为了得到最优电路，出现了量子可逆 电路的优化技术，其思想是能够在不改变可逆电路函数功能的条件下，对电路进行重组，通过子电路模块 1 东南人学硕l 学位论文 的等价替换，达剑减少电路逻辑i 、j 数堵的目的，从而降低了量子可逆电路的代价。以下分别就电路的综合 及优化介绍其研究现状。 1 2 1 可逆逻辑电路的综合 一个1 1 何输入、n 位输出h 包含k 个量子可逆逻辑门的量子电路，称为k 度为k 的n n 规模的量子电 路。量子电路的合成彳i 同丁使_ j 不可逆| 、j 的经典电路合成方法，一些经典电路特有的概念在量子电路中通 常不出现。首先，量子电路不允许出现| 亓l 路，即从电路的一部分到另一部分的反馈，也就是说量子电路是 无环的。其次，经典l u 路允许迮线汇合，即所谓的扇入操作，显然这个操作是不可逆的，闪此在量子电路 中不允许出现扇入。最后相反的操作，扇出，即产生1 比特的多个拷贝在鼙子电路中也是不允许的，事实 上量子力学禁i 卜量子比特的复制，扇山操作是不可能的。因此，只能采j 量子可逆逻辑门级联的方式来综 合量子可逆逻辑电路。 常见的可逆逻辑j 有n 门，c n o t 门，t o f f o l i 门，f r e d k i n 门，p e r e s 门等，大部分综合方法选取含有 一系列特定的fj 的集合米生成电路，目前比较有代表性的综合方法如下： 穷举法【s l 【9 l 【l o 】，其思想是对丁给定的函数功能以及可供选择的门库，按照电路k 度的增加，依次生成所 有可能的电路，直至找剑实现该函数功能的电路为i ：。由于穷举法是根据电路长度从小到人寻找电路的， 所以它得到的电路必定为代价最小的电路，也就是最优电路。但同时也是最耗费时间的方法，目前穷举法 只得到了3 x 3 ( 或称三量子，三变量，三阶) 最优量子电路，由于四量子全部电路数量达1 61 个，超出了现 在计算机的计算和存储能力。文献【s l 【1 1 l 通过穷举法得到了所有3 x 3 的最优电路。 真值表法【1 2 l u 引，是一种贪心算法，它依据给定的函数，不断变换真值表的列值，每一次变换选取相应 的逻辑门，直到真值表的输出列值变换为与输入序列完全相同为i ：。通常有三种做法：前向、后向、和舣 向。此方法构造巧妙，综合电路迅速，而且可适刚于任意比特电路，但综合出的电路通常不是最优的，需 要辅助的优化方法对结果进行再次处理，如模板匹配法1 1 2 j 【1 4 l 【1 5 l 等。 止极性r m 表达式方法( p o s i t i v ep o l a r i t yr e e dm u l l e r ) ，或简称r m 方法【1 6 1 7 1 引。由y - 任何“个布尔 函数都可以表示为一个异或的乘积之和表达式，止极性r m 表达式具有类似的形式。将函数输出端的每一 个变量都可写成r m 表达式，依次取得各输出端表达式，通过冈子代换与消除，直至输出端的表达式同输 入端相同。r m 方法有着与真值表法类似的效率，同样也需要优化算法来化简综合结果。 群论方法【1 9 l 【删，由于可逆函数可以很白然地与置换相关联，借此引入置换群理论，并借助群论的相关 理论结果与特性，把可逆逻辑综合问题完全转化为求解群论问题。群理论的廊j j 使得综合电路获得额外的 效果，比如文献【2 0 j 中综合3 量子的电路最多需要4 步，4 个门。但是算法较为复杂，且构造的门库较大，代 价较高。 其它方法，比如探索法【2 1 】【2 2 】【2 3 1 ，它根据给定的函数功能，带有目的性的选择逻辑门，不断试探性的生 成电路，直至找到实现该函数功能的电路为止。这类方法的特点是通过相应的参数变化决定选择何种逻辑 门进行电路合成，如通过测量汉明距剐2 1 j ，r a d e m a c h e r - w a l s h 谱均数【驯、二进制共享决策图【2 3 j 等。实际上， 这类方法是穷举法的改进，它通过一些约束条件缩小了电路的穷举范围，减少了搜索次数。 另外有一些专用构造方法，根据一些特定功能的可逆逻辑电路的特点，用专用构造算法，快速生成电 路如用b i t o n i c 2 4 j 方法可快速构造大规模的量子排序电路，然而这些算法不具有通用性，但性能较好。例 如构造可逆排序电路，如果用其它方法，则算法复杂性较高，且构造的电路没有规律，很难由此直接构造 更大的排序电路。 多值逻辑可逆电路综合【z 5 j 1 2 6 j 。量子计算中，每个量子位可以表示多种状态，具有多种取值，所以在量 子计算中，使用多值逻辑代替经典计算的二值逻辑成为可能。同时，多值逻辑能够人幅提升计算能力，减 少量子线数目或存储所需的比特数。引入g a l o i s 域，通过求解g f s o p 和构造g f 判定图来构造多值的量子 逻辑电路。 可以看出，穷举法综合结果好，能达到最优，但时间空间开销巨大，实用性不强；真值表法，r m 方法 算法构造巧妙，综合速度快，但结果不尽理想，需要辅以优化；群论方法新颖高效，算法收敛迅速( 有限一 2 第一章绪论 步结求) ，但构造复杂，需要的门库规模较人；多值逻辑综合另辟蹊径，给出了一个崭新的解决方案，但算 法较繁琐；其它方法也均是在综合效果和综合效率之间寻求一个平衡点，这个平衡点如何米选取，则应该 以实战中的具体需求为准。 1 2 2 可逆逻辑电路的优化 除了穷举法之外，几乎所有可逆逻辑的综合方法均不能保证结果的最优性，所以可逆电路的优化有着 广泛的需求。量子可逆电路优化的目标，是在保持该电路功能不变的前提下，尽可能地减少电路的晕子代 价( 代价通常川逻辑fj 的数量米衡量) 。1 w a m a 羽1 ，m i l l e d d l 与m a s l o v 1 2 1 等人在优化方面做了深入的研究。 文献【27 1 总结了c n o tf j 电路的变换规则并给予了证明，此方法优化效果较好，但只针对c n o t | j 电路， 且算法较为复杂，应用的辅助线比较多。文献1 1 3 j u z j 提出了使崩模板来优化电路的方法，事先构造模板库， 通过对电路的一部分进行匹配与替换，达剑减少门数的目的。模板优化技术，实质上是子电路模块问的等 价替换。模极优化技术的核心思想是，在待优化的电路中，找到一个同模板部分门序列相一致的门序列， 若这个门序列的长度大于模板长度的一半，则可以件j 模板剩余的l j 序列替换当前电路中这部分门守列，从 而减少电路逻辑门数量，达到电路优化的目的。 本文在前者基础上提出了类似的规则优化方法，并结合模板优化方法的一些优点，使之更加适合本文 所提出的综合算法。实验结果表明，此方法可以有效地减少电路中门的数量。 1 3 工作内容与论文组织 改进量子可逆电路自动生成与优化的相关技术，设计综合与优化的高效与实用的算法，提高可逆电路 自动生成的效率，一直是本研究小组的研究目标之一。本文所做的就是，通过对合成方法与优化技术的探 讨，寻找出高效的电路综合及优化方法，并验证其有效性与可川性，为后续研究提供相应的理论基础与实 验依据。 本文的组织结构如下： 第一章，主要是对量子计算中可逆逻辑电路综合问题的研究背景做了简要的介绍；总结了当前几种具 有代表性的综合方法，并分析了它们各白的特点；此外，简要总结了可逆电路的优化问题的研究状况及主 要方法，亦分析了各自特点。在此基础之上，引入了本文的综合方法与优化思路。 第二章，先后对量子计算的相关基础知识进行了简述。包括量子力学基础概念、量子比特、叠加态等； 详细探讨了量子门与可逆逻辑中的特性，对可逆逻辑综合中经常面对的相关问题做了必要的解释；最后， 简单讨论了量子电路的物理实现。 第三章，对目前比较具有代表性的综合方法与综合思想进行了详细归纳，包括穷举法，真值表法， r e e d m u l l e r 方法，群论方法及多值逻辑综合中的算法，并总结了各种方法的优缺点。 第四章，分别针对三比特及n 比特( n 3 ) 的情况，提出了基丁真值表变换的综合方法，采用了变换法 的思路，并借助对换、邻接矩阵等工具，实现可逆电路的高效综合；同时也给出了综合的例子；另外，提 出了规则优化方法，在讨论了门序列的抵消、交换、约化等规则的基础之上，参考模板优化技术，对综合 结果进行优化。 第五章，对于第四章提出的算法与优化方法，分别通过实验来验证其效率。 第入章，是全文的总结以及未来工作的展望。 3 东南人学硕 ：学位论文 第二章量子计算与可逆逻辑电路 量子计算机是一类遵循垃子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。当 某个装置处理和计算的是量子信息，运行的是量子算法时，它就是量子计算机。 2 1 量子计算基础 2 1 1 量子比特 比特( b i t ) 是经典计算和经典信息的基本概念，同样，量子计算与量子信息是建立在类似的概念量子 比特( q u a n t u mb i t 或q u b i t ) 的基础之上。 经典计算中，二进制信息以比特形式存储，物理上是一个在电晶体电子电路中的电压信号；数学上， 一个b i t 表示成一个布尔值或变量。在量子领域，二进制信息以量子状态形式存储，比如光子的偏振( 水平 的垂直的) 、围绕单个原子的电子的两种状态( 基态激发态) 或均匀电磁场中电子原子核的白旋( 向上 向卜) 。不同丁经典比特，一个量子比特能够以其经典比特的一个叠加态的形式存在，任何外界刺激都会 扰乱该叠加态，人多数情况是破坏该状态( 典型的破坏如测量操作) 。 量子计算能实现并行运算的根本原因，在于量子比特具有“替加状态”的性质。经典计算机每个比特只能 取一种可识别的状态0 或“1 ”，而量子比特不仅可以取“0 ”或“l ，还可同时取0 和“l ”，即其替加态。依此类 推，1 1 位经典比特仅能代表2 “中的某一态，而n 位量子比特却能同时表示2 “个替加态，这正是量子世界神 奇之处。运算时量子计算只须对这2 “个量子叠加态处理一次，这就意味着一次同时处理了2 “个苗子比特( 同寞 样的操作传统计算机需处理2 “次，因此理论上量子计算丁作速率可提高2 “倍) ，从而实现了并行运算。 v 经典比特是两态系统，即要么是0 要么是1 ；在d i r a c 符号系统中，量子状态表示成i o ) 和1 1 ) ，它们是 两个独立的极化状态，以这两个独立态为基矢，张起一个二维复矢量空间。与经典信息的状态必不会在0 、晦 1 之外不同，量子比特的状态能够落在i o ) 和1 1 ) 之外，由一个二元向量形式的线性组合 l 妒) - a o ) + 卢1 1 ) ( 2 1 ) 来代表，称为叠加态，其中a 和b 是复数且满足归一化条件l a l 2 + 1 8 1 2 = 1 ，一个q u b i t 就是一个二维h i l b e r t 空 间。我们无法通过测量手段确定一个q u b i t 的状态，也就是无法得到a 和b 的值，我们只能得到量子状态的 有限信息，即测得0 的概率是l a l 2 ，测得1 的概率是l b l 2 。一个量子比特( 如等式2 1 所示) 也可改写为 l 小一( c o s o 0 + e 却s i n o f l 1 ) ) ( 2 2 ) 其中e i r 不具有可观测性，因此可以略去，由0 和，定义t - 维单位球面上的一个点，这个球面通常被称为 b l o c h 球面( 见下图2 1 ) 。 l o ) 。 1 1 ) 图2 - 1 单量子比特的布洛赫( b l o c h ) 球表示法 假如有两个量子比特，对应于经典态的0 0 、0 1 、1 0 和1 1 ，这个双量子比特有四个基矢：i o o ) 、1 0 1 ) 、1 1 0 ) 和1 1 1 ) ，同时它也可以处于这四个基矢的叠加，该量子状态包含相应基矢的复系数，也称为概率幅，双量子 4 张量运算的q u b i t 状态本身就蕴涵了一种火规模并行计算的方法，冈为替加态允许一个n 量子比特的状态 妒) = ；= ：1 qi 岛一一。6 f 一一：，6 f ，。) ( 2 4 ) 同时存储2 “个二进制数，每一个q 都是一个复数且满足条件 7 0 1 l c f l 2 = 1 ，并且岛一一a 一埘，岛，。是f 的：_ 二进 制展开。 2 。1 2 量子比特的存储 经典计算机的信息存储单位是比特，类似地，量子计笄的信息存储单位是量子比特，量子比特的两种 状态的表示常用以下两种方式： ( 1 ) 利用电子白旋方向。如向左自旋状态代表“1 ”，向右自旋状态代表“o ”。电子的白旋方向可通过电磁 波照射加以控制。 ( 2 ) 利州原子的不同能级。原子有基态和激发态两种能级，规定原子基态时为“0 ”，激发态时为“1 ”。其 具体状态可通过原子光谱或核磁共振技术辨别。 n 个量子位的有序集合称为n 位量子寄存器。它的态是n 位量子态的张量积( t e n s o rp r o d u c t ) ，亦称直积， 用符号。表示。 若彳。( 三：a 吼o 。l ，b2 ( 乏2 ：) ，则爿。曰_ ( 三：茗a q o 。l b b ) ，c 2 5 ， 量子计算在处理0 一n 个数相加时，采用的是并行处理方式将n 个数据( 比如n = 2 时，4 个数据：0 0 、o l ， 1 0 、1 1 等) 同时输入处理器，并在最后做一次运算得出结果。无论有多少数据，量子计算都是同时输入， 运算一次，从而避免了传统计算机输入一次运算一次的耗时过程。当对海量数据进行处理时，这种并行处 理方式的速率足以让传统计算机望尘莫及。 2 1 3 相干性 量子计算除了其并行性以外，还具有高效性，这源于量子的另外一个特性量子相干性。量子相干 性是指晕子之间的特殊联系，利用它可从一个或多个量子状态推出其它量子态。比如两电子发生止向碰撞， 若观测到其中一个电子是向左自转的，那么根据动量和能量守恒定律，另外一个电子必是向右自转。这两 电子之间所存在的这种联系就是量子相干性。 可以把量子相干性应用于存储当中。若某串量子比特是彼此相干的，则可把此串最子比特视为协同运 行的同一整体，对其中某一比特的处理就会影响剑其它比特的运行状态，量子计算机之所以能快速高效地 运算缘归于此。然而量子相干性很难保持，在外部环境影响下很容易丢失相干性从而导致运算错误。虽然 采用量子纠错码技术可避免出错，但其也只是发现和纠正错误，却不能从根本上杜绝量子相干性的丢失。 因此，到达高效量子计算时代还有一段漫长曲折之路。 2 2 量子逻辑门 为保持量子位的态所在的h i l b e r t 空间的本征态的正交归一性，对量子位的态进行的变换的算符u ，均 有酉性【2 8 l 【2 9 l ( u n i t a r y ，或称幺正性) 要求，即：( u 为u 的共轭转置矩阵) u u i 或u t u 一， 一 ( 2 6 ) 5 东南人学硕上学位论文 对量子比特的幺正操作就是量子逻辑门，简称量子门。量子逻辑门是量子逻辑电路的最基本单元，不 过它不再川电子的宏观统计特性朱表征，而是刚微观粒子的个体行为状态来描述它将一个态演化为另一 个态。例如，电子等微观粒子的白旋、电子在不同能级上的跃迂等等。酉性是餐子逻辑l 、j 的惟一限制，每 个i 珥矩阵都定义一个有效的鼍子i 、j 【2 8 1 【3 0 】。基本的量子i j 按涉及到的比特数分为单比特鼍子f j 年i i 多比特量子 门。常川的单比特量子fj 有h a d a m a r d 门和相何门和旋转门等：多比特量子| 、j 有c o n t r o l l e d n o t 门， c o n t r o l l e d p h a s es h i f t 门，s w a p 门和t o 丘b l ifj 等。部分逻辑fj 的西矩阵及对应的图符号如表2 - 1 所示： 表2 - 1逻辑i 、 及相戍的i 【l 路图符i j 表示 7 1o o 0 o1o o廿 【r 1 i l1 士 c 匕。 oo1o 肌万【1 - 1 j r 10 】 000p 寸 廿耻i op l i 1 0 00 。 f 1 0 00 1 享 l o100 工 s w a p 一 | 0 o1 0 i “i oo ol 1 0 100 i l oo1o l o o ol l l 对于任意的状态i x ) i y ) i z ) 分别使用h 门、r 门、c p 门、c n 门、s w a pi j 矛lt o f f o l i 门分别得到： l z ) l ( 一1 ) l x + l l - x ) l 工) k p 刮r 4i z ) 俐y ) j k 扩卅矿小) 1 ) ，) f ，7 、 俐y ) j k 俐) ，o x ) 蚓y ) - 俐x ) 俐y ) i z ) 旦俐) ，) i zo 砂) 量子信息经过各个量子逻辑门时，依据门的功能发生相应的变换。从数学的观点，量子逻辑门对量子 信息的操作可以用一个幺止矩阵m 来表示，幺止变换的一个重要特点就是这些变换都是可逆的，即每个罐 子逻辑fj 也是可逆的。若干个量子逻辑门的排列，组成了一个可逆逻辑电路，这个电路实现了某个可逆逻 辑函数功能。量子逻辑门通过幺正变换实现了一个可逆函数，这就是利用量子力学构建可逆逻辑电路的实 验基础。量子逻辑门不带有信息的擦除操作( 输入信息的丢失) ，在理论上也就不存在热耗散的极限，从而 杜绝了经典计算机从根本上无法解决的热耗散严重影响器件正常功能的问题。d e u t s c h 最早考虑了川量子逻 辑门来构造计算机的问题，他发现几乎所有的三比特量子逻辑门都是通t h j 逻辑门。所谓通j j 逻辑门是指， 通过该逻辑门的级联，能够以任意精度逼近任何一个幺止操作。后来，有一些研究人员发展了d e u t s c h 的结 论，最终d e u t s c h 和l l o y d 各自独立地证明了几乎所有的二比特量子逻辑i j 都是通刚的，这里“儿乎”是