陳 華，傅美容

（1.中國電子學(xué)會辦公室，北京 100036；2.北京聯(lián)合大學(xué)特殊教育學(xué)院特殊教育系，北京 100101）

1 研究背景

如果數(shù)字組合邏輯電路將每個輸入模式映射到唯一的輸出模式，則稱該電路為可逆電路［1］。根據(jù)Landauer［2］的證明，不管底層技術(shù)如何實現(xiàn)，如果使用傳統(tǒng)的不可逆邏輯門必定會產(chǎn)生功耗。而根據(jù)Bennett［3］的結(jié)果，假使為了讓功率不在任意的電路中被消耗，則電路必須由可逆門組成。由此，可逆電路在低功耗CMOS 設(shè)計［4］、光學(xué)計算［5］、量子計算［6］和納米技術(shù)［7］中廣受關(guān)注。

與傳統(tǒng)的不可逆電路的不同之外在于，可逆電路要求輸入、輸出之間存在雙射，并且電路中不能有扇入、扇出及反饋的存在，使可逆電路研究比不可逆電路研究更加復(fù)雜，到目前為止并沒有通用且高效的算法。對于任意大小的可逆函數(shù)，尋找其最優(yōu)電路通常很困難，因此出現(xiàn)了一些啟發(fā)式的方法來求解，其中包含基于環(huán)理論、轉(zhuǎn)換、二元決策圖、搜索的方法等［8］。LUCIFER算法是DES算法的前身，其置換表為四元可逆函數(shù)。本文基于環(huán)理論方法中的相關(guān)知識，并結(jié)合文獻(xiàn)［1］中介紹的構(gòu)造方法開展該算法置換表的量子可逆電路實現(xiàn)研究。

全文安排如下：第2 節(jié)介紹相關(guān)基本概念及實現(xiàn)方法，第3節(jié)中討論LUCIFER 算法置換表量子電路實現(xiàn)的詳細(xì)步驟，討論部分放在第4節(jié)。

2 方法介紹

本節(jié)中，我們主要介紹實現(xiàn)量子線路的主要方法及相關(guān)基本知識。

2.1 CmNOT 門

一種量子門能實現(xiàn)一種可逆函數(shù)。廣義Toffoli門CmNOT(x1，x2，…，xm+1)表示前m比特為控制線，當(dāng)且僅當(dāng)每一條控制線值都為1 時，才使得目標(biāo)線xm+1的結(jié)果翻轉(zhuǎn)，即x1=x1，…，xm=xm，xm+1=xm+1⊕x1*x2*…*xm。構(gòu)成通用門集合的NOT門、CNOT門、Toffoli門也可以寫成C0NOT，C1NOT，C2NOT。

2.2 置換群

設(shè)Ω是由n個文字組成的集合：

Ω到自身的一個映射稱為（作用于）Ω上的一個置換，或n元置換，簡稱置換。

一般地，如果n元置換σ把n個文字中的一部分α1，α2，…，αm(m≤n) 作 如 下 變 換 ：ασ1=α2，ασ2=α3，…，ασm=α1，而其余n-m個文字保持不變，則稱σ為一個m輪換，簡稱輪換，記作σ={α1，α2，…，αm}。m稱為輪換的長度。m=1 時，σ就是恒等置換。當(dāng)m=2時，稱為一個對換［9］。

定理1任何一個置換都可以表示成一些不相交的輪換的乘積，而且表示法（除輪換的次序外）是唯一的［9］。

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

很明顯，若兩個輪換之間沒有公共元素，則稱它們相互獨立，相互獨立的輪換之間滿足乘法交換律［9］。

2.3 方法步驟

下面我們將簡要描述文獻(xiàn)［1］中的方法，即如何在不額外添加輔助量子比特的情況下，通過NOT門和CmNOT門來構(gòu)造量子電路。

定義1如果兩個n維向量u，s只有1 比特不同，就稱置換(u，s)為一個相鄰對換。

引理1假設(shè)u，s中有且只有1 比特Bj不同，l個比特相同且都為0，分別為Bi1，…，Bil。則有(u，s) =Ni1*…*Nil*Cj*Ni1*…*Nil。其中Ni表示第i比特上為NOT門，Cj表示第j比特為目標(biāo)位，其余比特為控制位。

注意：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ī)則二：以一系列對換乘積的形式將可逆線路進(jìn)行分解，保證最終形式中的每一個對換之間相異比特數(shù)為1。

規(guī)則三：根據(jù)引理1，將每個對換分解成NOT門和CmNOT門。

2.4 算法可行性

一個n量子比特的可逆線路是對稱群S2n中的一個置換，反之亦然。兩個門的級聯(lián)等價于S2n中兩個置換相乘。根據(jù)定理2 可知，任何置換群都可以用一系列的對換相乘，通過引理1，可證明一個置換可以表示成一系列量子門的級聯(lián)形式。同樣地，根據(jù)文獻(xiàn)［1］中給出的證明及結(jié)論，該構(gòu)造方法對于任意的n量子比特可逆函數(shù)都適用，且量子線路中至多出現(xiàn)2n·N個CmNOT 門和4n2·N個NOT 門，N表示輸出與輸出對應(yīng)不同的個數(shù)。

3 實現(xiàn)過程

在20 世紀(jì)60 年代后期，IBM 公司成立了一個由Horst Feistel負(fù)責(zé)的計算機(jī)密碼學(xué)研究項目，1971年設(shè)計了分組密碼算法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，寫出所有對換的表達(dá)式，即

經(jīng)過合并簡化，最終置換表分解成為54個NOT門和35個CmNOT門。電路圖表示如圖1所示。

圖1 LUCIFER 算法置換真值表的量子可逆線路圖

4 討論

本文以LUCIFER算法置換表為重點，介紹了量子門及置換群中的相關(guān)理論，詳細(xì)列舉實現(xiàn)其量子可逆線路的方法及步驟，并給出線路示意圖，使讀者對LUCIFER 算法的結(jié)構(gòu)有了更深刻的認(rèn)識。面對更高維度的置換表，其量子線路的復(fù)雜度如何，以及有無更高效的線路實現(xiàn)方法等，還需要進(jìn)一步開展研究。