量子可逆电路综合的启发式快速匹配算法  

Heuristic fast-matching algorithm for synthesis of quantum reversible logic circuits

作　　者：王冬[1,2] 陈汉武[1] 安博[1] 杨忠明[1] 

机构地区：[1]东南大学计算机科学与工程学院,南京210096 [2]河南大学计算中心,开封415002

出　　处：《东南大学学报（自然科学版）》2009年第5期900-903,共4页Journal of Southeast University：Natural Science Edition

基　　金：国家自然科学基金资助项目(60572071;60873101);江苏省自然科学基金资助项目(BM2006504;BK2007104)

摘　　要：提出了基于Reed-Muller展开式,使用CNT量子门库,以量子门表达式为启发式规则进行前向模式匹配的量子可逆逻辑电路快速综合算法.与通常所用的穷尽搜索算法相比,该算法利用量子门表达式作为启发式规则进行匹配代换,避免盲目匹配,有效降低了匹配复杂度,减少匹配代换的数量.同时该算法不会出现穷尽搜索中因不能找到有效解而进行回溯的现象,能以较小的时间空间复杂度生成最优或近似最优的量子可逆电路,特别在多量子可逆逻辑电路综合上,能够表现出更好的性能.Heuristic fast-matching algorithm for quantum reversible logic circuits synthesis is presented. The algorithm is based on Reed-Muller expansion, uses CNT quantum gates library, takes the quantum gate equations as the heuristic rules and adopts forward-matching method to construct quantum circuits. Compared with current exhaustive search, the proposed algorithm uses the quantum gate equations as the heuristic rules which can avoid blind matching and decrease the matching complexity. It is simple and can effectively build optimal or near-optimal circuits with lower cost. Moreover it can perform well in the multi-quantum reversible logic circuits synthesis.

关 键 词：量子可逆逻辑电路 Reed-Muller展开式 CNOT门 Toffoli门 

分 类 号：TP387[自动化与计算机技术—计算机系统结构] TN911.73[自动化与计算机技术—计算机科学与技术]