资源描述：
《基于reed_muller量子可逆逻辑电路的综合快速算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第9卷第4期扬州大学学报(自然科学版)Vol.9No.42006年11月JournalofYangzhouUniversity(NaturalScienceEdition)Nov.2006基于Reed-Muller量子可逆逻辑电路的综合快速算法1,232李志强,陈汉武(1.扬州大学信息工程学院,江苏扬州225009;2.东南大学计算机科学与工程学院,南京210096)摘 要:结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的算法,自动构造正极性Reed2Muller展开式(RM),在生成量子可逆逻辑电路的解空间树上,
2、采用总体层次遍历,局部深度搜索,借鉴模板优化技术,构造限界函数快速删除无解或非最优解的分枝,优先探测RM中的因子,以极高的效率生成最优电路.关键词:量子逻辑电路;优化;ReedMuller;可逆逻辑电路;Toffoli门中图分类号:TP387;TN911.73文献标识码:A文章编号:1007824X(2006)04005205量子计算机可等效一个量子图灵机.理论上已证明,量子图灵机可等价一个量子逻辑电路.量子逻辑门的组合与级联是组成量子计算机的基本元素.迄今为止,世界上还没有真正意义上的量子计算机,但世界主要经济发达国
3、家都在制定战略性规划.正因为实现量子计算机技术困难重重,而量子计算机的实现又必将为信息科学与通信技术带来革命性的突破,所以量子可逆逻辑电路的设计、优化与测试等方面的研究越来越受到研究者的关注.20世纪中叶,人们发现计算机芯片的能耗导致芯片发热,限制芯片集成度,影响计算机的运行速度.芯片能耗主要源于计算中的不可逆操作,因此降低能耗的关键是将不可逆操作变为可逆操作.由于量子逻辑门都是可逆的,因此可以用可逆的设计方法综合量子逻辑电路,它不丢失输入信息,不存在热耗散,从理论上解决了芯片的热耗问题.可逆逻辑电路已广泛应用在量子计
4、算、低功耗CMOS电路、纳米技术、光计算、加密技术等许多领域.最近30年,人们提出了多种可[1]逆量子门,如FEYNMAN提出的控制非门(CNOT)、Toffoli门、Fredkin门等.如何使用规定的量子门[2]自动生成量子代价较小的量子电路,SHENDE等人提出了一些可逆逻辑的综合算法以及一种3输入[3]变量的综合方法;IWAMA等人给出了CNOT电路的综合规则,提出CNOT门序列顺序变化的规[4]则,并将实现幺正变换的相邻且相同的门消除,最终实现可逆电路的化简;MILLER等人应用谱函数实现近似最优的可逆电路化简
5、.然而,目前人们还没有找到通用高效的算法,特别对多个输入变量的量子电路,这是量子电路中亟待解决的重要问题之一.由于SHENDE等人提出的穷举算法太慢,[4][5][6]MILLER等人、MASLOV等人给出了几个启发式算法,有些还需要模板优化技术;GUPTA等人给出了基于RM的启发式规则,但这些算法缺乏普遍适用性,且通常生成的电路不能达到最优.为此,本文根据化简RM展开式生成可逆逻辑电路的基本思想,认为层次遍历找到的第一个解必定是最优解,又吸收深度搜索可以复用前面计算的结果,在遍历的过程中借鉴模板优化技术,快速去除无解
6、与非最优解的情况,使用多种编程技术,以较小的平均空间、时间复杂度快速生成全部最优的可逆电路.收稿日期:20060818基金项目:江苏省自然科学基金资助项目(BK2005053,BM2006504);江苏省教育厅自然科学基金资助项目(06KJB520137)3联系人,E2mail:yzqqlzq@163.com©1994-2007ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net第4期李志强等:基于Reed
7、2Muller量子可逆逻辑电路的综合快速算法531 量子可逆逻辑电路的基本概念利用微观粒子状态表示的信息称为量子信息,量子信息的基本单位是量子比特(qubit).与经典信息不同,量子比特能够以叠加态的形式存在,任何量子比特均可由一个二元向量形式表示:ûU〉=22Aû0〉+Bû1〉,其中A和B为复数,满足归一化条件:ûAû+ûBû=1.量子逻辑门是处理量子信息的基本单元,其级联构成量子电路必须是可逆的,即量子信息的动态过程在复向量空间上必须保持正交变换.在量子计算中,一个量子逻辑门对应一个幺正变换,根据输入输出的对数,逻
8、辑门可分为单量子比特门与多量子比特门.定义1Toffoli量子门记为TOF(C;t),其中输入变量集合In={x1,x2,⋯,xn},控制端集合C={xi,xi,⋯,xi},k∈{1,2,⋯,n-1},受控端集合为t={xj},且满足C∩t=§,C∪t
