可逆电路综合与优化的若干研究进展

Research progress in reversible circuit synthesis and optimization

量子计算是一种新型计算模式,遵循量子力学规律对信息进行处理,其应用涵盖密码学、组合优化和量子模拟等多个领域。量子计算强大算力的发挥有赖于量子算法,而量子算法的运行首先需要编译为量子电路。可逆电路是一类重要的量子电路,可逆电路的综合与优化是量子编译的主要研究内容之一。本文对可逆电路综合与优化中的一些重要工作进行总结,首先介绍线性可逆电路的综合与优化,对CNOT门数量与电路深度两个方面优化的结果进行讨论;然后介绍一般性可逆电路的规模和深度优化,对当前算法所能达到的上下界情况进行了分析总结;最后对可逆电路综合与优化的相关延伸拓展进行探讨。

Quantum computing is a new type of computing mode that follows the laws of quantum mechanics to process information,its application covers multiple fields such as cryptography,combinatorial optimization,and quantum simulation.The power of quantum computing relies on quantum algorithms,while the quantum algorithms must first be compiled into quantum circuits to execute.Reversible circuit is an important type of quantum circuits,and the synthesis and optimization of reversible circuits is one of the main research topics in quantum compilation.Some important progress in the synthesis and optimization of reversible circuits are summarized.Firstly,the synthesis and optimization of linear reversible circuits is introduced,and the optimization results in terms of the number of controlled-NOT(CNOT)gates and the depth of circuits are discussed.Then,the size and depth optimization of general reversible circuits are introduced,the upper and lower bounds that the current algorithms can achieve are analyzed.Finally,the extensions of reversible circuit synthesis and optimization are discussed.