一种MCT门量子可逆线路分解与优化方法

A Method for Decomposing and Optimizing MCT Gate Quantum Reversible Circuits

  • 摘要: 为提高可逆线路中MCT门的分解和优化效率,提出了一种MCT门的优化分解方法,根据该方法得出MCT分解模板并验证了正确性。基于该模板给出了相应的分解与优化算法,算法对MCT门分解出的Toffoli线路进行分类,使用优化分解模板将其分解为NCV线路。该算法的时间复杂度为O(m),优于传统算法的复杂度O(m2)。通过对控制位m∈3,10的MCT门与Benchmark可逆线路的实验,验证了该算法优化和分解的有效性。

     

    Abstract: One of the key problems in reversible logic synthesis is optimizing the reversible circuits, and the focus of research is on how to decompose advanced reversible gates into basic reversible gates more efficiently. To improve the decomposition and optimization efficiency of Multiple Control Target (MCT) gates, an optimal decomposition method of MCT gates is proposed in the paper, along with an MCT decomposition template which correctness is verified. Based on this template, the corresponding decomposition and optimization algorithm is given. Using the optimal decomposition template, the algorithm classifies the Toffoli circuits decomposed by MCT gates and decomposes them into NCV circuits. The time complexity of the algorithm is O(m), which is better than O(m2) for the conventional algorithm. Experiments on MCT gates with benchmark reversible circuits for control bits m∈3,10 show the effectiveness of the algorithm’s optimization and decomposition.

     

/

返回文章
返回