结合因式分解与布尔表达式图的可逆电路综合方法

Reversible Circuit Synthesis Method by Combining Factoring and Boolean Expression Diagram

为降低由布尔表达式图(BED)综合所得可逆电路的成本,提出一种将因式分解与BED表示模型相结合的可逆电路综合方法.给定布尔函数的积之异或和(ESOP)覆盖,首先由ESOP立方体的共享零抑制多输出决策图表示借助代数除法对立方体实施因式分解,并在此基础上构建BED;然后将BED结点映射为可逆门级联.对基准函数的可逆电路综合结果表明,该方法具有较高的时间效率.与现有将有向无环图作为函数表示模型的综合方法相比,该方法在许多情况下能降低综合所得可逆电路的量子成本和量子位数.从平均角度看,与结合变量分组和BED表示模型的综合方法相比,该方法可将量子成本和量子位数分别降低5.01%和5.47%.

In order to reduce the cost of the resulting circuits,a reversible circuit synthesis method by combining factoring and Boolean expression diagram(BED)is proposed.For a given cover representing the exclu-sive-sum-of-products(ESOP)expansion of a Boolean function,cubes in the ESOP expansion represented by shared zero-suppressed multiple-output decision diagrams are first factored by leveraging algebraic division,then a BED is built from the factored ESOP cover and a reversible circuit is synthesized from the BED by mapping a BED node to a cascade of reversible gates.The proposed synthesis method is evaluated using benchmark func-tions.Experimental results show that the proposed synthesis method is time efficient.Compared to the existing reversible circuit synthesis methods using a directed acyclic graph as the representation model for Boolean func-tions,the proposed synthesis method can reduce the quantum cost and the number of qubits of the resulting re-versible circuits in many cases.On average,compared to the synthesis method by combining variables grouping and BED,the proposed synthesis method can reduce the quantum cost and the number of qubits by 5.01%and 5.47%,respectively.