量子可逆邏輯電路綜合

樂 亮, 解光軍

(合肥工業(yè)大學(xué)電子科學(xué)與應(yīng)用物理學(xué)院,安徽合肥 230009)

0 引 言

從20世紀(jì)60年代開始,摩爾定律在幾十年的時間里都是近似成立的。然而,大多數(shù)觀察家預(yù)期這將在21世紀(jì)的前20年內(nèi)結(jié)束:當(dāng)電子器件越做越小的時候,其內(nèi)部量子效應(yīng)也越來越明顯,制造計算機的傳統(tǒng)方法在進一步提高集成度上越來越顯得力不從心;與此同時,集成電路能耗會導(dǎo)致計算機芯片發(fā)熱,這一點也影響了芯片集成度的進一步提高。集成電路功耗主要來自于計算過程中的不可逆操作,例如,對于2個比特的異或操作,只有一個比特的輸出。這個過程中損失了一個自由度,這正是一個不可逆操作,而損失掉的自由度就轉(zhuǎn)化為熱量耗散掉了。所以消除能耗的關(guān)鍵就是尋找可逆操作替代計算過程中的不可逆操作。量子計算就是基于量子力學(xué)而非經(jīng)典物理學(xué)的思想進行的計算,量子計算中每一步操作都可以用一個幺正變換來表示,因而每一個操作都是可逆的。

量子計算機不丟失輸入信息,不存在熱耗散,從理論上解決了芯片的熱耗問題,量子計算機可以等效為一個量子圖靈機。量子圖靈機是一個抽象的數(shù)學(xué)模型,理論上已證明,量子圖靈機可以等價為一個量子邏輯電路。類似于經(jīng)典計算機是由包含連線與邏輯門的電路構(gòu)建而成,量子計算機是由包含連線和量子邏輯門級聯(lián)形成、處理量子信息的量子電路建造的。如何用計算機自動綜合量子電路成為研究的重點。

1 量子可逆邏輯電路概述

利用微觀粒子狀態(tài)表示的信息稱為量子信息,量子信息的基本單位是量子比特。與經(jīng)典信息不同,量子比特能夠以疊加態(tài)的形式存在,任何量子比特均可由一個二元向量形式表示:|ψ〉=a|0〉+b|1〉,其中a和b為復(fù)數(shù),滿足歸一化條件:|a|2+|b|2=1。在經(jīng)典信息系統(tǒng)中,n個比特只能夠代表2n個不同的狀態(tài);而在量子信息系統(tǒng)中,n個量子比特能夠代表的不同狀態(tài)的數(shù)量與這2n個態(tài)所能疊加出的態(tài)的數(shù)目是一致的。這個特點使得量子比特在其所能夠表達(dá)的信息量的數(shù)量上,大大優(yōu)于經(jīng)典比特。

處理量子信息的基本單元是量子邏輯門。量子信息經(jīng)過各個量子邏輯門時,依據(jù)門功能發(fā)生變換。量子邏輯門對量子信息的操作其實是一個幺正變換,幺正變換的一個重要特點就是這些變換都是可逆的,即每個量子邏輯門也是可逆的。主要的量子邏輯門有Toffoli門、Fredkin門等。

量子電路是由若干量子邏輯門級聯(lián)構(gòu)成,它是對量子信息作一系列幺正變換以實現(xiàn)電路功能。量子可逆邏輯電路具有以下特點:①輸入線數(shù)與輸出線數(shù)相等;②沒有扇出與扇入;③沒有反饋;④電路分層級聯(lián),有時為保證電路可逆性需要人為添加一些輔助位,即沒有用的數(shù)據(jù)位。一個n位輸入、n位輸出的量子電路,稱為n×n規(guī)模的量子電路。

可逆電路的量子代價是指它所有量子門的量子代價的總和,而量子門的量子代價是指這個門為了實現(xiàn)其可逆函數(shù)功能,所需要完成的基本的量子操作的量子代價的總和。不同量子門的量子代價不同。

2 量子可逆邏輯電路綜合方法

經(jīng)典電路的綜合是用適當(dāng)?shù)碾娐吩骷赃m當(dāng)?shù)倪B接方式實現(xiàn)所需要的功能,量子電路的綜合也類似于此:找尋適當(dāng)?shù)牧孔娱T級聯(lián)方式實現(xiàn)指定功能。在量子電路可逆邏輯綜合問題的研究中,不只為了找到量子電路可逆的執(zhí)行方法,而且要在綜合結(jié)果中盡可能找到最低的量子代價,但這并不意味著只保證綜合電路的門數(shù)最少。傳統(tǒng)的邏輯綜合方法中,邏輯門的數(shù)量被看作是一個電路代價的重要因素。而從量子電路可逆邏輯綜合的觀點看,還存在另一個重要的事實,那就是垃圾信息輸出的數(shù)量。

在使用可逆量子門進行可逆邏輯設(shè)計過程中,輸入的數(shù)量與輸出的數(shù)量必須是相等的。一個量子可逆邏輯電路中,可逆性要求輸出門總數(shù)與輸入門總數(shù)相等。所以在很多情況下,垃圾信息是不可避免的。在尋找量子邏輯電路最低代價的過程中,對于相同量子門電路的優(yōu)化問題,最小化門的數(shù)量仍然是可逆邏輯優(yōu)化的重要目標(biāo)。以下主要以Toffoli門為例對電路綜合方法作說明,僅以量子門數(shù)量作為優(yōu)化衡量標(biāo)準(zhǔn)。

2.1 基于變化法的綜合

由文獻(xiàn)[1,2]提出的基于變換法的綜合方法主要是通過一些變換規(guī)則,將輸出值逆向逐次變換成輸入值,在每一次的變換過程中選取相應(yīng)的Toffoli門,最終構(gòu)成所需要的量子電路。設(shè)輸入為i,輸出為f(i),變換的步驟如下:

(1)如果 f(0)≠0,則翻轉(zhuǎn)輸出 f(0)中所有為1的量子位。每一位翻轉(zhuǎn)都要求用到一個1×1的Toffoli門(即NOT門)。如果將變換后的可逆函數(shù)記為f+,那么這一步最后得到的結(jié)果將滿足f+(0)=0。

(2)依次考慮輸入 i,其中i滿足 1≤i＜2n-1。如果f+(i)=i,我們的目的達(dá)到了,就不需要對電路進行任何變換,也就不需要添加 Toffoli門;如果f+(i)≠i,那么對于這一輸入i,需要添加合適的Toffoli門,對電路進行變換,以使得變換后得到的新的布爾函數(shù) f++滿足 f++(i)=i。添加的Toffoli門將滿足 f+(i)→i。

對于在輸入i的二進制形式中為1而在輸出f+(i)的二進制形式中卻為0的量子位,用在所有相應(yīng)位置為1的比特序列p來表示,那么為了實現(xiàn) f+(i)→i的匹配,必須在輸出端與比特序列p中為1的量子位相應(yīng)的位置添加1;相反,對于在輸入i的二進制形式中為0而在輸出 f+(i)的二進制形式中卻為1的量子位,用在所有相應(yīng)位置為 1的比特序列 q來表示,那么為了實現(xiàn)f+(i)→i的匹配,必須在輸出端與比特序列中q為1的量子位相應(yīng)的位置清除1。

對于比特序列p的每一位pj=1,都需要在量子電路的輸出端一邊使用一個 Toffoli門進行翻轉(zhuǎn),并且這個Toffoli門在所有對應(yīng)于輸入i的二進制形式中為1的量子位上都有其一個控制點,而它的受控位則在j線上;同樣,對于比特序列q的每一位qk=1,也都需要在量子電路的輸出端一邊使用一個Toffoli門進行翻轉(zhuǎn),并且這個Toffoli門在所有對應(yīng)于輸出 f+(i)的二進制形式中為1的量子位上都有其一個控制點,而它的受控位在k線上。

對于每一輸入1≤i＜2n-1,第(2)步操作都通過特定順序的Toffoli門序列完成 f+(i)→i的映射。由于這種算法是按順序依次考慮不同的輸入i的,并且步驟(1)解決的是i=0時的情形,可以確定對于0≤j＜i,有 f+(j)→j成立。這一點的重要意義在于,在步驟(2)中新使用的Toffoli門并不會影響在前一級操作所匹配成功的布爾函數(shù)功能f+(j),其中 j＜i。即一旦將一行規(guī)則變換到正確的數(shù)值,它就固定不變而與后面行所需的變換無關(guān)。顯然,最后一行規(guī)則不需要變換,因為前面2n-1個數(shù)值的位置已經(jīng)是正確的。

由圖3中A可知，隨著酶解時間的增加，辣椒堿、辣椒二氫堿及辣椒紅色素的含量先增加后降低。原因可能是，溫度與酶解時間有關(guān)，酶解時間短，失活不明顯，最佳溫度較高；反應(yīng)時間越長，最佳溫度越低。由于這種關(guān)系，酶的最適溫度只有在一定條件下才有意義，同時由于溫度過高，會導(dǎo)致部分酶失活。因此，確定提取辣椒堿、辣椒二氫堿及辣椒紅色素的最適酶解溫度均為50 ℃。

該算法具有簡單、易于實現(xiàn)的特點,對于給定的函數(shù)功能,此算法最終總能得出一個成功的電路。但對于任意的 M,建立的函數(shù)有可能需要(M-1)2M+1個Toffoli門。在以上規(guī)則中,所描述的通過選擇Toffoli門來生成電路的算法都只是處理規(guī)則的輸出邊,稱為后向綜合法。

圖1所示列舉了一個3輸入、3輸出量子電路的后向綜合法的過程,按照上述規(guī)則演示了從輸出端順次加入4個門,使輸出變換到與輸入一致的過程:①在輸出b0加一個非門使 f(0)從010翻轉(zhuǎn)成000;②f1(1)=100,要將其翻轉(zhuǎn)成001,先翻轉(zhuǎn)a1,由于c1=1,加入一個受控端在a1控制端在c1的受控非門;f2(1)=101,③繼續(xù)翻轉(zhuǎn)c2加入一個受控端在c2,控制端在a2的受控非門使得f3(1)=001;④按輸入的二進制數(shù)大小的升序繼續(xù)考慮 f3(2)=010無須翻轉(zhuǎn),f3(3)=111≠011,需翻轉(zhuǎn)c3,由于 a3、b3=1,加入一個控制端在 a3、b3受控端在 c3的 Toffoli門使得f4(3)=011;后面的輸入與輸出一致,變換結(jié)束。

由于規(guī)則的可逆性,我們可以將規(guī)則翻轉(zhuǎn)(從輸入邊加門)也可以得到一個電路,稱為前向綜合法,再選擇2種電路中規(guī)模較小的一個。一種更簡便的方法是,在規(guī)則的兩邊同時運用這種選擇策略,以輸入與輸出的二進制數(shù)間的漢明距離大小決定門是加在輸入邊還是輸出邊,稱為雙向綜合法。圖2演示了同一真值表用雙向綜合法用3個門完成電路綜合的過程:①在輸入端b加一個非門使f1(0)=000;② f1(1)=001,f1(2)=010無需變換,f1(3)=110,此時考慮正向變換011與111漢明距離為1,后向變換011與110漢明距離為2,前者較小所以使用前向變換加入個受控端在c1,控制端在a1、b1的 Toffoli門交換輸入 011和111使得 f2(3)=011;③f2(4)=101,前向變換和后向變換都是要將100和101交換,漢明距離都為1,無論使用哪種變換方向,加入1個受控端在a2,控制端在c2的受控非門,完成變換。

由于雙向綜合法在加門的過程中加入對漢明距離的判斷,從兩邊加門,更為靈活,容易得到比較簡單的電路。這種方法必然可以通過真值表生成電路,具有普遍適應(yīng)性。其缺點是生成電路復(fù)雜,即便經(jīng)過模板法優(yōu)化也難達(dá)到最優(yōu)(原因在于模板的完備性及模板匹配率的局限)。

圖1 后向綜合法舉例

圖2 雙向綜合法舉例

2.2 窮舉法

由文獻(xiàn)[3]提出的窮舉算法的核心思想是根據(jù)輸入輸出數(shù),遍歷所有電路,找到最優(yōu)符合邏輯功能的電路。對于確定的輸入、輸出數(shù)n,給電路加入各種Toffoli門,門的數(shù)量由少到多,搜索到的第一個符合功能要求的就是最優(yōu)電路。

此方法必定可以找到最優(yōu)解,但是目前僅對輸入、輸出數(shù)較小的電路有可行性,隨著n的增大計算量迅速增大,算法太慢,失去可行性。

2.3 RM展開式綜合法

對于每一個輸出Fi,有Fi=d0⊕d1P1⊕…⊕diPi,其中的d值由以下算法給出:

將電路功能表示成RM展開式后,就可以利用它進行量子電路綜合。依據(jù)各個量子位輸出量的RM表達(dá)式,找出其展開項中不含相應(yīng)輸入量的因子,然后依次試探量子門Toffoli(ck,xk),把原來的表達(dá)式中的 xk用代換(此代換表示所加量子門的功能),并化簡,不斷重復(fù)此過程,直至RM 展開式變?yōu)楹愕仁?即對于任意i∈{1,2,…,n},有yi=xi,將化簡過程中使用的量子邏輯門順序排列,即可生成所求量子可逆邏輯電路。

將圖2的真值表生成可逆邏輯電路的過程如圖3所示。

圖3 RM展開式法舉例

將化簡過程中用到的Toffoli門,從輸出到輸入按順序排列,就得到圖2所示電路。代換化簡的路徑不止一種,通常通過優(yōu)先權(quán)公式?jīng)Q定,也有人提出遍歷所有路徑,第一個完成化簡的就是最優(yōu)解。這種方法缺乏通用性,而且生成電路通常不是最優(yōu),只是局部最優(yōu)。

2.4 基于群論的綜合法

文獻(xiàn)[4,5]將可逆邏輯電路綜合抽象為群論問題,設(shè)計出基于群論GAP軟件的量子電路綜合算法,其性能大幅度提高。一個n×n的量子可逆邏輯門的輸入和輸出對可有2n!種組合,若將每個組合對應(yīng)一個置換,則這些置換的集合就組成一個置換群Sn,而n階的各種門對應(yīng)的置換也在Sn中。此方法的核心思想是將目標(biāo)函數(shù)所對應(yīng)的置換用置換群中一些門(這些門的集合是此算法的庫)的置換分解替代,并找到最簡的替代組合,綜合出電路。對于庫L,其元素可以構(gòu)成的所有置換功能的集合記做G(L)。對于G(L)中的元素a,若用L中至少minl(a)個元素串接能構(gòu)成a,則minl(a)稱為a在G(L)中的最小長度。以下用2個程序說明此方法的基本流程:

程序FML計算最小長度,將被MLR調(diào)用。

程序MLR是對于目標(biāo)函數(shù)對應(yīng)的置換g,用庫L去求其最小長度并得出最簡電路。前幾步先判定g是否能由L生成,若能則定位其最小長度電路的長度k。接下來尋找L中元素ci其逆置換與g相乘后能得到最小長度為k-1的置換,如此遞歸下去保證每加入1個元素都使置換的最小長度減1,直到最小長度為0。

將這些元素所對應(yīng)的門順次排列起來就得到最簡電路。綜合3階電路時可以用3個非門,6個受控非門,3個標(biāo)準(zhǔn) Toffoli門構(gòu)成完備的庫L;對于更高階電路,使用通用庫是非常困難的,庫中元素數(shù)目的變化同時影響計算速度和庫的通用性,并且此消彼長。

3 結(jié)束語

量子可逆邏輯綜合是一個新興的研究領(lǐng)域。可逆邏輯電路的綜合與優(yōu)化由同一過程完成是今后研究的主流。在綜合量子電路的同時還要考慮電路門的最小化和量子代價最小化,這對算法模型、算法解空間上的搜索復(fù)雜程度都有相當(dāng)?shù)目简?。窮舉法雖然必能找最優(yōu)解但是計算復(fù)雜度太高,只能適用低階電路;真值表變換法基于電路變換規(guī)則直接對真值表操作,對任何電路都有解,且計算復(fù)雜度低,具有普遍適用性,缺點是結(jié)果不是最優(yōu)解,優(yōu)化難度高;RM展開式法將電路綜合過程轉(zhuǎn)化為展開式化簡過程,計算復(fù)雜度低,只與電路階數(shù)n線性相關(guān),即使遍歷所有化簡路徑也只與m×n有關(guān)(m為最大路徑數(shù)),且能找到較優(yōu)解,缺點是結(jié)果不一定是最優(yōu)解,有些情況下可能無解;群論法將電路用置換對的數(shù)學(xué)模型代替,合理利用群論的高性能計算,必能找到最優(yōu)解,缺點是計算復(fù)雜度與2n!相關(guān)[6-9]。

在掌握和比較分析現(xiàn)有方法的基礎(chǔ)上,應(yīng)該繼續(xù)探索新的方法,新方法應(yīng)對任何目標(biāo)函數(shù)都能適用,最好能確定最優(yōu)解;綜合模型容易轉(zhuǎn)換實現(xiàn),算法要能適應(yīng)高階電路,復(fù)雜程度、計算量不能隨階數(shù)增大成指數(shù)增長,可適用于高階電路。

[1] Dueck G W,Maslov D,Miller D M.Transformation-based synthesis of networks of T offoli/Fredkin Gates[C]//IEEE CCECE,2003:211-214.

[2] Miller D M,Maslov D,Dueck G W.A transformation based algorithm for reversible logic sy nthesis[C]//DAC,2003:318-323.

[3] Shende V V,Bullock S S,M arkov I L.Synthesis of quantum logic circuits[J].IEEE T ransactions on Computer-Aided Design of Integrated Circuits and Systems,2006,25(6):1000-1010.

[4] Yang G W,Song X Y,Hung W N,et al.Group theory based synthesis of binary reversible circuits[C]//TAMC,2006:365-374.

[5] Yang G W,Song X Y,Hung W N,et al.Fast synthesis of exact minimal reversible circuits using group theory[C]//ASP-DAC,2005:1002-1005.

[6] Gupta P,Agrawal A,Jha N K.An algorithm for synthesis of reversible logic circuits[J].IEEE Transactions on Computer-Aided Design of Integ rater Circuits and Sy stems,2006,25(11):2317-2330.

[7] Wille R,G rope D.Fast exact Toffoli network sy nthesis of reversible logic[C]//ICCAD,2007:60-64.

[8] Li Z Q,Chen H W,Xu B W,et al.Fast algorithm for 4-qubit reversible logic circuits synthesis[C]//CEC,2008:2202-2207.

[9] Li Z Q,Chen H W,Xu B W,et al.An algorithm for synthesis of optimal 3-qubit reversible circuits based on bit operation[C]//WGEC,2008:455-458.