（测试计量技术及仪器专业论文）量子可逆逻辑电路进化设计研究.pdf

， n a n j i n gu n i v e r s i t yo f a e r o n a u t i c s a n da s t r o n a u t i c s t h eg r a d u a t es c h o o l c o l l e g eo f a u t o m a t i o ne n g i n e e r i n g e v o l u t i o n a r y d e s i g n o f q u a n t u m r e v e r s i b l e l o g i cc i r c u i t s a 砀e s i si n i n s t r u m e n t a t i o ns c i e n c ea n dt e c h n o l o g y b y h u a n gy u a n y u a n a d v i s e d b y p r o f e s s o rw a n gy o u r e n s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g f e b r u a r y , 2 0 1 0 r 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进 行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外， 本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标 明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许 论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：董篮璧 日 期： 垄：主：旦一 l、 】一， 南京航空航天大学硕士学位论文 摘要 本文研究量子可逆逻辑电路进化设计方法，论文主要研究工作为： ( 1 ) 分析了量子可逆电路的研究现状，阐述了量子可逆逻辑门和相关定理，介绍了基本的 量子可逆逻辑电路。给出了现有的各种量子可逆逻辑电路综合方法的总结分析。 ( 2 ) 研究了基础量子逻辑门组成的可逆电路的进化设计方法。利用遗传算法作为优化算法， 完成了量子电路优化设计中二进制编解码、交叉操作、变异操作、适应度函数设计等。以四输 入可逆逻辑电路设计为例，验证了进化设计方法是有效的。实验结果表明，该方法在进化较少 输入的可逆逻辑电路时，可以很快找到最优解，效率较高。 ( 3 ) 提出了实数位串编码方法，该方法在进化可逆逻辑电路时不需要建立量子门库，编码 方法简单。针对由常用量子门组成的可逆逻辑电路，研究了其多目标进化设计方法。完成了1 位可逆全加器和4 * 4 可逆乘法器的优化设计，该方法对电路的功能、量子门数、垃圾位数和量 子代价同时进化，取得了很好的优化效果。 ( 4 ) 面向复杂的量子可逆逻辑电路优化设计，提出了矩阵编码方法。设计了8 * 8 可逆乘法 器，通过实验结果分析，验证了改进后的编码方法进化复杂量子可逆逻辑电路的优越性。 关键词：量子电路；可逆逻辑；优化设计：遗传算法；低功耗集成电路；t s g 门；可逆乘法器 -、 量子可逆逻辑电路进化设计研究 a b s t r a c t i nt h i sp a p e r , r e s e r c ho ne v o l u t i o n a r yd e s i g nm e t h o do 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 ti sm a d e t h em a i nr e s e a r c hw o r k so ft h i sd i s s e r t a t i o nc a nb es u m m a r i z e da sf o l l o w s ： ( 1 ) t h er e c e n tr e s e a r c hs i t u a t i o no fq u a n t u mr e v e r s i b l ec i r c u i t sa l ea n a l y s i s e d ，t h er e v e r s i b l e q u a n t u ml o g i cg a t e sa n dr e l a t e dt h e o r e m sa r ed e s c r i b e d ，a n db a s i cq 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 a r ea n a l y s i s e d b a s i d e s ，t h ev a r i o u se x i s t i n gs y n t h e s i sm e t h o d so fq u a n t u m r e v e r s i b l el o g i cc i r c u i t s a r es u m m a r i z e d ( 2 ) t h ee v o l u t i o n a r yd e s i g nm e t h o do fr e v e r s i b l ec i r c u i tc o n s i s t e db yt h eq u a n t u ml o g i cg a t ei s s t u d i e d - t h i sp a p e ra d o p t sg e n e t i ca l g o r i t h ma so p t i m i z a t i o na l g o r i t h mt oc o m p l e t eb i n a r yc o d i n g ， d e c o d i n g ，c r o s s o v e r , m u t a t i o na n df i t n e s sf u n c t i o nd e s i g ni nt h eo p t i m a ld e s i g no fq u a n t u mc i r c u i t s t h ee v o l u t i o n a r yd e s i g no ff o u r - i n p u tr e v e r s i b l e l o g i cc i r c u i t ，a sa ne x a m p l e ，v e r i f i e st h a tt h e e v o l u t i o n a r yd e s i g nm e t h o di se f f e c t i v e 0 ) d e c i m a ls t r i n gc o d i n gm e t h o dh a sb e e np r o p o s e d ，t h em e t h o di nt h ee v o l u t i o no fr e v e r s i b l e l o g i cc i r c u i t sd o e sn o tn e e dt ob u i l dq u a n t u mg a t e sl i b r a r ya n de n c o d i n gi ss i m p l e d i r e c t i n gt ot h e g e n e r a lq u a n t u mg a t e sf o r mo fr e v e r s i b l el o g i c ，t h em u l t i - o b j e c t i v ee v o l u t i o n a r yd e s i g nm e t h o di s s t u d i e d o n e - b i tf u l l a d d e ra n d4 * 4r e v e r s i b l em u l t i p l i e ro p t i m a ld e s i g nh a v eb e e nc o m p l e t e d t h e f u n c t i o n s ，t h en u m b e ro fq u a n t u mg a t e s ，g a r b a g e ，a n dq u a n t u mc o s to fc i r c u i t sa e v o l v e da tt h e s a m t i m ea n dt h eg o o do p t i m i z a t i o nr e s u l t sa r eg a i n e d ( 4 ) f o ro p t i m i z a t i o no fc o m p l e xt 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 。m a t r i xc o d i n gm e t h o di s p r o p o s e d 8 * 8r e v e r s i b l em u l 卸l i e ri sd e s i g n e da n dt h ea n a l y s i so fe x p e r i m e n t a lr e s u l t sv e r i f yt h e s u p e r i o r i t yo ft h ei m p r o v e de n c o d i n gm e t h o dw h i c hi sa d o p t e dt oe v o l v et h ec o m p l e x i t yq u a n t u m r e v e r s i b l el o g i cc i r c u i t s k e y w o r d s ：q u a n t u mc i r c u i t ；r e v e r s i b l el o g i c ；o p t i m a ld e s i g n ；g e n e t i ca l g o r i t h m ；l o w p o w e r i n t e g r a t e dc i r c u i t s ；t s gg a t e ；r e v e r s i b l em u l t i p l i e r ， 、 南京航空航天大学硕士学位论文 目录 第一章绪论1 1 1 课题的研究背景与研究意义l 1 1 1 课题的研究背景1 1 1 2 课题的研究意义2 1 2 量子可逆逻辑电路的研究现状及发展趋势3 1 2 1 量子可逆逻辑电路的国内外研究现状分析3 1 2 2 量子可逆逻辑电路研究存在问题与发展方向5 1 3 本文的研究内容和论文结构5 第二章量子可逆逻辑电路基础知识及综合方法分析7 2 1 量子可逆逻辑电路的基础知识7 2 1 1 量子门介绍7 2 1 2 量子门及量子电路的基本定理。1 3 2 2 常用量子可逆逻辑电路主要综合方法分析1 5 2 2 1 基丁变换法的合成。1 5 2 2 2 逻辑符号综合法1 7 2 2 3 模板法一1 8 2 2 4 综合方法对比。1 9 2 3 本章小结1 9 第三章量子可逆逻辑基础门电路进化设计方法研究一2 0 3 1 量子可逆逻辑电路设计的数学模型与设计规则2 1 3 2 遗传算法描述。2 1 3 3 量子可逆逻辑基础门电路进化方法设计2 3 3 4 设计实例及仿真实验结果分析2 7 3 4 1 实例设计2 7 3 4 2 仿真结果分析2 9 3 5 本章小结3 0 第四章量子可逆逻辑电路进化设计方法研究3 1 4 1 量子可逆逻辑电路编码方法及遗传操作3 1 4 1 - 1 改进的编解码方法3 l 量子可逆逻辑电路进化设计研究 4 1 2 种群初始化3 2 4 1 3 遗传操作3 2 4 2 适应度函数设计3 7 4 3 设计实例及仿真实验结果分析3 8 4 3 1 可逆全加器3 8 4 3 24 * 4 可逆乘法器4 3 4 3 本章小结一4 9 笫五章复杂可逆逻辑电路进化设计初步研究5 0 5 1 基于矩阵编码的复杂量子可逆逻辑电路进化设计方法一5 0 5 1 1 复杂量子可逆逻辑电路编码方法及遗传操作。5 0 5 1 2 适应度函数设计5 6 5 2 设计实例及仿真实验结果分析5 7 5 3 本章小结6 7 第六章总结与展望一6 8 6 1 课题研究工作总结。6 8 6 2 课题展望一6 9 参考文献7 0 致谢7 5 在学期间的研究成果及发表的学术论文7 6 ， - 、 南京航空航天大学硕士学位论文 图表清单 图2 1 单比特量子门电路7 图2 2 量子比特的b l o c h 球面表示8 图2 3z c n o t 门线路表示9 图2 4 受控u 门1 0 图2 5 量子异或门l o 图2 6 量子a n d 门1 1 图2 7 量子o r 门1 1 图2 8 交换一对比特的量子电路。l l 图2 9 异或x o r 门1 1 图2 1 0t o f f o l i 门线路表示和矩阵表示1 2 图2 11t o f f o l if - 丁1 2 图2 1 2f r e d k i n 门示意图1 3 图2 1 3 三变量的量子可逆逻辑电路一1 4 图2 1 4 实现置换仃的量子线路示意图1 6 图3 1 集合示意图2 0 图3 2 搜索方法分类图2 1 图3 3 遗传算法原理图2 2 图3 4 遗传算法流程图2 3 图3 5 三输入完整门库2 4 图3 6 交叉操作示意图2 6 图3 7 变异操作示意图2 6 图3 8 四输入量子门库2 8 图3 9 四输入电路进化过程中适应度变化曲线2 9 图4 11 位可逆全加器3 2 图4 2 染色体编码3 2 图4 3 种群初始化3 3 图4 4 交叉前的两个染色体3 3 图4 5 交叉后的两个染色体3 4 图4 6 变异量子门连线示意图3 5 v 量子可逆逻辑电路进化设计研究 图4 7 变异量子门功能示意图3 5 图4 8 变异量子门的位置示意图3 6 图4 9 变异有无量子门示意图3 6 图4 1 0l 位可逆全加器电路3 8 图4 1 1f g 量子门3 9 图4 1 2t g 量子门3 9 图4 1 3n g 量子门3 9 图4 1 41 位可逆全加器遗传进化结果4 1 图4 1 51 位可逆全加器进化目标参数变化曲线图4 3 图4 1 64 * 4 可逆乘法器4 4 图4 1 7m t s gf - 】4 4 图4 1 84 * 4 可逆乘法器电路模块划分4 5 图4 1 94 * 4 可逆乘法器遗传进化结果4 7 图4 2 04 * 4 可逆乘法器进化目标参数变化曲线图4 9 图5 1 变异量子门连线示意图5 3 图5 2 变异量子门功能示意图5 4 图5 3 变异量子门位置示意图：5 5 图5 4 变异有无量子门示意图5 6 图5 58 * 8 可逆乘法器5 8 图5 68 * 8 可逆乘法器功能模块划分6 0 图5 78 * 8 可逆乘法器遗传进化结果6 4 图5 88 * 8 可逆乘法器进化目标参数变化曲线图6 6 表2 1 常用的单比特量子门及其符号表示8 表2 2 量子异或门真值表1 0 表2 - 3t o f f o l i 门真值表1 3 表2 4f r e d k i n 门真值表1 4 表2 5 三变量量子可逆逻辑电路的真值表1 5 表2 6 置换仃的逻辑函数真值表1 6 表3 1 四输入量子可逆逻辑电路实验参数表2 9 表4 1 常用量子门的量子代价3 7 表4 2f g 门真值表3 9 表4 3t g 门真值表3 9 表4 4n g 真值表3 9 -1、 l 、 r 、 南京航空航天大学硕士学位论文 表4 51 位全加器真值表4 0 表4 61 位可逆全加器实验参数表4 0 表4 71 位可逆全加器优化目标参数对比4 2 表4 84 * 4 乘法器设计方法4 3 表4 94 * 4 可逆乘法器实验参数表4 6 表4 1 04 * 4 可逆乘法器优化目标参数对比4 8 表5 18 * 8 可逆乘法器设计方法。5 8 表5 28 * 8 可逆乘法器实验参数表一6 0 表5 3 位串编码和矩阵编码的遗传进化结果对比6 5 表5 4 进化的8 * 8 可逆乘法器目标优化参数对比6 5 量子可逆逻辑电路进化设计研究 、，l l l 简称 f g g a p n g p p r m t g t s g 注释表 英文全称 f e y m a ng a t e g e n e t i ca l g o r i t h m i n t e g e rl i n e a rp r o g r a m n e w g a t e 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 t o 蜀f o hg a t e t s g a t e 中文全称 f e y m a n 门 遗传算法 整数线性规划 n e w 门 正极性r m 展开式 t o f f o l i 门 t s 门 一 ， 1 ， 号膨 1 2 3 4 5 6 7 - 、 吖 乞 南京航空航天大学硕士学位论文 第一章绪论弟一早珀t 匕 1 1 课题的研究背景与研究意义 1 1 1 课题的研究背景 随着集成电路规模的增大和集成度的提升，集成电路的能耗问题日益突出，如何降低集成 电路的能量消耗是集成电路规模能否扩大的决定因素之一。电路中每一个晶体管由导通状态切 换成关断状态时，其电路上存储的电荷将经由地线释放，这部分电荷释放时将电能转变为热能， 这便是无用的能耗。近年来，人们开始采用降低工作电压、实行电源管理等措施来节能。这些 措施虽然有效而且也正在得到，“泛应用，但总受到某种限制，如降低工作电压，当电压降低到 难以区分有用信号与噪音信号时，就失去了意义。据计算，当电压降n o 5 - - 1 2 v 时将发生这种 情况。 同时，随着集成电路的集成度越来越高，电子器件内部的量子效应越来越明显，制造计算 机的传统方法在提高集成度上越来越力不从心：集成电路能耗导致计算机芯片发热，也影响了 芯片集成度的进一步提高。为了减少计算机的能量损耗，首先就要弄清在现有的微处理器上， 能量是在哪里被消耗掉的，哪些能量消耗又是不必要的，是能够节省而且应该节省下来的。微 处理器是由许多逻辑门组成的，而它们又是以晶体管开关作为基础的。提高工作速度将增加耗 电，因为微处理器的每一次操作都要使一定数目的晶体管进行由导通到关断的切换，而每次切 换都要耗电，单位时间内切换次数多耗电自然也就多。追求速度还在另一方面耗电，因为要求 晶体管切换更快就需要有更多的电荷使晶体管尽可能快地饱和，这样，每次切换时就会有更多 的电荷使电能变为热能。一般来说，要使芯片的速度提高一倍，耗电就不止增加一倍。另一方 面，小型化对减小芯片耗电倒有好处。因为晶体管越小，用以使其饱和所需的电荷也越少，因 此每一个晶体管耗电也就减少了。这意味着随着集成度的提高耗电不会与晶体管数目成比例地 增加。 因此，早在几年前，人们便在探求更为彻底的新节能方法。其中一种有效的方法是从如何 减少无用的能量损耗这方面着手来减少电路的能槲1 1 1 2 1 3 1 。 r l a n d a u e 最早考察了能耗的来源 4 1 ，指出能耗产生于计算过程中的不可逆操作。例如，对 两比特的异或操作，因为只有一比特的输出，这一过程损失了一个自由度，因此是不可逆的， 按照热力学理论，必然会产生一定的热量。事实上，只要对异或门的操作进行简单改进，即保 留一个无用的比特，该操作就变为可逆。因此消除能耗的关键是将不可逆操作改造为可逆操作。 c h b e n n e t t 后来更严格地证明了只要组成可逆的门网络【5 】，做到能量零损耗是可能的。经典计 算机实际上就是一个通用图灵机，通用图灵机是计算机的抽象数学模型，图灵机的模型是不可 量子可逆逻辑电路进化设计研究 逆的。但b e n n e t t 证明了对所有不可逆的通用图灵机，都可以找到一个对应的可逆图灵机，使得 两者具有完全相同的计算能力和计算效率。因为计算机中的每步操作都可以改造为可逆操作， 在量子力学中，它就可以用一个幺正变换来代表，p b e n i o f 嘬早用量子力学来描述可逆计算机 p 】。证明通过可逆设计的方法可以实现量子电路的逻辑综合。1 9 8 5 年，d d e u t s c h 率先提出量子 图灵机概念【7 】，量子计算机可以等效为一个量子图灵机，理论上已证明，量子图灵机可以等价 为一个量子逻辑电路，因此可以通过若干量子逻辑门组合成逻辑电路来构成量子计算机。随后 的二十年里，有关量子计算机的基础研究在理论上有长足的发展。 迄今为止，虽然世界上还没有真正意义的量子计算机。但是，由于其广阔的应用前景，世 界主要经济发达国家都在制定战略性规划，各国有代表性的实验室正以巨大的热情投入人力物 力财力，期望在新一代计算机的科学与技术上占据领导地位。正因为实现量子计算机的技术困 难重重，而量子计算机的实现必将为信息科学与通信技术带来革命性的突破，所以量子可逆逻辑 电路的设计、优化与测试等方法的研究作为量子信息与量子计算理论的基础研究越来越受到理 论研究者与应用研究者的关注。 1 1 2 课题的研究意义 量子计算中，信息的基本操作元件是量子逻辑门，量子比特是信息的载体，量子比特的信 息经量子逻辑门操作处理后，最后得到计算结果。所有的量子逻辑门都是可逆操作，量子逻辑 门不带有信息的擦除操作，在理论上也就不存在热耗散的现象，从而杜绝了经典计算机从根本 上无法解决的热耗散严重影响器件正常功能的问题。不导致信息丢失的设计称为可逆的。因此， 可逆性将成为未来电路设计的基本特性。 在未来诸多具有可逆性质的研究和应用中，量子由于可以实现可逆操作，被广泛的应用在 可逆电路的研究中，近期可逆逻辑电路的研究大多都是基于量子的。可逆逻辑不仅解决了计算 机的能耗问题，而且为其他领域的能耗问题开辟了一个新的解决思路，可逆逻辑电路是量子计 算科学、低能耗c m o s 以及纳米技术研究的基础。传统不可逆电路由于信息的擦除而导致了能 量的消耗，而在理想的物理环境中，可逆计算不存在能耗问题。在加密系统、数字信号处理及 通信系统领域的应用中，数据转换过程不存在任何对原始信息的擦除，因此系统采用可逆逻辑 电路实现是非常适合的。另外，可逆电路还可以通过增加有限的位，实现传统的不可逆计算。 由于可逆电路与传统不可逆电路相比有许多优点，因此具有重要的研究意义。 为了得到代价最小的电路，一个良好的合成方法以及优化技术是必不可少的。特别是高效 的电路优化技术能够弥补电路设计方法的不足，因此，系统而深入的研究量子可逆电路的优化 方法是很有必要的。量子可逆电路的优化目标是保持电路函数功能不变条件下，尽可能地减少 电路逻辑门数量、垃圾位等。 2 一 ， b 气 k 在可逆逻辑电路研究的初期，研究者提出了多种可逆的量子逻辑门，关于这些量子逻辑门 已经有诸多相关研究，且大部分文献的作者都带有物理、数学、逻辑或计算机科学理论的研究 背景。随着设计的逻辑门的增多，可逆逻辑研究也不仅仅局限于逻辑门的设计，可逆逻辑电路 的设计开始受到越来越多的关注，但是人工设计可逆逻辑电路很复杂，难以设计大规模的电路。 因此，许多研究者对量子可逆逻辑综合也逐渐重视起来，美国、德国、加拿大、荷兰、韩国等 国家的一些组织和个人，对该研究予以高度重视。量子可逆逻辑的研究涉及到数学、物理学、 信息科学等基础学科，并在一些现代科学如集成电路技术、光电技术、纳米技术和热力学等领 域中也有着重要应用。 可逆逻辑电路主要研究内容有： ( 1 ) 可逆逻辑电路的综合方法研究 量子电路可逆逻辑综合，主要研究在给定的量子门和量子电路的约束条件及限制下，使量 子可逆逻辑电路的代价最小；研究接近最优化量子代价或为非最优量子代价提速的量子电路可 逆逻辑综合理论和方法；研究接近最优化的可逆逻辑电路生成方法。量子电路可逆逻辑综合包 含合成和优化两个方面，量子可逆电路的合成是指，通过给定一个可逆逻辑函数的输入、输出 值，计算机能够通过先观的算法得到实现该函数功能的可逆逻辑电路。然而，各种合成法得到 的量子可逆逻辑电路往往不是电路代价最小的最优电路，一般意义上，量子可逆电路的代价是 指量子电路中基本量子逻辑门的数量。为了得到最优电路，相应地，出现了量子可逆逻辑电路 的优化技术，其思想是能够在不改变可逆电路函数功能的条件下，对电路进行重组、替换，达 到减少电路逻辑门数量的目的，从而降低了量子可逆电路的代价。现在也有些方法，将合成与 优化这两个过程同时进行，而且已成为综合方法的主澍引。 目前对可逆逻辑电路的研究主要集中于此方面。可逆逻辑电路的合成方法有若干种，其关 键是如何使用指定的可逆逻辑门，以较高的效率自动生成量子代价较小的可逆逻辑电路。应用 不同的实现技术，通常量子可逆门的代价是不相同的。为此人们提出了若干可逆逻辑电路综合 的算法。 穷举法【9 】【1 0 】【1 1 】，其思想是对于给定的函数功能以及可供选择的逻辑门类型，按照电路规模 的扩大，依次生成所有可能的电路，直至找到实现该函数功能的电路为止。由于穷举法是根据 电路长度从小到大寻找电路的，也就是一定可以寻找到最优电路，但是也是最耗时间的方法。 基于代数的方法，该方法是利用代数的方法对电路进行转化、化简等一系列操作，以得到 简化的量子可逆逻辑电路。如r e e d m u l l e r 展开式法坨】【”】，该方法根据量子电路的功能构造 r e e d m u l l e r 展开式，并对展开式进行化简得到可逆逻辑电路。 3 量子可逆逻辑电路进化设计研究 基于模板的方法，该方法根据量子电路之间存在等效关系的特点，使用局部量子电路替换 的方式对量子电路进行优化。 基于真值表的方法，根据给定的输入、输出值，通过电路的变化规则，选择相应的逻辑门， 一步一步将输出值变化为输入值，直至输出值和输入值一致为止。 这些综合方法中，穷举法一定可以找到最优解，但是其搜索空间大，搜索效率低，不适用 于大规模的电路；基于代数的方法缺乏通用性，而且生成的电路通常不是全局最优；基于模板 的方法需要大量的模板，找到的往往不是最优解；基于真值表的方法随着电路输入输出位的增 加计算非常繁琐，不具有通用性，因此该方法只能适用于小规模的量子电路，对于中大规模电 路则不适用。 ( 2 ) 可逆逻辑电路的错误检测及定位 和传统不可逆电路一样，为了确保可逆电路的可靠性与止确性，电路的错误检测必不可少。 不同的量子可逆电路实现技术可能导致不同的错误类型。现在已有的错误模型有永为错误模型， 门丢失错误模型，结点丢失和结点多余错误模型等。 永为错误模型是经典电路中最典型的错误模型，它表现为电路中的一条线或几条线在某一 层上发生错误而使其永远为l 或永远为0 。k n p a t e l 等对这种错误模型进行了详细的分析【1 4 l ，并 使用i l p 方法得到了这类错误的完备的检测集。 结点错误模型”】，可逆电路单个门上除了可能发生永为错误外，还可能发生结点错误、控 制点丢失错误以及更一般的门错误。可逆电路的结点错误分为丢失结点错误和多余结点错误。 多余门错误模型，相关研究给出了此错误模型下的诸多性质，并结合这些性质提出了多余 门错误模型检测集完备性的判定定理，得到了3 3 个可逆逻辑电路的单个多余门错误的完备检测 集。 适应树的算法来定位固定故障模型错误【1 6 】，该算法首先生成错误表，然后根据错误表产生 适应树，在真值表和错误表基础上生成错误定位树1 7 1 ，通过分析可逆逻辑电路发生门失效错误 时对电路的影响，给出了一种定位门失效模型错误的方法，其生成的错误定位树中根据输入向 量的不同输出能把当前错误集划分成多个小的错误集，使得树的高度更小，定位错误更快。 上述错误检测方法都是分别针对不同的错误模型提出的，一种方法并不能检测电路中所有 可能的错误。当检测到电路中存在错误时，一般还需要找出出错点并纠正。因此一般通用性不 强。 ( 3 ) 可逆逻辑电路的应用 和可逆逻辑电路的综合方法研究不同，这一方面的研究主要集中于具有某种具体功能的可 逆逻辑电路的生成，而前者是生成所有可能的可逆逻辑电路。目前设计的具体电路主要有加法 器【1 8 】【1 9 】【2 0 1 、乘法器【2 1 】【2 2 l 、减法器【2 3 1 、比较器【2 4 1 等。 4 南京航空航天大学硕+ 学位论文 加法器的研究主要集中在4 位可逆并行加法器【2 5 1 ，4 位可逆b c d 加法器【2 叼等，电路规模均较 小；乘法器有4 * 4 可逆阵列乘法器；减法器有l 位可逆跳跃进位b c d 减法器等；比较器有疗位四进 制等于比较器、刀位四进n d 于比较器等，这些电路规模较小，功能较简单。因此，如何生成较 大规模的功能电路是今后的研究热点之一。 1 2 2 量子可逆逻辑电路研究存在问题与发展方向 ( 1 ) 可逆逻辑电路研究难点和存在问题 1 ) 可逆逻辑电路的综合方面 现有的综合方法通常缺乏普遍适用性口7 删，且通常生成的电路不能达到最优。怎样找到新 的综合方法，能以较小的平均空间、时间复杂度快速生成全部最优的可逆逻辑电路是研究的难 点。 同时，在可逆逻辑电路的优化中存在着适用的可逆逻辑门网络的规模太小、优化花费代价 高、优化过程中时空复杂度高以及测试用例少等一系列问题，不能满足未来量子计算和量子信 息以及其他领域对量子可逆电路逻辑门优化的要求。 2 ) 可逆逻辑电路的错误检测与定位p 1 。3 1 对于新生的可逆逻辑电路，不可避免的存在许多未解决的问题。错误检测与定位这一方面 的难点在于探索可逆逻辑电路可能存在的一些错误，建立错误模型，并在此基础上能建立普遍 适用的错误定位方法。 ( 2 ) 可逆逻辑电路研究发展方向 可逆逻辑电路是一个新兴的研究领域，它是量子计算和量子信息技术研究的重要组成部分， 并在低功耗电路设计1 3 4 】【3 5 1 、信息安全、纳米技术等其它一些现代科学领域有着重要应用。由于 它潜在的巨大实际应用价值和重大的科学理论意义，正引起越来越多的关注。对可逆逻辑电路 的研究主要集中在具体可逆电路设计这方面。 对于具体可逆逻辑电路的设计主要集中于研究生成花费较低的具体功能电路，比如作为电 路构成基础的各种类型的加法器以及在此基础上构建减法器、乘法器等。在这个方面，不断有 新的可逆逻辑门被用到可逆逻辑电路中来。因此，这个方向的发展主要是设计为功能电路所用 的新的可逆逻辑门，并在此基础上结合已有的可逆逻辑门来构造花费更小的功能电路。 1 3 本文的研究内容和论文结构 本课题主要是研究了量子可逆逻辑电路的进化设计，阐述了量子电路的进化原理并设计实 例验证了方法的可行性和优越性。 第一章是绪论。主要介绍了量子可逆电路的研究背景、研究现状、存在的难点及热点、量 子可逆逻辑电路的发展方向等内容，从总体上阐述了量子可逆逻辑研究的概况。最后给出了本 5 量子可逆逻辑电路进化设计研究 文的主要研究内容和结构安排。 第二章是量子可逆逻辑电路理论基础。主要介绍了基本的量子门，分析说明了基本的量子 电路，阐述了量子可逆逻辑电路的基本定理，并介绍了量子可逆逻辑电路的各种综合方法，对 这些方法进行了分析对比，说明了各综合方法的优缺点。 第三章是基于基础量子逻辑门的可逆逻辑电路进化设计方法研究。阐述了可逆逻辑电路设 计的数学模型和遗传进化思想，设计二进制编码方法对电路进行编码，在编码中需要建立量子 门库。选取四输入可逆逻辑电路作为实验用例验证了该方法进化较少输入的可逆逻辑电路的高 效性。 第四章是基于常用量子门的可逆逻辑电路进化设计方法研究。设计了新的可逆逻辑电路编 码方法，并采用了多目标进化的方法。在进化过程中，对可逆逻辑电路进行编解码和遗传操作， 包括选择、交叉、变异，并对l 位全加器和4 * 4 可逆逻辑乘法器进行了进化，取得了很好的优 化效果。 第五章是复杂量子可逆逻辑电路进化设计的初步研究。针对复杂量子可逆逻辑电路的特点， 对设计方法进行了改进，并设计了8 * 8 可逆乘法器，采用改进后的进化方法对此电路进行了优 化，验证了改进后的进化方法对复杂电路的进化有着不可取代的优越性。 第六章是总结与展望。总结了本课题的前期工作，并提出了课题研究的不足和今后研究的 方向，对课题的研究前景进行了展望。 6 南京航空航天大学硕士学位论文 第二章量子可逆逻辑电路基础知识及综合方法分析 2 1 量子可逆逻辑电路的基t i $ 矢1 1 识 2 1 1 量子门介绍 在经典计算机中，二二进制信息以比特( b i t ) 形式存储p 6 1 ，物理上可以是在晶体管电子电路中 符号i 表示量子比特而不是经典比特。如果以i 。 和l 分别表示向量( 吉) ( 詈) ，那么普 = = 翟= 荔 仁t ， 一般6 = 俨产0 ，所以【o 一一1 1 ，己“l = l o 。符号表示周期因子不影响逻辑运算。单比 j a 一卜一一u o l a 图2 1 单比特量子门电路 图中单量子比特( 如自旋1 2 的粒子) 的初始态可表述为i a ，它通过电路后状态转变为 u a i a 。 另一重要的单比特门是u ，u 彰将自旋向下粒子映射为自旋向上和自旋向上的叠加： u 形i o 2 ( 1 0 + 1 1 ) ( 2 2 ) 7 量子可逆逻辑电路进化设计研究 考虑一串k 个自旋l 2 的粒子的初始态是自旋向下，如果这个量子门独立地应用于每个粒子， 可以得到长度为k 的每个可能比特的叠加 p 彪驴 ( 2 3 ) 其中q = 2 k 。计算机现在可工作于从0 至2 k _ l 的整数a 的叠加态上。假设可构造一种运算，该运算利 用函数和) 可将一对比特l a ；o 映射为i 口；( 口) ，那么进行如此叠加状态的一元运算将对于各种输 入a 并行地计拿歌口) 。 可以用更直观的方式来看这种形式，数秒和够定义了三维单位球面上的一个点，如图2 2 所示，这个球面通常被称为b l o e h 球面。不过这种直观的想象是有局限的，因为尚不知道如何 将b l o c h 球面简单地推广到多量子比特的情况。 1 0 y | l 1 图2 2 量子比特的b l o c h 球面表示 表2 1 所示是一些常用的单量子门及其符号表示。 表2 1 常用的单比特量子门