基于正反控制模型的可逆逻辑综合管致锦1),2)秦小麟1)施佺2)郑吉平3)1)（南京航空航天大学信息科学与技术学院南京210016）2)（南通大学计算机科学与技术学院南通226019）3)（清华大学计算机科学与技术系北京100084）摘要对一般Toffoli门进行了衍变和推广，给出了一个正反控制可逆级联模型（PNCRC），该模型拥有五种基本线型，并能正反控制目标位的输出。基于该模型给出了相应的可逆综合算法。对输入数不大于16的NCMCBenchmark函数进行测试并与已有的可逆综合方法比较，结果表明，利用该模型进行的可逆综合，垃圾信息数和可逆门数的优化效果都具有一定程度的改善。关键词可逆逻辑；可逆门；垃圾信息；正反控制；可逆网络TP302ReversibleLogicSynthesiswithPositive/NegativeControlModelGUANZhi-激n1),2)QINXiao-Lin1)SHIQuan2)ZHENG激-Ping3)1)(CollegeofInformationScienceandTechnology,Nan激ngUniversityofAeronauticsandAstronautics,Nan激ng210016)2)(CollegeofComputerScienceandTechnology,NantongUniversity,Nantong226019)3)(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Bei激ng100084)AbstractBasedontraditionalToffoligate,anewreversiblenetworkcascademodelPNCRCwasproposed.Themodelconsistsoffiveline-styles,anditabletocontroloutputoftargetbitswithpositive/negativewayeffectively.Areversiblesynthesisalgorithmcorrespondingtotheproposedmodelisalsodesignedinthispaperparedtothepreviouslyreportedresults,someexperimentsonNCMCBenchmarkfunctions(lessthanorequal16variables)showthatPNCRCdecreasethenumberofgarbageoutputandnumberofreversiblegatesasawhole.Keywordsreversiblelogic;quantumgate;garbage;positive/negativecontrol;reversiblenetwork1引言可逆逻辑综合是一个新兴的研究领域，它是量子计算和量子信息技术研究的重要组成部分[1]，并在低功耗电路设计、信息安全、纳米技术等其它一些现代科学领域有着重要应用[2-4]。由于它潜在的巨大实际应用价值和重大的科学理论意义，正引起越来越多的关注。可逆逻辑综合，就是用给定的可逆门和可逆网络的约束条件及限制等，实现所需要的可逆逻辑网络，并使得代价尽可能小。可逆逻辑综合使用的基本可逆逻辑门与经典的非可逆逻辑综合使用的逻辑3本课题得到国家自然科学基金（60673127）、国家高技术研究发展计划（863计划）项目（863计划，（2007AA01Z404）、江苏省高校自然科学基金（05KJB520107）资助。管致锦，男，1962年生，博士研究生，教授，主要研究方向为可逆计算、信息安全和逻辑综合．Email：guan_zj@nuaa.edu．秦小麟，男，1953年生，教授，博士生导师,主要研究方向为数据库与数据挖掘技术、空间信息处理、信息安全技术。施佺,男,1973年生,硕士,副教授,研究方向为网络数据库、软件工程。郑吉平，男，1979年生，博士，助理研究员，主要研究方向为场境感知的智能数据管理、数据库安全。门有着根本的不同。可逆逻辑网络为输入数与输出数相等，并且输入向量与输出向量是一一映射的网络。因此，输入向量的状态可以唯一地被输出向量重构。通过函数的方式描述即为：如果函数的每一个输入向量唯一地映射一个输出向量，则称该函数是可逆的。一个n变量的可逆函数也可以定义为整数集自身的映射。一个不可逆逻辑函数总可以通过变换找到它的可逆函数，一般地，会因此产生相应的垃圾信息。在可逆逻辑综合的研究中，一方面要找到可逆网络的实现方法，另一方面要考虑实现可逆网络过程中尽可能花费较低的代价。实现可逆逻辑网络的每一种技术，都需要有一个合理的代价。可逆门的数量和垃圾信息输出的数量是影响可逆逻辑综合代价的重要因素，也是衡量可逆逻辑综合过程好坏的主要依据。在很多技术中只要增加一个可逆门或无用输出信息位可能给网络的实现带来昂贵的代价，甚至不可能实现。所以，可逆网络代价问题在量子计算等领域的研究中具有重要意义和实际应用价值。龙桂鲁等人提出了一个初始化量子寄存器方案，该方案在没有引入附加量子位的情况下，只需要O(Nn2)标准的1位和2位可逆门就能...
