陳 華,傅美容
(1.中國電子學會辦公室,北京 100036;2.北京聯(lián)合大學特殊教育學院特殊教育系,北京 100101)
如果數(shù)字組合邏輯電路將每個輸入模式映射到唯一的輸出模式,則稱該電路為可逆電路[1]。根據(jù)Landauer[2]的證明,不管底層技術(shù)如何實現(xiàn),如果使用傳統(tǒng)的不可逆邏輯門必定會產(chǎn)生功耗。而根據(jù)Bennett[3]的結(jié)果,假使為了讓功率不在任意的電路中被消耗,則電路必須由可逆門組成。由此,可逆電路在低功耗CMOS 設計[4]、光學計算[5]、量子計算[6]和納米技術(shù)[7]中廣受關注。
與傳統(tǒng)的不可逆電路的不同之外在于,可逆電路要求輸入、輸出之間存在雙射,并且電路中不能有扇入、扇出及反饋的存在,使可逆電路研究比不可逆電路研究更加復雜,到目前為止并沒有通用且高效的算法。對于任意大小的可逆函數(shù),尋找其最優(yōu)電路通常很困難,因此出現(xiàn)了一些啟發(fā)式的方法來求解,其中包含基于環(huán)理論、轉(zhuǎn)換、二元決策圖、搜索的方法等[8]。LUCIFER算法是DES算法的前身,其置換表為四元可逆函數(shù)。本文基于環(huán)理論方法中的相關知識,并結(jié)合文獻[1]中介紹的構(gòu)造方法開展該算法置換表的量子可逆電路實現(xiàn)研究。
全文安排如下:第2 節(jié)介紹相關基本概念及實現(xiàn)方法,第3節(jié)中討論LUCIFER 算法置換表量子電路實現(xiàn)的詳細步驟,討論部分放在第4節(jié)。
本節(jié)中,我們主要介紹實現(xiàn)量子線路的主要方法及相關基本知識。
一種量子門能實現(xiàn)一種可逆函數(shù)。廣義Toffoli門CmNOT(x1,x2,…,xm+1)表示前m比特為控制線,當且僅當每一條控制線值都為1 時,才使得目標線xm+1的結(jié)果翻轉(zhuǎn),即x1=x1,…,xm=xm,xm+1=xm+1⊕x1*x2*…*xm。構(gòu)成通用門集合的NOT門、CNOT門、Toffoli門也可以寫成C0NOT,C1NOT,C2NOT。
設Ω是由n個文字組成的集合:
Ω到自身的一個映射稱為(作用于)Ω上的一個置換,或n元置換,簡稱置換。
一般地,如果n元置換σ把n個文字中的一部分α1,α2,…,αm(m≤n) 作 如 下 變 換 :ασ1=α2,ασ2=α3,…,ασm=α1,而其余n-m個文字保持不變,則稱σ為一個m輪換,簡稱輪換,記作σ={α1,α2,…,αm}。m稱為輪換的長度。m=1 時,σ就是恒等置換。當m=2時,稱為一個對換[9]。
定理1任何一個置換都可以表示成一些不相交的輪換的乘積,而且表示法(除輪換的次序外)是唯一的[9]。
定理2每個n元置換均能表示成若干個對換的乘積,如
很明顯,若兩個輪換之間沒有公共元素,則稱它們相互獨立,相互獨立的輪換之間滿足乘法交換律[9]。
下面我們將簡要描述文獻[1]中的方法,即如何在不額外添加輔助量子比特的情況下,通過NOT門和CmNOT門來構(gòu)造量子電路。
定義1如果兩個n維向量u,s只有1 比特不同,就稱置換(u,s)為一個相鄰對換。
引理1假設u,s中有且只有1 比特Bj不同,l個比特相同且都為0,分別為Bi1,…,Bil。則有(u,s) =Ni1*…*Nil*Cj*Ni1*…*Nil。其中Ni表示第i比特上為NOT門,Cj表示第j比特為目標位,其余比特為控制位。
注意:NOT 門的乘積存在交換性,同一量子線路中的相鄰一對NOT門可以去掉。
引理2如果兩個n維向量u,s有k個比特不同,則 存 在 一 個 有 序 集 合M={d1,d2,…,dk+1},d1=u,dk+1=s,并且對于任意的i,1 ≤i≤k+1,di和di+1之間只存在1 比特差異,有(u,s)=(d1,d2)(d2,d3)…(dk,dk+1)(dk,dk-1)…(d2,d1)。
算法步驟:
規(guī)則一:檢查函數(shù)f的真值表??紤]一個給定的可逆線路的真值表,每個輸出比特有2n個值,將它們與輸入比特一一對比,如果相異數(shù)大于2n-1,則需在這個比特的線路上添加NOT門。
規(guī)則二:以一系列對換乘積的形式將可逆線路進行分解,保證最終形式中的每一個對換之間相異比特數(shù)為1。
規(guī)則三:根據(jù)引理1,將每個對換分解成NOT門和CmNOT門。
一個n量子比特的可逆線路是對稱群S2n中的一個置換,反之亦然。兩個門的級聯(lián)等價于S2n中兩個置換相乘。根據(jù)定理2 可知,任何置換群都可以用一系列的對換相乘,通過引理1,可證明一個置換可以表示成一系列量子門的級聯(lián)形式。同樣地,根據(jù)文獻[1]中給出的證明及結(jié)論,該構(gòu)造方法對于任意的n量子比特可逆函數(shù)都適用,且量子線路中至多出現(xiàn)2n·N個CmNOT 門和4n2·N個NOT 門,N表示輸出與輸出對應不同的個數(shù)。
在20 世紀60 年代后期,IBM 公司成立了一個由Horst Feistel負責的計算機密碼學研究項目,1971年設計了分組密碼算法LUCIFER,該算法分組長度為64、密鑰長度為128 位。它就是DES 算法的前身,該算法的一個置換真值表如表1所示。
表1 置換真值表
根據(jù)真值表,可以寫出置換群表示為
第一步:將B列與P列一一對比后可知,相異數(shù)分別為(10 8 8 12),依據(jù)算法規(guī)則一,則需要在第一條和第四條添加NOT門。
第二步:添加NOT 門之后的真值表如表2 所示。根據(jù)新的真值表,可以寫出置換群表示為
表2 添加NOT 門之后的置換真值表
第三步:根據(jù)定理2,可將f分解成如下對換乘積形式為
第四步:根據(jù)引理1 和引理2,寫出所有對換的表達式,即
經(jīng)過合并簡化,最終置換表分解成為54個NOT門和35個CmNOT門。電路圖表示如圖1所示。
圖1 LUCIFER 算法置換真值表的量子可逆線路圖
本文以LUCIFER算法置換表為重點,介紹了量子門及置換群中的相關理論,詳細列舉實現(xiàn)其量子可逆線路的方法及步驟,并給出線路示意圖,使讀者對LUCIFER 算法的結(jié)構(gòu)有了更深刻的認識。面對更高維度的置換表,其量子線路的復雜度如何,以及有無更高效的線路實現(xiàn)方法等,還需要進一步開展研究。