李志鋼 陳漢武，2 李志強 朱皖寧 劉志昊

(1東南大學(xué)計算機科學(xué)與工程學(xué)院，南京211189)

(2東南大學(xué)計算機網(wǎng)絡(luò)和信息集成教育部重點實驗室，南京211189)

(3揚州大學(xué)信息工程學(xué)院，揚州225009)

量子計算機的概念源于對可逆計算機的研究，而研究可逆計算機是為了克服計算機的能耗問題.經(jīng)典計算機是由包含連線與邏輯門的電路構(gòu)建而成的，與此類似，量子計算機是由連線和量子邏輯門級聯(lián)形成的處理量子信息的量子電路建造的.區(qū)別于傳統(tǒng)的不可逆電路，可逆電路要求其輸入和輸出之間存在一一映射，且在電路中不能存在扇入、扇出和反饋，所以可逆電路綜合技術(shù)比不可逆電路綜合技術(shù)更為復(fù)雜，目前還沒有通用高效的算法.近30年來，研究者們已經(jīng)提出了多種量子門，如CNOT 門、Toffoli門、Fredkin 門等［1］.如何使用指定量子門自動生成量子代價較小的量子電路，是一種可逆邏輯綜合問題.為解決此問題，研究者們提出了一些綜合算法.Song等［2］給出了可逆邏輯門的代數(shù)特征;Iwama等［3］提出了特定 CNOT電路的綜合規(guī)則，但此規(guī)則比較煩瑣，且對電路有特別要求;Maslov等［4］提出了先用真值表法構(gòu)造量子電路，再采用模板技術(shù)優(yōu)化電路的算法來加速可逆邏輯綜合;Shende等［5］將可逆邏輯電路綜合簡化為置換問題，并提出了一種性能較好的遞歸算法;在此基礎(chǔ)上，Yang等［6］將可逆邏輯電路綜合進一步抽象為群論問題，并設(shè)計了一種基于群論GAP軟件的量子電路綜合算法，該算法性能遠(yuǎn)遠(yuǎn)超過其他算法，但它完全依賴GAP群論軟件，因此其性能有待進一步提高;安博等［7］提出了一種基于真值表變換中對換思想的算法，但算法中門庫復(fù)雜度較高，且初始對換的產(chǎn)生過于固定，容易造成后期優(yōu)化困難;在Miller等［8］提出的基于變換的可逆邏輯綜合算法的基礎(chǔ)上，萬四爽等［9］提出了類選擇排序的算法，該算法從圖論的角度考慮問題，提供了一個新的思路進行電路綜合;李志強等［10］提出了一種量子可逆邏輯電路綜合的快速算法，性能較優(yōu)，但由于綜合了全部量子電路，因此其復(fù)雜度較高，難以在單一確定的可逆電路綜合中應(yīng)用.由此可見，研究者們還沒有找到適合高效綜合大型量子電路的算法.

本文借鑒文獻［6-7］中關(guān)于置換群理論的思想，針對單一確定可逆電路綜合，以可逆函數(shù)的本質(zhì)是置換為基礎(chǔ)，總結(jié)了最優(yōu)的基于對換的門庫.應(yīng)用快速排序過程中交換的元素對構(gòu)成對換序列，逆序級聯(lián)這些對換對應(yīng)的門序列，產(chǎn)生實現(xiàn)可逆函數(shù)的電路;并運用多項優(yōu)化技術(shù)對初始電路進行優(yōu)化，以獲得最優(yōu)值或較優(yōu)值.

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個不同的輸入.當(dāng)某一二元邏輯電路是一一映射時，它是可逆的.一個n輸入n輸出的可逆邏輯電路也被稱為n量子比特的可逆門.二元可逆函數(shù)總共對應(yīng)(2n)!個不同的n量子比特二元可逆電路.

定義2(置換)令 M={d1，d2，…，dk}，M 到自身的一一映射稱作M上的置換.在映射的組合下，M上所有置換構(gòu)成一個群，稱為M上的對稱群Sk.置換群是對稱群的一個子群.

定義3(循環(huán)置換)在Sn中，將x1變到x2，x2變到x3，…，xk變回到x1，而其他文字(如果還有其他文字)不發(fā)生變化的置換，稱為k-循環(huán)置換(簡稱 k-循環(huán))，記為(x1，x2，x3，…，xk).

性質(zhì)1k-循環(huán)置換滿足

定義4每個2-循環(huán)置換均稱為一個對換.

定理1每個n元置換均可以寫成若干個不相連的循環(huán)置換的乘積.

定理2每個n元置換均能表示成若干個對換的乘積，如

定義5設(shè) M 上有 2個輪換 τ1，τ2，且 τ1=(a1，a2，…，ai)，τ2=(b1，b2，…，bj)，i，j≤m.若對?ai，bj均有 ai≠bj，則這2 個輪換作用在不同的元素上，稱它們?yōu)椴幌嘟坏?

定理3任意不相交對換的乘積滿足交換律.2個相同對換的乘積為恒等關(guān)系.

性質(zhì)2Gt(Ci，Ti)·Gt(Ci，Ti)?I，其中，Gt表示Toffoli門，Ci表示控制位，Ti表示受控位.即2個相同的Toffoli門(受控線與控制線均相同)級聯(lián)，等價于一個恒等關(guān)系［11］.

1.2 優(yōu)化規(guī)則

在本文算法中，按照快速排序中產(chǎn)生的對換，從28個基本對換中查找相應(yīng)的門，便可快速構(gòu)造初始電路，因此算法的時間復(fù)雜度較低.但是，初始電路中門的數(shù)量較多，在最壞情況下共有2.82×7=19.74個門，與最優(yōu)值有較大差距.為了對初始電路進行優(yōu)化，減少門的數(shù)量，本文給出了以下啟發(fā)式規(guī)則:

1)交換移動規(guī)則.對于相鄰的2個門Gt(C1，T1)與 Gt(C2，T2)，若 T1?C2且 T2?C1，即受控位與控制位不相交，則可以交換2個門的位置.

2)抵消歸一規(guī)則.相同門若相鄰，根據(jù)性質(zhì)1可以抵消.

3)合并規(guī)則.如果相鄰2個Toffoli門的受控端相同而控制端僅1位不同，則可以把不同的控制端去掉，留下相同的控制端和受控端，并將其合并成1個Toffoli門.

2 算法定義

2.1 對換門庫的構(gòu)建

本文構(gòu)建了一系列實現(xiàn)某一具體對換的可逆門電路，進而形成一個對換門庫.在具體的應(yīng)用算法中，可以直接利用這些模塊電路，無需重新生成，從而降低了具體應(yīng)用算法的時間復(fù)雜度.下面以3量子為例介紹對換門庫(見表1).由對換的交換性(xy)=(y x)可知，3量子最小對換門庫是上三角陣，共7組28個對換門.

表1 三量子對換

2.2 快速排序的輸入數(shù)據(jù)

假設(shè)函數(shù)F對應(yīng)的輸入輸出如表2所示，則快速排序算法的輸入數(shù)據(jù)為{1，0，3，2，5，7，4，6}.

表2 函數(shù)F的輸入輸出

2.3 核心算法

2.3.1 基于快速排序的對換生成算法

將函數(shù) F 的輸出{1，0，3，2，5，7，4，6}作為快速排序的輸入數(shù)據(jù)，并記錄快速排序中產(chǎn)生的元素交換對，生成最終的對換序列為T0=(0，1)(2，3)(4，5)(5，7)(6，7).進一步將 T0逆序即得到實現(xiàn)F 的序列，即函數(shù) 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 對換序列相似度優(yōu)化算法

利用相似度表生成算法和相似度優(yōu)化算法可提高對換序列相似度，進而消除更多的門.相似度表s［］［］用于記錄不同對換之間可消除的門數(shù).如果當(dāng)前對換與其左邊的對換不相交，且交換這2個對換后可以提高序列的相似度，則執(zhí)行交換.在算法過程中，每掃描一個對換，均可使結(jié)果序列的相似度不低于之前的序列.調(diào)整后的對換序列為(6，7)(2，3)(5，7)(4，5)(0，1).相似度生成算法和相似度優(yōu)化算法的詳細(xì)描述分別見算法2和算法3.

算法2相似度表生成算法

算法3相似度優(yōu)化算法

2.3.3 基于合并消除規(guī)則的門優(yōu)化算法

為進一步減少最大相似度序列對應(yīng)電路中門的數(shù)量，本文提出了一種應(yīng)用多種門級別的優(yōu)化規(guī)則進行門合并或消除的算法.該算法遍歷每一個門，對比整個門序列，若與某個門相同且兩門相鄰，將它們置為0(即可以直接消除);若相同但不相鄰，判斷這2個門與位于它們中間的門是否可交換，若可以，則可將它們置為0(即可以通過交換來消除).具體過程見算法4.

算法4門優(yōu)化算法

3 算法實例

按照算法2和算法3輸出的最大相似度序列為(6，7)(2，3)(5，7)(4，5)(0，1).參照對換門庫，將最大相似度序列中對換所對應(yīng)的電路序列進行級聯(lián)，輸出的初始電路如圖1所示.由圖可知，此電路共包含5個Toffoli門.

圖1 初始電路

應(yīng)用算法4對圖1中的初始電路進行優(yōu)化.左邊2個門可以合并為1個控制非門，右邊2個門可以合并成1個0控的控制非門.所用的優(yōu)化規(guī)則如圖2所示.

圖2 優(yōu)化規(guī)則

經(jīng)過算法4優(yōu)化后的最終電路如圖3所示.由圖可知，此時僅包含1個Toffoli門和2個控制非門，較初始電路有較大改進.

圖3 優(yōu)化后的電路

4 算法分析與比較

本文算法以可逆函數(shù)和置換的等價性為基礎(chǔ)，利用快速排序過程中元素交換產(chǎn)生對換，結(jié)合預(yù)先構(gòu)建的對換門庫進行快速可逆邏輯綜合.算法1的時間復(fù)雜度為O(N)(其中N為可逆函數(shù)的輸出數(shù)據(jù)數(shù))，且其中并不引入任何關(guān)于門的計算.算法2生成所有對換的鄰近消除規(guī)則，其時間復(fù)雜度為O(N2)，該算法僅在生成消除規(guī)則庫時運行1次，之后的應(yīng)用中僅是對相似度表中元素進行查找，查找時間為O(1).算法3的時間復(fù)雜度為

式中，L為算法1綜合出的對換序列的初始長度.最壞情況下，將所求可逆函數(shù)分解為7個對換，每個對換對應(yīng)的平均門數(shù)為2.82，則此時L≈19.74.

整個綜合過程需要存儲一個置換表s［］［］、對換序列T、門序列G以及基本對換庫，因此其空間復(fù)雜度為O(N2).經(jīng)過算法1初步綜合生成的電路門的數(shù)量較多，應(yīng)用本文提出的基于規(guī)則的優(yōu)化算法后，則可保證達到或接近最優(yōu)電路.如上例中，綜合出的門數(shù)為5，優(yōu)化后的門數(shù)則為3.

相比于文獻［7］提出的算法，本文算法在對換門庫上進行了優(yōu)化，減少了基本電路中的門數(shù)量.在產(chǎn)生對換時，本文算法采用快速排序過程中的數(shù)據(jù)交換對，盡量避免了生成相交的對換，提高了初始電路的相似度并降低了優(yōu)化復(fù)雜度.此外，本文算法中的對換門庫引進了廣義Toffoli門的優(yōu)化規(guī)則，使得初始產(chǎn)生的電路在優(yōu)化過程中優(yōu)先進行Toffoli門的優(yōu)化，迅速減少門數(shù)量及電路開銷.引進的Toffoli門優(yōu)化規(guī)則會產(chǎn)生新的門，而新產(chǎn)生的門可能會與剩下電路中的門進行優(yōu)化.為此，在進一步的優(yōu)化時，通過增加僅在前一次循行中確實減少了門數(shù)量才能進行下一次循環(huán)的限制，即可避免算法過程中的無限循環(huán)，提高算法效率.

5 結(jié)語

本文通過記錄快速排序過程中交換的元素對，將可逆函數(shù)輸出轉(zhuǎn)化為一系列對換的乘積，基于預(yù)構(gòu)建的對換門庫逆序快速綜合出電路;然后，對綜合所得的初始結(jié)果應(yīng)用交換及消去合并規(guī)則進行優(yōu)化，得到最優(yōu)或較優(yōu)值.本文算法避免了過多的迭代過程，僅僅相當(dāng)于完成了一次排序過程，因此在時間與效率上有較大的提高.與文獻［7］中的算法相比，本文算法中的初始電路門數(shù)量更少，優(yōu)化速度更快;與文獻［4］中的算法相比，綜合電路時節(jié)約了更多的時間.

排序過程中交換元素的不確定性，使得對于不同的可逆函數(shù)，本文算法不能保證產(chǎn)生的初始電路總有較高的相似度.因此，即使進行多項優(yōu)化，最終結(jié)果仍可能距最優(yōu)值有較大差距.下一步的研究工作是尋找更好的能穩(wěn)定產(chǎn)生較高相似度初始電路的排序算法、建立更多的優(yōu)化規(guī)則以及引入更有效的優(yōu)化算法.

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］.東南大學(xué)學(xué)報:自然科學(xué)版，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］.計算機學(xué)報，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］.計算機學(xué)報，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.