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

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

提出了基于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.