基于对换门库的可逆逻辑电路综合算法

李志钢 陈汉武，2 李志强 朱皖宁 刘志昊

(1东南大学计算机科学与工程学院，南京211189)

(2东南大学计算机网络和信息集成教育部重点实验室，南京211189)

(3扬州大学信息工程学院，扬州225009)

量子计算机的概念源于对可逆计算机的研究，而研究可逆计算机是为了克服计算机的能耗问题.经典计算机是由包含连线与逻辑门的电路构建而成的，与此类似，量子计算机是由连线和量子逻辑门级联形成的处理量子信息的量子电路建造的.区别于传统的不可逆电路，可逆电路要求其输入和输出之间存在一一映射，且在电路中不能存在扇入、扇出和反馈，所以可逆电路综合技术比不可逆电路综合技术更为复杂，目前还没有通用高效的算法.近30年来，研究者们已经提出了多种量子门，如CNOT 门、Toffoli门、Fredkin 门等［1］.如何使用指定量子门自动生成量子代价较小的量子电路，是一种可逆逻辑综合问题.为解决此问题，研究者们提出了一些综合算法.Song等［2］给出了可逆逻辑门的代数特征;Iwama等［3］提出了特定 CNOT电路的综合规则，但此规则比较烦琐，且对电路有特别要求;Maslov等［4］提出了先用真值表法构造量子电路，再采用模板技术优化电路的算法来加速可逆逻辑综合;Shende等［5］将可逆逻辑电路综合简化为置换问题，并提出了一种性能较好的递归算法;在此基础上，Yang等［6］将可逆逻辑电路综合进一步抽象为群论问题，并设计了一种基于群论GAP软件的量子电路综合算法，该算法性能远远超过其他算法，但它完全依赖GAP群论软件，因此其性能有待进一步提高;安博等［7］提出了一种基于真值表变换中对换思想的算法，但算法中门库复杂度较高，且初始对换的产生过于固定，容易造成后期优化困难;在Miller等［8］提出的基于变换的可逆逻辑综合算法的基础上，万四爽等［9］提出了类选择排序的算法，该算法从图论的角度考虑问题，提供了一个新的思路进行电路综合;李志强等［10］提出了一种量子可逆逻辑电路综合的快速算法，性能较优，但由于综合了全部量子电路，因此其复杂度较高，难以在单一确定的可逆电路综合中应用.由此可见，研究者们还没有找到适合高效综合大型量子电路的算法.

本文借鉴文献［6-7］中关于置换群理论的思想，针对单一确定可逆电路综合，以可逆函数的本质是置换为基础，总结了最优的基于对换的门库.应用快速排序过程中交换的元素对构成对换序列，逆序级联这些对换对应的门序列，产生实现可逆函数的电路;并运用多项优化技术对初始电路进行优化，以获得最优值或较优值.

1 背景知识

1.1 置换群理论

定义1(二元可逆门)令B={0，1}，一个n输入n输出的二元逻辑电路f定义为f:Bn→Bn.令〈b1，b2，…，bn〉∈Bn，〈p1，p2，…，pn〉∈Bn，其中，b1，b2，…，bn为输入位，p1，p2，…，pn为输出位，且共有2n个不同的输入.当某一二元逻辑电路是一一映射时，它是可逆的.一个n输入n输出的可逆逻辑电路也被称为n量子比特的可逆门.二元可逆函数总共对应(2n)!个不同的n量子比特二元可逆电路.

定义2(置换)令 M={d1，d2，…，dk}，M 到自身的一一映射称作M上的置换.在映射的组合下，M上所有置换构成一个群，称为M上的对称群Sk.置换群是对称群的一个子群.

定义3(循环置换)在Sn中，将x1变到x2，x2变到x3，…，xk变回到x1，而其他文字(如果还有其他文字)不发生变化的置换，称为k-循环置换(简称 k-循环)，记为(x1，x2，x3，…，xk).

性质1k-循环置换满足

定义4每个2-循环置换均称为一个对换.

定理1每个n元置换均可以写成若干个不相连的循环置换的乘积.

定理2每个n元置换均能表示成若干个对换的乘积，如

定义5设 M 上有 2个轮换 τ1，τ2，且 τ1=(a1，a2，…，ai)，τ2=(b1，b2，…，bj)，i，j≤m.若对∀ai，bj均有 ai≠bj，则这2 个轮换作用在不同的元素上，称它们为不相交的.

定理3任意不相交对换的乘积满足交换律.2个相同对换的乘积为恒等关系.

性质2Gt(Ci，Ti)·Gt(Ci，Ti)⇔I，其中，Gt表示Toffoli门，Ci表示控制位，Ti表示受控位.即2个相同的Toffoli门(受控线与控制线均相同)级联，等价于一个恒等关系［11］.

1.2 优化规则

在本文算法中，按照快速排序中产生的对换，从28个基本对换中查找相应的门，便可快速构造初始电路，因此算法的时间复杂度较低.但是，初始电路中门的数量较多，在最坏情况下共有2.82×7=19.74个门，与最优值有较大差距.为了对初始电路进行优化，减少门的数量，本文给出了以下启发式规则:

1)交换移动规则.对于相邻的2个门Gt(C1，T1)与 Gt(C2，T2)，若 T1∉C2且 T2∉C1，即受控位与控制位不相交，则可以交换2个门的位置.

2)抵消归一规则.相同门若相邻，根据性质1可以抵消.

3)合并规则.如果相邻2个Toffoli门的受控端相同而控制端仅1位不同，则可以把不同的控制端去掉，留下相同的控制端和受控端，并将其合并成1个Toffoli门.

2 算法定义

2.1 对换门库的构建

本文构建了一系列实现某一具体对换的可逆门电路，进而形成一个对换门库.在具体的应用算法中，可以直接利用这些模块电路，无需重新生成，从而降低了具体应用算法的时间复杂度.下面以3量子为例介绍对换门库(见表1).由对换的交换性(xy)=(y x)可知，3量子最小对换门库是上三角阵，共7组28个对换门.

表1 三量子对换

2.2 快速排序的输入数据

假设函数F对应的输入输出如表2所示，则快速排序算法的输入数据为{1，0，3，2，5，7，4，6}.

表2 函数F的输入输出

2.3 核心算法

2.3.1 基于快速排序的对换生成算法

将函数 F 的输出{1，0，3，2，5，7，4，6}作为快速排序的输入数据，并记录快速排序中产生的元素交换对，生成最终的对换序列为T0=(0，1)(2，3)(4，5)(5，7)(6，7).进一步将 T0逆序即得到实现F 的序列，即函数 F⇔{1，0，3，2，5，7，4，6}⇔(6，7)(5，7)(4，5)(2，3)(0，1)=T.具体过程见算法 1.

算法1基于快速排序的对换生成算法

2.3.2 对换序列相似度优化算法

利用相似度表生成算法和相似度优化算法可提高对换序列相似度，进而消除更多的门.相似度表s［］［］用于记录不同对换之间可消除的门数.如果当前对换与其左边的对换不相交，且交换这2个对换后可以提高序列的相似度，则执行交换.在算法过程中，每扫描一个对换，均可使结果序列的相似度不低于之前的序列.调整后的对换序列为(6，7)(2，3)(5，7)(4，5)(0，1).相似度生成算法和相似度优化算法的详细描述分别见算法2和算法3.

算法2相似度表生成算法

算法3相似度优化算法

2.3.3 基于合并消除规则的门优化算法

为进一步减少最大相似度序列对应电路中门的数量，本文提出了一种应用多种门级别的优化规则进行门合并或消除的算法.该算法遍历每一个门，对比整个门序列，若与某个门相同且两门相邻，将它们置为0(即可以直接消除);若相同但不相邻，判断这2个门与位于它们中间的门是否可交换，若可以，则可将它们置为0(即可以通过交换来消除).具体过程见算法4.

算法4门优化算法

3 算法实例

按照算法2和算法3输出的最大相似度序列为(6，7)(2，3)(5，7)(4，5)(0，1).参照对换门库，将最大相似度序列中对换所对应的电路序列进行级联，输出的初始电路如图1所示.由图可知，此电路共包含5个Toffoli门.

图1 初始电路

应用算法4对图1中的初始电路进行优化.左边2个门可以合并为1个控制非门，右边2个门可以合并成1个0控的控制非门.所用的优化规则如图2所示.

图2 优化规则

经过算法4优化后的最终电路如图3所示.由图可知，此时仅包含1个Toffoli门和2个控制非门，较初始电路有较大改进.

图3 优化后的电路

4 算法分析与比较

本文算法以可逆函数和置换的等价性为基础，利用快速排序过程中元素交换产生对换，结合预先构建的对换门库进行快速可逆逻辑综合.算法1的时间复杂度为O(N)(其中N为可逆函数的输出数据数)，且其中并不引入任何关于门的计算.算法2生成所有对换的邻近消除规则，其时间复杂度为O(N2)，该算法仅在生成消除规则库时运行1次，之后的应用中仅是对相似度表中元素进行查找，查找时间为O(1).算法3的时间复杂度为

式中，L为算法1综合出的对换序列的初始长度.最坏情况下，将所求可逆函数分解为7个对换，每个对换对应的平均门数为2.82，则此时L≈19.74.

整个综合过程需要存储一个置换表s［］［］、对换序列T、门序列G以及基本对换库，因此其空间复杂度为O(N2).经过算法1初步综合生成的电路门的数量较多，应用本文提出的基于规则的优化算法后，则可保证达到或接近最优电路.如上例中，综合出的门数为5，优化后的门数则为3.

相比于文献［7］提出的算法，本文算法在对换门库上进行了优化，减少了基本电路中的门数量.在产生对换时，本文算法采用快速排序过程中的数据交换对，尽量避免了生成相交的对换，提高了初始电路的相似度并降低了优化复杂度.此外，本文算法中的对换门库引进了广义Toffoli门的优化规则，使得初始产生的电路在优化过程中优先进行Toffoli门的优化，迅速减少门数量及电路开销.引进的Toffoli门优化规则会产生新的门，而新产生的门可能会与剩下电路中的门进行优化.为此，在进一步的优化时，通过增加仅在前一次循行中确实减少了门数量才能进行下一次循环的限制，即可避免算法过程中的无限循环，提高算法效率.

5 结语

本文通过记录快速排序过程中交换的元素对，将可逆函数输出转化为一系列对换的乘积，基于预构建的对换门库逆序快速综合出电路;然后，对综合所得的初始结果应用交换及消去合并规则进行优化，得到最优或较优值.本文算法避免了过多的迭代过程，仅仅相当于完成了一次排序过程，因此在时间与效率上有较大的提高.与文献［7］中的算法相比，本文算法中的初始电路门数量更少，优化速度更快;与文献［4］中的算法相比，综合电路时节约了更多的时间.

排序过程中交换元素的不确定性，使得对于不同的可逆函数，本文算法不能保证产生的初始电路总有较高的相似度.因此，即使进行多项优化，最终结果仍可能距最优值有较大差距.下一步的研究工作是寻找更好的能稳定产生较高相似度初始电路的排序算法、建立更多的优化规则以及引入更有效的优化算法.

References)

［1］Fredkin E，Toffoli T.Conservative logic［J］.International Journal of Theoretical Physics，1982，21(3):219-253.

［2］Song X Y，Yang G W，Perkowski M.Algebraic characteristics of reversible gates［J］.Theory of Computing Systems，2004，37(2):311-319.

［3］Iwama K，Kambayashi Y，Yamashita S.Transformation rules for designing CNOT-based quantum circuits［C］//Proceedings of the 39th Annual Design Automation Conference.New York，USA，2002:419-424.

［4］Maslov D，Dueck G W，Miller D M.Toffoli network synthesis with templates［J］.IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems，2005，24(6):807-817.

［5］Shende V V，Prasad A K，Markov I L，et al.Reversible logic circuit synthesis［C］//Proceedings of 2002 IEEE/ACM International Conference on Computer-Aided Design.New Orleans，Louisiana，USA，2002:125-132.

［6］Yang G W，Song X Y，Perkowski M，et al.Fast synthesis of exact minimal reversible circuits using group theory［C］//Proceedings of 2005 IEEE ASP-DAC.Shanghai，China，2005:18-21.

［7］安博，陈汉武，杨忠明，等.基于真值表变换的可逆逻辑综合算法［J］.东南大学学报:自然科学版，2010，40(1):58-63.An Bo，Chen Hanwu，Yang Zhongming，et al.A reversible logic synthesis algorithm based on the transformation of truth table［J］.Journal of Southeast University:Natural Science Edition，2010，40(1):58-63.(in Chinese)

［8］Miller D M，Maslov D，Dueck G W.A transformation based algorithm for reversible logic synthesis［C］//Proceedings of the 40th Annual Design Automation Conference.Anaheim，CA，USA，2003:318-323.

［9］万四爽，陈汉武，曹如进.类选择排序的可逆逻辑综合算法［J］.计算机学报，2010，33(12):2343-2352.Wan Sishuang，Chen Hanwu，Cao Rujin.An analogic selection sorting algorithm for synthesis of reversible logic circuits［J］.Chinese Journal of Computer，2010，33(12):2343-2352.(in Chinese)

［10］李志强，陈汉武，徐宝文，等.量子可逆逻辑电路综合的快速算法研究［J］.计算机学报，2009，32(7):1291-1303.Li Zhiqiang，Chen Hanwu，Xu Baowen，et al.A fast algorithm for synthesis of quantum reversible logic circuits［J］.Chinese Journal of Computer，2009，32(7):1291-1303.(in Chinese)

［11］Bennett C.Logical reversibility of computation［J］.IBM Journal of Research and Development，1973，17(6):525-532.