摘要
可逆逻辑有许多应用,尤其在量子计算领域,量子可逆逻辑电路是构建量子计算机的基本单元,量子可逆逻辑电路综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.文中结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的算法,自动构造正极性Reed-Muller展开式(RM),在生成量子可逆逻辑电路的解空间树上,采用总体层次遍历,局部深度搜索,借鉴模板优化技术,构造限界函数快速剪去无解或非最优解的分枝,优先探测RM中的因子,以极高的效率生成最优电路.以国际公认的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过同类算法.
Reversible logic finds many applications, especially in the area of quantum computing. Quantum reversible logic circuits are basic elements in quantum computer construction. Synthesis of quantum reversible logic circuits means to automatically construct desired quantum reversible logic circuit with minimal quantum cost. The authors absorb different ideas of reversible logic circuits synthesis and present a novel and efficient algorithm which can automatically derive the positive polarity Reed-Muller expansion （RM）. A solution space tree is constructed to create quantum reversible logic circuits. Firstly, floor traversal is applied globally, and depth-first search is used locally. Secondly, according to the technique of template optimization, the bound function is constructed, which can rapidly prune the branches with no or nonoptimal result. Thirdly, factors of RM are first considered, therefore the algorithm can effectively construct optimal result and saves computational cost significantly. Judging by the internationally recognized reversible functions of three variables, the proposed algorithm not only synthesizes all optimal reversible functions, but also runs extremely faster than others of the same kind.
出处
《计算机学报》
EI
CSCD
北大核心
2009年第7期1291-1303,共13页
Chinese Journal of Computers
基金
国家自然科学基金(60572071
60873101)
国家自然科学基金会重大研究计划(90412014)
江苏省自然科学基金(BK2008209
BK2007104)
江苏省高校自然科学研究计划(06KJB520137)资助~~
