扩展Toffoli门及其在多输出电路设计中的应用张小颖I,王伶俐I,吴文晋2,汪鹏君】ZHANGXiao-ying*,WANGLing-li\WUWen-jin2,WANGPeng-junb21.复旦大学专用集成电路与系统国家重点实验室，上海2012032.宁波人学电路与系统研究所，浙江宁波3152111.StateKeyl^boratoiyofASIC&System,KudanLniversity,Shanghai201203,China2」nstituteofCircuitsandSystems,NingboUniversity,Ningbo,Zhejiang315211,ChinaE-mail:llwang@fuclan.edu.cnZHANGXiao-yingtWANGLing-li,WUWen-jin.etal.ExtendedToffoligatesanditsapplicationinmulti-outputlogicfunctions.ComputerEngineeringandApplications.2009,45(2)：88-91.Abstract：ImplemenlingBooleanfunctionsonquantumcircuitsisanessentialaimforthedevelopmentofquantumcomputing.ThispaperintroducesthedefinitionofextendedToffoligatetandproposesanalgorithmofimplementationofmulti-outputquantumBooleanfiinctions.ThisalgorithmconvertstheconventionalSOPcubesofPLA(ProgrammableIx)gicArray)filesintoextendedToffolicubeswiththesamelogicfunction;thereforethefunctioncanbebuiltinextendedTofloligates.ExperimentalresultsofMCNCbenchmarkshowthatexlended-Toflbli-gateimplemenlationofmulti-outputlogicfunctionismoreeffectivethanthePLAimplementalion.Keywords：(fuantumcomputing;extendedToffoligate;AND/XORlogic;ProgrammableLogicAiTay(PLA)摘要：用量子计算电路实现布尔逻辑运算是发展量子计算的一个重要目标。提出了量子扩展Toffoli门，及其在实现多输出逻辑电路中的转换算法。该算法将传统PLA文件的SOP积项转换到实现等价逻辑功能的量子loffoli积项，能够用董子扩展Toffoli门实现。通过MCNC基准电路的测试结果表明，与经典卩1小描述相比，用扩展ToffoliH能够更有效地描述多输出逻辑函数。关键诚：量子计算;扩展Toffoli门；与/异或逻辑;可编程逻辑阵列DOI:10.3778/j.issn.1002-8331.2009.02.025文住编号:1002-8331(2009)02-0088-04文献标识码:A中图分类号:TP301引言随着半导体工艺技术不断逼近其物理极限,基于纳米技术的电路设计需要考虑量子效应。为了解决芯片功耗和计算复杂度问题，量子汁算是近年来国际上的研究热点之一叭量子计算具有不同于经典计算的特殊性质,包括态叠加性、相干性、不可克隆性等。利用右效的量子算法能够实现并行计算現对解决利用传统计算机难以解决的NP-hard问题提供了多项式复杂度算法，如实现大数质冈数分解的Shor算法⑴和进行数据库快速查找的(；rover算法冋。在对量子计算体系的探索过程中，用量了计算电路实现经典的布尔逻辑运算非常重要叫找到用量了计算电路表示经典计算的方法，对未来量子计算机的发展和应用有看巨人的推动作用和深远意义。逻辑函数传统上用与/或/非(AND/OR/NOT)运算来描述,但是也可以用与/异或(AND/XOR)运算來描述。目询学术上已右关于与/或/非和与/异或电路的极性转换和优化算法性量子fJ运算和与/异或运算有着紧密的联系，要用量子门来实现传统逻辑功能，就必须对与/或/非描述进行转换Iwama等卩给出了以CNOTI'J为基础的电路转换规则，但是这种方法会引入附加量子比特，増大电路规模「Younes和Mill"提岀了基fReed-Muller的量了逻辑电路描述，但是他们同样没有给出从经典电路描述到量了•逻辑电路描述的有效算法,并缺乏対多输岀电路的表示。本文通过对基本量子门和布尔代数的研究，根据量子门运算的四性要求(unitarity),定义扩展ToffolifJ——ETOF门，提出一种基于ETOF积项的多输出逻辑函数转换算法,能够有效处理大变量的多输出函数。2扩展Toffoli门2.1基本壮子门在量子计算机中，信息的基本操作单元是量子逻辑门，信息的载体是量子比特(qubit)o与经典信息不同,量子比特能够以叠加态(superposition啲形式存在，任何的一位量子比特均可山一个二维复向昂:空间中的单位向昂:表示:妙〉=alO＞+0l1＞,其中“卜”为Dirac记号,10＞和11＞表示一位昂:子系统的两个基态,«和0是复数,分别表示10＞和11＞的概率幅,加和”分别表基金项忖：国家自然科学基金(the\alionalNaturalScienceFo...