LUCIFER 算法置換表的量子可逆線路實(shí)現(xiàn)

陳 華，傅美容

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

1 研究背景

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

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

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

2 方法介紹

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

2.1 CmNOT 門

一種量子門能實(shí)現(xiàn)一種可逆函數(shù)。廣義Toffoli門CmNOT(x1，x2，…，xm+1)表示前m比特為控制線，當(dāng)且僅當(dāng)每一條控制線值都為1 時(shí)，才使得目標(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個(gè)文字組成的集合：

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

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

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

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

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

2.3 方法步驟

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

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

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

注意：NOT 門的乘積存在交換性，同一量子線路中的相鄰一對(duì)NOT門可以去掉。

引理2如果兩個(gè)n維向量u，s有k個(gè)比特不同，則 存 在 一 個(gè) 有 序 集 合M={d1，d2，…，dk+1}，d1=u，dk+1=s，并且對(duì)于任意的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的真值表。考慮一個(gè)給定的可逆線路的真值表，每個(gè)輸出比特有2n個(gè)值，將它們與輸入比特一一對(duì)比，如果相異數(shù)大于2n-1，則需在這個(gè)比特的線路上添加NOT門。

規(guī)則二：以一系列對(duì)換乘積的形式將可逆線路進(jìn)行分解，保證最終形式中的每一個(gè)對(duì)換之間相異比特?cái)?shù)為1。

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

2.4 算法可行性

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

3 實(shí)現(xiàn)過(guò)程

在20 世紀(jì)60 年代后期，IBM 公司成立了一個(gè)由Horst Feistel負(fù)責(zé)的計(jì)算機(jī)密碼學(xué)研究項(xiàng)目，1971年設(shè)計(jì)了分組密碼算法LUCIFER，該算法分組長(zhǎng)度為64、密鑰長(zhǎng)度為128 位。它就是DES 算法的前身，該算法的一個(gè)置換真值表如表1所示。

表1 置換真值表

根據(jù)真值表，可以寫出置換群表示為

第一步：將B列與P列一一對(duì)比后可知，相異數(shù)分別為（10 8 8 12），依據(jù)算法規(guī)則一，則需要在第一條和第四條添加NOT門。

第二步：添加NOT 門之后的真值表如表2 所示。根據(jù)新的真值表，可以寫出置換群表示為

表2 添加NOT 門之后的置換真值表

第三步：根據(jù)定理2，可將f分解成如下對(duì)換乘積形式為

第四步：根據(jù)引理1 和引理2，寫出所有對(duì)換的表達(dá)式，即

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

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

4 討論

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