基于對(duì)換門庫(kù)的可逆邏輯電路綜合算法

李志鋼 陳漢武，2 李志強(qiáng) 朱皖寧 劉志昊

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

(2東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，南京211189)

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

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

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

1 背景知識(shí)

1.1 置換群理論

定義1(二元可逆門)令B={0，1}，一個(gè)n輸入n輸出的二元邏輯電路f定義為f:Bn→Bn.令〈b1，b2，…，bn〉∈Bn，〈p1，p2，…，pn〉∈Bn，其中，b1，b2，…，bn為輸入位，p1，p2，…，pn為輸出位，且共有2n個(gè)不同的輸入.當(dāng)某一二元邏輯電路是一一映射時(shí)，它是可逆的.一個(gè)n輸入n輸出的可逆邏輯電路也被稱為n量子比特的可逆門.二元可逆函數(shù)總共對(duì)應(yīng)(2n)!個(gè)不同的n量子比特二元可逆電路.

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

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

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

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

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

定理2每個(gè)n元置換均能表示成若干個(gè)對(duì)換的乘積，如

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

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

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

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

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

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

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

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

2 算法定義

2.1 對(duì)換門庫(kù)的構(gòu)建

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

表1 三量子對(duì)換

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

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

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

2.3 核心算法

2.3.1 基于快速排序的對(duì)換生成算法

將函數(shù) F 的輸出{1，0，3，2，5，7，4，6}作為快速排序的輸入數(shù)據(jù)，并記錄快速排序中產(chǎn)生的元素交換對(duì)，生成最終的對(duì)換序列為T0=(0，1)(2，3)(4，5)(5，7)(6，7).進(jìn)一步將 T0逆序即得到實(shí)現(xiàn)F 的序列，即函數(shù) F?{1，0，3，2，5，7，4，6}?(6，7)(5，7)(4，5)(2，3)(0，1)=T.具體過(guò)程見(jiàn)算法 1.

算法1基于快速排序的對(duì)換生成算法

2.3.2 對(duì)換序列相似度優(yōu)化算法

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

算法2相似度表生成算法

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

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

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

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

3 算法實(shí)例

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

圖1 初始電路

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

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

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

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

4 算法分析與比較

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

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

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

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

5 結(jié)語(yǔ)

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

排序過(guò)程中交換元素的不確定性，使得對(duì)于不同的可逆函數(shù)，本文算法不能保證產(chǎn)生的初始電路總有較高的相似度.因此，即使進(jìn)行多項(xiàng)優(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é)報(bào):自然科學(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］萬(wàn)四爽，陳漢武，曹如進(jìn).類選擇排序的可逆邏輯綜合算法［J］.計(jì)算機(jī)學(xué)報(bào)，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］李志強(qiáng)，陳漢武，徐寶文，等.量子可逆邏輯電路綜合的快速算法研究［J］.計(jì)算機(jī)學(xué)報(bào)，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.