资源描述:
《量子可逆逻辑电路综合的快速算法研究》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、量子可逆逻辑电路综合的快速算法研究摘要可逆逻辑有许多应用,尤其在量子计算领域,量子可逆逻辑电路是构建量子计算机的基本单元,量子可逆逻辑电路综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.本文结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的算法,自动构造正极性Reed-Muller展开式(RM),在生成量子可逆逻辑电路的解空间树上,采用总体层次遍历,局部深度搜索,借鉴模板优化技术,构造限界函数快速剪去无解或非最优解的分枝,优先探测RM中的因子,以极高的效率生成最优电路.以国际公认的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远
2、远超过同类算法.关键词量子电路优化;ReedMuller;可逆逻辑电路;Toffoli门;量子计算AbstractReversiblelogicfindsmanyapplications,especiallyintheareaofquantumcomputing.Quantumreversiblelogiccircuitsarebasicelementsinquantumcomputerconstruction.Synthesisofquantumreversiblelogiccircuitsmeanstoautomaticallyconstructdesiredqu
3、antumreversiblelogiccircuitwithminimalquantumcost.WeabsorbdifferentideasofreversiblelogiccircuitssynthesisandpresentanovelandefficientalgorithmwhichcanautomaticallyderivethepositivepolarityReed-Mullerexpansion(RM).Weconstructasolutionspacetreetocreatequantumreversiblelogiccircuits.First
4、ly,floortraversalisappliedglobally,anddepth-firstsearchisusedlocally.Secondly,accordingtothetechniqueoftemplateoptimization,weconstructtheboundfunctionwhichcanrapidlyprunethebrancheswithnoornonoptimalresult.Thirdly,factorsofRMarefirstconsidered,thereforethealgorithmcaneffectivelyconstru
5、ctoptimalresultandsavescomputationalcostsignificantly.Judgingbytheinternationallyrecognizedreversiblefunctionsofthreevariables;ouralgorithmnotonlysynthesizesalloptimalreversiblefunctions,butalsorunsextremelyfasterthanothersofthesamekind.Keywordsquantumcircuitoptimization;ReedMuller;reve
6、rsiblelogiccircuit;Toffoligate;quantumcomputing1引言量子计算机可等效一个量子图灵机.理论上已证明,量子图灵机可等价一个量子逻辑电路.量子逻辑门的组合与级联是组成量子计算机的基本元素.所有量子逻辑门均可表示成复变空间酋矩阵,其输入与输出的比特数相等,也称可逆算子.量子逻辑门对输入比特进行确定的酋变换,得到输出比特.Deutsch[1]最早考虑用量子逻辑门构造量子计算机的问题,他发现几乎所有的三比特量子逻辑门都是通用逻辑门.通用逻辑门的含义是指,通过该逻辑门的级联,能够以任意精度逼近任意一个幺正操作,幺正操作对应操作的数理解
7、析,逻辑门的级联将生成物理上的量子逻辑电路.Deutsch的结果随后得到发展,最后Deutsch等[2]和Lloyd[3]各自独立证明了几乎所有的二比特量子逻辑门都是通用的,这里“几乎”是指,二比特通用量子逻辑门的集合是所有二比特逻辑门的集合的一个稠密子集.实验上通常用一些具体的量子逻辑门构造量子计算机.Barenco[2]等人证明,一个二比特的异或门与对一比特进行任意操作的门可构成一个通用量子门集.相对而言,单比特逻辑门在实验上比较容易实现,现在多数实验方案都集中于制造量子异或门.量子异或门和经典异或门非常相似,它有两个输入比待:控制比特和受控比特