基于二分法量子可逆逻辑电路综合

Qubits Reversible Logic Circuits Synthesis Based on Bisection Method

为了能以较小的代价自动高效地构造量子可逆逻辑电路,提出了一种新颖的量子可逆逻辑电路综合方法.该方法通过线拓扑变换和对换演算,利用递归思想,将n量子电路综合问题转换成单量子电路综合问题,从而完成电路综合,经过局部优化生成最终电路.该算法综合出全部的3变量可逆函数,未优化时平均需6.41个EGT门,优化后平均只需5.22个EGT门;理论分析表明,综合n量子电路最多只需要n2n-1个EGT门.与同类算法相比,综合电路所用可逆门的数量大幅减少.同时该算法还避免了时空复杂度太大的问题,便于经典计算机实现.

In order to efficiently automatically construct quantum reversible logic circuits with low cost, a novel method for quantum circuit＇s synthesis is proposed. Through the line topology transformation and truth table permutation,it converts an n-qubit circuit synthesis problem into single quantum circuit synthesis using traditional recursive thought. Then directly generate relevant cir- cuit. After optimization, the quantum reversible logic circuit is synthesized finally. All 3-qubit reversible logic circuits have been syn- thesized by this method. The average number of EGT gates is only 6.41, and the number is down to 5.22 after optimization. Experi- mental results show that the number of gates to construct reversible logic circuits is less than other methods. For any n-qubit binary logic function,the number of EGT gates is less than n2n- 1.Meanwhile,it voids the exponential nature of the memory or run-time complexity, and is very simple to implement in classical computer.