（计算机软件与理论专业论文）基于真值表演算的量子可逆逻辑电路综合.pdf

q u b i tr e v e r s i b l el o g i c c i r c u i t s s y n t h e s i sb a s e do nt r u t h t a b l e p e r m u t a t i o n ad i s s e r t a t i o ns 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 y a n gz h o n g m i n g s u r ；r v i s e dbybupervlsea p r o f e s s o rh a n w uc h e n s c h o o lo fc o m p u t e r s o u t h e a mm7，帆7 叭mm6帆7叭1删y ，。、。、一：7 东南大学学位论文独创性声明 本人卢明所呈交的学位论文是我个人在导师指导下进行的研究l ：作及取得的研究成果。尽我所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰弓过的研究成果，也不包含为获 得东南人学或其它教育机构的学位或证书而使用过的材料。与我一同1 i 作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示了谢意。 研究生签名：旌查丛日期： 伊臼“ 东南大学学位论文使用授权声明 肇 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件剃电子文档， 可以采刚影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密 期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括以电子信息形式刊登) 论文的全部内容或中、 英文摘要等部分内容。论文的公布( 包括以电子信息形式刊登) 授权东南大学研究生院办理。 研究生签名：坦导师签名 摘要 中文摘要 随着量子计算与量子信息的深入发展，量子可逆电路的应用越来越多。可逆电路实现的是 一个双射的可逆逻辑函数功能。由于它的可逆汁算的功能，叮逆电路不仅能够应用在量子计算， 它同样可以应用在低功耗c m o s 、纳米技术以及光计算等领域，因此量子可逆逻辑电路的研究 对于量子计算与量子信息的发展具有重要的意义。 探讨以较小的代价( 最少的可逆门) 自动高效地构造量子可逆逻辑电路，是可逆逻辑电路 综合研究的重点。目前，各种量子逻辑电路综合算法，都存在量子逻辑电路规模小、综合代价 过高、优化时空复杂度高等一系列问题，还不能满足未来量子计算和量子信息以及其他领域对 量子可逆逻辑电路要求。本文采用扩展的通用t o f f o l i 门( e g t ) 作为基本门库，综合出全部 三量子最优电路；然后以三量子最优电路为基础，提出了一种新颖的四量子可逆逻辑综合方法； 接着通过三条规则( 消去、合并和移动) 对电路进行优化，通过真值表输出端置换的思想，综 合四量子可逆逻辑函数，以减少e g t 门的数量；最后对四量子电路综合方案进行递推拓展， 提出两种任意量子可逆逻辑电路综合的新方法：基于三量子最优电路的多量子电路综合， 基于二分法思想的多量子电路综合。 选用e g t 门库综合出全部的三量子电路，共4 0 3 2 0 个，与传统选用t o f 门库综合相比， 电路最大长度减少了2 个门( 从8 减少到6 个门) ，平均长度减少了2 1 9 8 ( 从5 8 7 减少到散 4 5 8 个门) 。四量子电路综合方法是先将一个四量子电路的函数表示成真值表的形式；通过线 拓扑变换和对换演算，将四量子电路映射函数的真值表分解成2 块相互独立的三量子电路映射 函数的真值表；查找相应的最优三量子电路，直接生成相关电路；最后将对换演算的电路并入。 该电路，经过局部优化即可生成最终电路。分析结果表明，用这种方法综合_ 四量子电路平均需”、 1 3 1 6 个e g t 门，最多只需要2 0 个e g t 门。与同类算法相比，大幅减少e g t 门的数量，同时 还避免了时空复杂度太大的问题，便于经典计算机实现。使用输出端置换思想改进四量子电路 综合方案，分析结果表明，平均e g t 门的数量减少了1 6 8 1 ( 从1 3 1 6 减少到1 0 9 5 个门) ，进。 一步降低电路综合的代价。 关键词】：e g t 门；可逆逻辑；电路综合；4 量子；多量子；二分法；置换 东南人学硕一l ：学位论文 a b s t r a c t w i t ht h ef u r t h e rd e v e l o p m e n to fq u a n t u mc o m p u t a t i o na n dq u a n t u mi n f o r m a t i o n ，t h eq u a n t u mr e v e r s i b l e c i r c u i ta p p l i c a t i o n sa r em o r ep e r v a s i v e ar e v e r s i b l ec i r c u i tr e a l i z e sab i j e c t i v er e v e r s i b l el o g i cf u n c t i o n f o ri t s r e v e r s i b l ec o m p u t i n g ，r e v e r s i b l ec i r c u i tc a nb ea p p l i e dn o to n l yt oq u a n t u mc o m p u t i n g ，b u ta l s ot ol o w - p o w e r c o m s ，n a n o t e c h n o l o g y ，a n do p t i c a lc o m p u t i n g h e n c e ，r 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 t t od e v e l o pq u a n t u m c o m p u t a t i o na n dq u a n t u m i n f o r m a t i o n t h ed i s c u s s i o no nh o wt oa u t o m a t i c a l l ye f f i c i e n t l yc o n s t r u c ta r b i t r a r yq 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 h l o wc o s ti st h ef o c u so fr e v e r s i b l el o g i cc i r c u i ts y n t h e s i s a tp r e s e n t a l lk i n d so fq u a n t u ml o g i cs y n t h e s i s a l g o r i t h m sh a v em a n yp r o b l e m s ，s u c ha ss m a l l s c a l eq u a n t u ml o g i cc i r c u i t s ，t o oh i g hc o s tf o rr e v e r s i b l ec i r c u i t s s y n t h e s i s ，ah i g hd e g r e eo fs p a c e t i m ec o m p l e x i t y ，a n ds oo n t h e ys t i l lc a nn o tm e e tt h ef u t u r er e q u i r e m e n t so f q u a n t u mc o m p u t a t i o na n dq u a n t u mi n f o r m a t i o n ，a sw e l la so t h e ra r e a s i nt h i sp a p e r ，w i t ht h ee x t e n d e dg e n e r a l t o f f o l ig a t e ( e g z ) a sab a s i cg a t el i b r a r y , a l l3 - q u b i to p t i m a lr e v e r s i b l el o g i cc i r c u i t sa l es y n t h e s i z e d a n db a s e d o n a l l 3 - q u b i to p t i m a lr e v e r s i b l el o g i cc i r c u i t s ，an o v e lm e t h o df o r4 - q u b i tc i r c u i t ss y n t h e s i si sp r o p o s e d t h e n t h r o u g ht h r e er u l e sw h i c ha r ee l i m i n a t i o n ，c o m b i n a t i o na n dm o v e m e n tr u l e s ，t h ec i r c u i t sa r eo p t i m i z e d a n d t h r o u g ht h et r u t ht a b l eo u t p u tp e r m u t a t i o n ，t h em e t h o do f4 一q u b i tc i r c u i t ss y n t h e s i si si m p r o v e di no r d e rt or e d u c e t h en u m b e ro fg a t e s f i n a l l yt h r o u g ht h er e c u r s i o na n de x p a n s i o nf o rt h em e t h o do f4 - q u b i tc i r c u i t ss y n t h e s i s ，t w o 簸 k i n d so fn e wm e t h o d sf o ra r b i t r a r yq u a n t u mc i r c u i t ss y n t h e s i sa r ep r o p o s e d o n ei sb a s e do n3 - q u b i to p t i m a l r e v e r s i b l el o g i cc i r c u i t s ，a n dt h eo t h e ri sb a s e do nb i s e c t i o nm e t h o d b a s e do ne g tg a t el i b r a r y ，a j l3 - q u b i to p t i m a lr e v e r s i b l el o g i cc i r c u i t sh a v eb e e ns y n t h e s i z e da n dt h e r ea r e 婚 4 0 3 2 0c i r c u i t s c o m p a r e dw i t ht h et r a d i t i o n a lt o f g a t el i b r a r y ，t h em a x i m u ml e n g t ho ft h ec i r c u i tr e d u c e s 2g a t e s ，。 a n dt h en u m b e ri sf r o m8d o w nt o6 t h ea v e r a g e l e n g t ho f t h ec i r c u i td e c r e a s e sb y2 1 9 8 ，a n dt h en u m b e ri sf r o m 5 8 7d o w nt o4 5 8 t h em e t h o do f4 - q u b i tc i r c u i t ss y n t h e s i si sf i r s t l yr e p r e s e n t sa4 - q u b i tf u n c t i o nb yt r u t ht a b l e u s i n gt r a d i t i o n a lr e c u r s i v et h o u g h t 。t h r o u g ht h el i n et o p o l o g yt r a n s f o r m a t i o na n dt r u t ht a b l ep e r m u t a t i o n at r u t h 姆、囊 t a b l eo f 4 - q u b i tm a p p i n gf u n c t i o nc a nb ed e c o m p o s e d t ot w oi n d e p e n d e n tt r u t ht a b l e so f3 - q u b i tm a p p i n gf u n c t i o n 咿。 t h e nf i n dt h ec o r r e s p o n d i n go p t i m a l3 - q u b i tc i r c u i t s ，a n dd i r e c t l yg e n e r a t er e l e v a n tc i r c u i t m e a n w h i l et h ec i r c u i t s g e n e r a t e di np e r m u t a t i o nw e r ea d d e di n t ot h ec i r c u i tt o o a f t e ro p t i m i z a t i o n ，4 - q u b i tq 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 sa r es y n t h e s i z e df i n a l l y e x p e r i m e n t a lr e s u l t ss h o wt h a tt h en u m b e ro fg a t e st oc o n s t r u c tr e v e r s i b l el o g i c c i r c u i t si sl e s st h a no t h e rm e t h o d s f o ra n y4 - q u b i tb i n a r yl o g i cf u n c t i o n ，t h ea v e r a g ee g t g a t e si s1 3 1 6a n dt h e m o s te g t g a t e si s2 0 t h i sm e t h o dv o i d st h ee x p o n e n t i a ln a t u r eo ft h em e m o r yo rr u n t i m ec o m p l e x i t y ，a n di sv e r y s i m p l et oi m p l e m e n ti nc l a s s i c a lc o m p u t e r a f t e ri m p r o v i n gt h em e t h o do f4 - q u b i tc i r c u i t ss y n t h e s i sb yt h et r u t h t a b l eo u t p u tp e r m u t a t i o n ，t h ea v e r a g el e n g t ho ft h ec i r c u i td e c r e a s e sb y1 6 8 1 ，a n dt h en u m b e ri sf r o m1 3 1 6 d o w nt o1 0 9 5 k e yw o r d s ：e g tg a t e ；r e v e r s i b l el o g i c ；c i r c u i ts y n t h e s i s ；4 - q u b i t s ；m u l t i q u b i t s ；b i s e c t i o nm e t h o d ； p e r m u t a t i o n s 目录 目录 中文摘要i a b s t r a c t i i 第一章绪论1 1 1 研究意义1 1 2 研究现状 = “1 1 2 1 量子可逆电路的合成2 1 2 2 量子可逆电路的优化4 1 3 论文工作与组织结构4 1 3 1 论文工作4 1 3 1 论文组织结构5 第二章可逆逻辑综合基础6 2 1 鼍子逻辑门- 6 2 2 可逆逻辑函数8 2 3 可逆逻辑出路1 0 2 4 可逆逻辑电路综合代价。：1 1 第三 3 2 关键技术的实现：1 2 3 1 1h a s h 函数的构造1 2 3 1 2 最小长度整体综合算法1 3 3 1 3 读取h a s h 表中所求量子电路的算法。1 4 3 3 基于e g t 门库的三量子电路综合1 5 3 4 实验结果1 6 3 5 小结，彳互：j 1 7 第四章基于真值表演算的四量苌电路综畲_ 1 8 4 1 四量子电路综合方案1 8 4 1 1 真值表中两元素互换规则1 8 4 1 2 多位比特位不同的两元素互换2 0 4 1 3 不同比特位的提取( 配合n o tf - j ) 2 1 4 2 算法实现2 3 4 3 算法分析2 4 4 4 电路优化2 s 4 4 1 优化规则2 s 4 4 2 优化规则的使用算法2 6 4 s 实验结果2 8 4 6 ，j 、结2 9 第五章基于输出端置换的四量子电路综合3 0 5 1 输出端置换的基本思想。3 0 5 2 输出端置换方法的应用3 l s 3 实验结果及分析。3 3 东南人学顾1 ：学位论文 5 3 1 三量子最优电路综合的改进3 3 5 3 2 四量子电路综合的改进。3 4 5 4 ，j 、结3 5 第六章多量子可逆逻辑电路综合3 6 6 1 基于三量子最优电路的多量子电路综合3 6 6 1 1 基本思想3 6 6 1 2 综合过程3 7 6 1 3 算法分析3 8 6 2 基r 二分法思想的多量子电路综合3 9 6 2 1 基本思想3 9 6 2 2 综合过程 4 0 6 2 3 算法分析4 1 6 3 算法比较分析：4 1 6 4 ，j 、l 砉z 1 3 第七章总结与展望：4 4 7 1 工作总结4 4 7 2j 琵望：4 4 致谢z i s 参考文献。4 6 在校期间发表文章：4 8 第一帝绪论 1 1 研究意义 第一章绪论 量子计算机可等效量子图灵机，理论上已证明，量子图灵机可等价量子逻辑电路1 1 j ，量子 逻辑门的组合与级联是组成量子计算机的基本元素。迄今为止，世界上还没有真i f 意义上的量 子计算机，实现量子计算机的技术困难重重，但量子计算机的实现必将为信息科学与通信技术 带来革命性的突破。1 9 9 4 年e w s h o r 给出了基于量子计算机的质数因数分解的快速算法但j ，能 在很短的时间内破译基于大因数分解困难性提出的r s a 公钥密码体制；1 9 9 6 年l k g r o v e r 发表 了基于量子计算机的数据库检索问题的快速算法【3 l ，能在数分钟内破译d e s 算法( 以1 0 6 次 秒的速度计算) ；量子念的叠加性保证通信信道容量的超加法性；量子态的纠缠和干涉性使得 信息能超空间传送( 量子隐形传态) ；量子态的不可克隆性，确保网络信息安全、实现不可破 译、不可窃听的保密通信等。还有其他方面都可突破现有经典计算机及其信息处理系统的极限， 其相关方面的综述性文献可参见【4 ，5 】。因此世界主要经济发达国家都在制定战略性规划，各国 有代表性的实验室币以巨大的热情投入人财物，期望在新一代计算机的科学与技术上占据领导 地位。量子可逆逻辑逻辑电路的设计、优化与测试等方法的研究，作为量子信息与量子计算理字 论的基础研究越来越受到人们的关注。 量子可逆逻辑综合源于可逆计算机的研究。2 0 世纪中叶，人们发现计算机芯片的能耗导致 芯片发热，限制芯片集成度，影响计算机的运行速度。l a n d a u e r 发现，芯片能耗主要源于计算 中的不可逆操作【6 1 。例如，对两比特的异或操作，因为只有一比特的输出，这一过程损失了一 ? 个自由度，因此是不可逆的，按照热力学理论，必然会产生一定的热量。但这种不可逆性是不 是不可避免的呢? 事实上，只要对异或门的操作进行简单改进，即保留一个无用比特，该操作 就变为可逆。因此降低能耗的关键是将不可逆操作变为可逆操作，b e n n e t t 对此有严格证吲。 经典计算机本质上是通用图灵机，是不可逆的，但所有不可逆通用图灵机，都对应一个可逆图 矗 灵机，且两者的计算能力和计算效率完全相同。量子逻辑门都是可逆的，在量子力学中，它就 可以用一个幺正变换来代表。基于其可逆性，e b e n i o f f 8 1 等人最早提出用量子力学来描述可逆 计算机。量子电路理论上不丢失输入信息，因此也不存在热耗散，从而从理论上有效地解决了 芯片的热耗问题。 类似于经典逻辑门电路构建了经典计算机，量子计算机由量子逻辑门电路构造。量子逻辑 门是量子计算机的基本单元，从数学角度看，每一个量子逻辑门的操作都可以用一个幺正矩阵 算子m 来表示，m 实现信息的幺j 下变换，而幺正变换的一个重要特点就是变换都是可逆的， 也就是说，每个量子逻辑门都是可逆的。若干个量子逻辑门的合成，组成了一个可逆逻辑电路， 这个电路将实现某一可逆逻辑函数功能。所谓可逆逻辑函数，就是一个n 位输入和n 位输出的 双射函数一一即每一个输入唯一对应一个输出。可逆逻辑电路不仅应用在量子计算中，它同样 可以应用到低功耗c m o s 电路、纳米技术、光计算、加密技术等领域，因此可逆逻辑电路正在 成为一个新兴的研究领域。 1 2 研究现状 量子电路可逆逻辑综合，主要研究在给定的量子门和量子电路的约束条件及限制下，使量 东南人学硕：学位论文 子呵逆逻辑电路的代价最小；研究接近最优化量子代价或为非最优量子代价提速的量子电路可 逆逻辑综合理论和方法；研究接近最优化的可逆逻辑电路e 成方法。量子电路可逆逻辑综合包 含合成和优化两个方而，量子可逆电路的合成是指，通过给定一个可逆逻辑函数的输入、输出 值，能够通过合成算法得到实现该函数功能的可逆逻辑电路。然而，各种合成法得到的量子可 逆逻辑电路往往不是电路代价最小的最优电路，一般意义上，量子可逆电路的代价是指量子电 路中逻辑门的数量。为了得到最优电路，相应的，出现了量子可逆逻辑电路的优化技术，其思 想是能够在不改变可逆电路函数功能的条件下，对电路进行重组、替换，达到减少电路逻辑门 数量的目的，从而降低了量子可逆电路的代价。现在也有些方法，将合成与优化这两个过程同 时进行，而且已成为综合方法的主流。 1 2 1 量子可逆电路的合成 最近3 0 年，人们提出了多种可逆量子门，如控制非门( c n o t ) 1 9 j 、t o f f o l i 门u 叫、f r e d k i n r i l l 等。如何使用指定量子门库自动合成量子代价较小( 量子门的数量最少) 的可逆电路，是 量子可逆逻辑综合研究的关键问题之一。目前比较有代表性的合成方法如下： ( 1 ) 穷举法【1 2 】【1 3 l 【1 4 1 其思想是对于给定的函数功能以及可供选择的门类型，按照电路长度的增加，依次生成所 有可能的电路，直至找到实现该函数功能的电路为止。穷举法是按电路长度从小到大的顺序寻 找电路的，所以它得到的电路必定为最优电路。文献 1 2 1 3 利用穷尽搜索法，综合出所有三誊 量子最优电路，但此类算法缺乏普遍适用性。结果表明，n 变量可逆逻辑函数的数量是? ! 。当 ，l 苫4 时，目前技术还无法实现同时存储r ! 个可逆电路，且运行时间也无法忍受，这是个p s p a c e 难题。z h i q i a n gl i 1 4 1 采用多种压缩方法综合四量子电路，也只能综合出f i ；j 8 层最优电路。 ( 2 ) 探索法【1 5 1 【1 6 1 1 1 7 】 其根据给定的函数功能，带有目的性的选择逻辑门，不断试探性的生成电路，直至找到实 现该函数功能的电路为止。这类方法的特点是通过相应的参数变化决定选择何种逻辑门进行电 路合成，如通过测量汉明距离【1 5 1 ，r a d e m a c h e r w a l s h 谱均数【1 6 1 、二进制共享决策图【1 7 l 等。实 际上，这类方法是穷举法的改进，它通过一些约束条件缩小了电路的穷举范围，减少了的搜索 次数。 ( 3 ) r e e d m ulle r ( r m ) 法1 8 l 【1 9 i 1 2 0 1 【2 1 l 【2 2 1 r e e d - m u l l e r 法类似于探索法，将表示布尔函数的正极r e e d m u l l e r 展开式用简洁的系数向 量( 口n ，a 1 一，a ，。，) ( “光谱”) 表示。给定一个规模n 的量子逻辑电路，它的r m 光谱可视为一个i n 的表，其中每列表示对应的量子逻辑电路输出的r m 光谱，可以利用类似于快速离散傅立叶变换 的技术来有效计算出。然后根据输出端表达式中的因子来选择t o f f o li 门，再对表达式进行化 简。对于某根输入输出线，选择其输出表达式中不包含该输入输出线的因子f a c t o r 作为 t o f f o l i 门的控制端，该输入输出线e 为受控端，从而得到一个t o f f o l i 的变换式 = uf a c t o r ，将输出端表达式中的所有b 替换为屹f a c t o r 后，该输入输出线屹的表达式 就有可能将所选取的因子f a c t o r 消去，再根据变换后的表达式选取t o f f o l i 门。不断的用不同 的因子进行试探，直至表达式恒等为止。 m i l l e r 1 8 1 1 9 i 等人应用谱函数实现近似最优的可逆电路，m i s h c h e n k o 2 0 1 、g u p t a 2 1 1 和 2 第一章绪论 z h i q a n gl i 2 2 l 等人给出了基于r e e d m u l l e r 的启发式规则，大大改进了算法的性能，提高了算 法的效率。r e e d - m u e f 去是对探索法的改进，在小规模电路综合中效果很好。它缩小了电路 的试探代价，缩短了运行时间。但是，这类方法由于缩小了选择范 ；i ，并且对于综合效果没有 回馈也没有预测，所以它不能保证综合算法的收敛，即电路综合失败。 ( 4 ) 真值表法 真值表法是种贪心算法，它根据给定的函数功能，有目的的选择逻辑门，不断试探生成 电路，直至找到实现该函数功能的电路为止。通常有三种做法：前向综合：先按照歹的升序， 对每一个j 寻找使得，( ) 可，再通过选取t o f f o li 门，将转换为j ，重复此过程直至满足 v ，厂( 厂) ：，将选择的门顺序排列；后向综合：先按照珀升序，对每个j 选取t o f f o l i 门，将，例转换为t 重复此过程直至满足vt ，俐可，将选择的门逆序排列；双向综合： 综合前面两种方法，先按照珀勺升序，对每个j ，寻找使得，倒- - - 1 ，若y a m ( kf 例) = h a m ( l 力，使用后向综合，否则使用前向综合。其中，h a m 表示汉明距离。设i = ( 之) ：， j f ( ，z ，n ) z j 与之间的汉明距离为： 协m o ，_ ) 2 荟以p q ( i k ，止) ，其中布尔函数 n e q ( i ，f ) ；j ”。它通过一些约束条件缩小了电路的穷举范围，减少了的搜索次数。 致 【o , i2 m a s l o v 2 3 l 等人率先在量子可逆电路综合中提出真值表构造法以及使用模板技术优化电路。 此方法构造巧妙，综合电路迅速，而且可适用于任意比特电路，但综合出的电路通常不是最优蛾 的，需要辅之以模板优化。 ( 5 ) 群论的方法f 2 4 】【2 5 l 【2 6 l 此方法是将一个量子逻辑电路看成一个置换，则，l x n 规模的所有电路等价于对称群s ，。 这方面的研究已逐渐成为一个研究的热点。a d ev o s 和y v a nr e n t e r g e m 2 4 1 是用群论中 的双陪集对n n 规模的电路作了一个等价类划分，使得，l x n 的电路变成一个代表元电路与 o 一1 ) 一1 ) 电路的级联电路，递归分解将大规模的电路构造转化为小规模的电路构造，随后 又使用左、右陪集代替双陪集来缩小等价类的阶 2 5 1 。g u o w uy a n g 和x i a o y us o n g 2 6 1 等人对 具体的循环置换的实现进行了研究，提出对于偶置换电路选择3 一循环置换作为电路基元，将问 题转化为对3 一循环置换的电路实现。一般来说，群论方法较为复杂，构造的门库较大，代价较 高。 ( 6 ) 专用构造方法 根据一些特定功能的可逆逻辑电路的特点，用专用构造算法，快速生成电路。如用 b i t o n i c 2 7 j 方法可快速构造大规模的量子排序电路，然而这些算法不具有通用性，但性能较好。 例如构造可逆排序电路，如果用其它方法，则算法复杂性较高，且构造的电路没有规律，很难 由此直接构造更大的排序电路。 可以看出，穷举法综合结果虽好，能达到最优，但时间、空间开销巨大，实用性不强：真 值表法、探索法、r m 方法算法构造巧妙，综合速度快，但结果不尽理想，需要辅以优化；群论 方法新颖高效，算法收敛迅速( 有限步结束) ，但构造复杂，需要的门库较大。目前大部分算 蛀只能综合3 量子电路，在综合4 量子电路时不是运行时间太长，内存消耗太快，就是无法达到 3 东南人学硕i j 学位论文 最优或较优。 1 2 2 量子可逆电路的优化 通过各种合成方法合成的电路( 穷举法除外) ，往往不是电路代价最小的最优电路，这使 得电路优化技术成为另一个研究重点。量子可逆电路的优化目标是保持电路函数功能不变条件 下，尽可能的减少电路的代价( 电路逻辑门数量) 。目前有代表性的优化方法如下： ( 1 ) 特定规则优化 1 w a m a 2 8 j 等人给出了以c n o t f l 为基础的电路转换规则。该方法的输入部门是以一个t o f f o l i 门为基本元素的可逆逻辑电路，其输出的是一个标准型的t o f f o l i 门可逆逻辑电路。这个标准 型是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 t ) 的直接可逆执行，同时也是一个z h e g a l k i n 多项式。 1 w a m a 证明了任何一个电路都能通过确定的可逆操作得到一个标准型，标准型可以转化成一个 最小电路。遗憾的是，他没有给出任何通过转换集合简化电路的方法。一般地，分析e x o r 操作 是非常困难的。事实上，目前最好的布尔e x o r 多项式只实现到6 变量的函数。因此，当前的工 作停留在启发式的处理方法上。 ( 2 ) 模板优化 模板是一个实现恒等函数功能的电路。模板优化技术实质上是两个等价子电路问的替换。 m a s l o v 等人对模板技术做了深入的研列2 3 】【2 9 1 【3 0 】。模板优化技术的核心思想是，在待优化的电 路中，找到一个同模板部分门序列相一致的门序列，若这个门序列的长度大于模板长度的一半，磐 则可以用模板剩余的门序列替换当前电路中这部分门序列，从而减少电路逻辑门数量，达到电 路优化的目标。在量子可逆电路的优化方面，模板技术是较为通用的优化技术，其核心思想简 明有效。w e n q i a nl i 等人发现m a s l o v 模板存在着缺陷( 控制线不完整性) ，提出了类模板优化。 技术【3 1 1 ，其特点是在相同的模板基本电路条件下，类模板能够无遗漏的提供合适的模板，进行”+ 电路优化。由于模板优化需要寻找与模板匹配的子电路，因此优化需较长的时间；另外模板优 化减少门的数量也是有限的，不能保证优化得到的电路是最优的。 总之，目前量子逻辑电路综合算法还存在着量子逻辑电路规模小、量子代价过高、优化过j ： 程中时空复杂度高等一系列问题，还不能满足未来量子计算和量子信息以及其他领域对量子电甜n i 路逻辑电路要求。因此，系统而深入的研究量子可逆电路的合成及优化技术，寻找更为高效的 j 合成和优化算法是很有必要的。 1 3 论文工作与组织结构 1 3 1 论文工作 怎样能以较小的代价( 最少的可逆门) 自动高效地构造任意量子可逆逻辑电路，是本文的 中心工作。现在，三量子可逆逻辑电路的综合问题已基本解决，四量子及多量子可逆逻辑电路 综合方法的探讨才刚刚起步。本文概括介绍量子可逆逻辑电路综合的研究意义、研究现状和基 础知识；采用扩展的通用t o f f o l i 门( e g t ) 作为基本门库，综合出全部三量子最优电路；然 后以三量子最优电路为基础，通过线拓扑变换和真值表演算，巧妙的把一个四量子电路转换成 两个三量子电路综合，提出了一种新颖的四量子可逆逻辑综合方法；接着通过三条规则( 消去、 合并和移动) 对电路进行优化，通过真值表输出端置换的思想对四量子可逆逻辑电路综合方法 进行改进，以减少e g t 门的数量；对四量子电路综合方案进行递归扩展，提出两种任意量子 可逆逻辑电路综合的新方法：基于三量子最优电路的多量子电路综合，基于二分法思想的 4 笫一章绪论 多量子电路综合；最后对全文进行总结和展望。 全文涉及的所有算法，都在v c 6 0 环境下编程实现，并对实验结果作了详细的比较分析。 1 3 1 论文组织结构 本文主要阐述基于真值表演算的可逆逻辑电路综合算法、优化技术以及改进方案。全文共 分为七章： 第一章绪论，概括介绍量子可逆逻辑电路综合的研究意义、研究现状和本文研究任务。 第二章量子可逆逻辑电路综合概述，详细介绍了量子逻辑门、可逆逻辑函数、可逆逻辑电 路等可逆电路综合方面的基本概念。 第三章用扩展的通用t o f f o li 门( e g t ) 作为基本门库，综合出全部三量子最优电路，并 与传统选用t o f 门库综合三量子电路相比较。 第四章介绍了种新的四量子电路综合方法。该方法通过线拓扑变换和真值表演算，巧妙 的把一个四量子电路转换成两个三量子电路，从而完成电路综合；最后通过消去、合并和移动 三条规则对可逆电路进行优化。 第五章阐述通过输出端置换思想对四量子电路综合方法进行改进，进步减少可逆逻辑门 的数量。 第六章多量子可逆逻辑电路综合，提出两种多量子电路综合方案：基于三量子最优电路 的多量子电路综合，基于二分法思想的多量子电路综合。 爹 第七章对全文总结并对未来展望。 东南人学硕i ：学位论文 第二章可逆逻辑综合基础 量子计算机可以等效为量子图灵机，但量子图灵机只是一个抽象的数学模型。理论上已证 明量子图灵机可以等价为量子逻辑电路，因此可以通过某些量子逻辑门的级联构成量子计算 机。因为量子逻辑门是可逆的，所以其输入和输 h 比特数相等。 量子可逆逻辑电路的输入数与输出数相等，是输入向量与输出向量一一映射的电路。因此， 输入向量的状态可以唯一地被输出向量重构。通过函数的方式描述：如果函数的每一个输入向 量唯一地映射一个输出向量，则称可逆函数，那么一个咒变量的可逆函数也可以定义为整数集 o ，1 ，2 ，2 一1 自身的映射。一个不可逆函数总可以通过变换找到它的可逆函数，同时会因此 ij 产生相应的垃圾信息位。本章对后续章节中用到的知识点做概要介绍，若需对量子计算和可逆 逻辑电路有更详细的了解，请阅读参考文献 4 。 2 1 量子逻辑门 利用微观粒子状态表示的信息称为量子信息，其基本单位是量子比特( q u b i t ) ，与经典信扩 息不同，量子比特能够以叠加的形式存在，任何量子比特均可表示为一个二元向量，如“ l 驴) ：a l o ) + 卢1 1 ) ，其中a 和卢为复数，满足归一化条件：川2 + i 卢i 。= 1 。在量子计算中，一个 量子逻辑门对应一个幺正变换，根据输入与输出的对数，逻辑门可分为单量子比特门和多量子氐摹 比特门。常用的单比特量子门有n o t 门、h a d a m a r d f 和p h a s es h i f t 门等；多比特量子f i 有c 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 f f o l i 门等。本文用到通用t o f