趙曙光，李智偉，王朝正，崔 平

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620)

三值Toffoli門的級(jí)聯(lián)優(yōu)化及其應(yīng)用

趙曙光，李智偉，王朝正，崔 平

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620)

三值Toffoli門是構(gòu)成三值量子電路的基本邏輯門，而三值Toffoli門是通過(guò)M-S門實(shí)現(xiàn)。文中對(duì)相鄰的三值Toffoli門的特性進(jìn)行了分析，提出并證明了三值Toffoli門級(jí)聯(lián)的化簡(jiǎn)規(guī)則，可有效減少電路的量子代價(jià)。同時(shí)在此化簡(jiǎn)方法上對(duì)現(xiàn)有的三值量子全加器進(jìn)行改良設(shè)計(jì)，量子代價(jià)有明顯減少。進(jìn)一步證明了三值Toffoli門級(jí)聯(lián)化簡(jiǎn)規(guī)則具有一般性和應(yīng)用性。

三值Toffoli門；M-S門；化簡(jiǎn)規(guī)則；全加器

1982年Feynman首次提出量子計(jì)算的概念[1-2],由于量子計(jì)算與經(jīng)典計(jì)算相比有本質(zhì)的超越，被認(rèn)為是最具有前景的計(jì)算模式之一[3]。量子邏輯系統(tǒng)可分為二值量子系統(tǒng)和多值量子系統(tǒng)，多值量子系統(tǒng)的研究雖不成熟，但是在量子加密[4]和信息處理能力[5]上優(yōu)于二量子值系統(tǒng)。而三值量子系統(tǒng)是最小的多值量子系統(tǒng)，故對(duì)三值量子系統(tǒng)的研究是對(duì)多值量子系統(tǒng)研究的基礎(chǔ)。對(duì)于三值量子電路，近十幾年來(lái)眾多研究者取得了一定的研究成果，2004年Khan設(shè)計(jì)出三值量子加法器電路[6]，2005年給出三值量子編碼器和解碼器電路[7]。2007年Khan等人設(shè)計(jì)出三值量子并行加法器和減法器[8]。這些成果對(duì)量子多值計(jì)算機(jī)的設(shè)計(jì)起到推進(jìn)作用?，F(xiàn)有三值量子電路的設(shè)計(jì)中，其中的門電路大都未經(jīng)化簡(jiǎn)，量子代價(jià)也并非最優(yōu)。本文對(duì)三值三值量子基本門的特性進(jìn)行分析，得出級(jí)聯(lián)化簡(jiǎn)的一般性方法，應(yīng)用到電路中可以有效減少量子代價(jià)。在此基礎(chǔ)上得出改進(jìn)的三值量子全加器的實(shí)現(xiàn)電路，與同類電路相比量子代價(jià)要少，可見(jiàn)此化簡(jiǎn)方法的實(shí)用性和推廣性。

1 量子信息

1.1 量子比特

經(jīng)典計(jì)算的基本信息單位是比特，在存儲(chǔ)和計(jì)算的時(shí)候用0和1表示，在計(jì)算機(jī)內(nèi)部用物理量電平的高低來(lái)表示[1]。量子信息與量子電路也是建立在類似基礎(chǔ)之上，量子比特中兩個(gè)可能狀態(tài)是|0〉和|1〉，構(gòu)成向量空間的一組正交基。一般情況下量子比特|β〉是基矢態(tài)的線性疊加，表示為

|β〉=β0|0〉+β1|1〉

(1)

其中，β0和β1為復(fù)數(shù)，且滿足歸一化性質(zhì)

(2)

一個(gè)量子比特是一個(gè)典型的微觀系統(tǒng)，比如一個(gè)原子、一個(gè)核自旋或者一個(gè)偏振的光子。

1.2 三值量子比特

三值量子比特的狀態(tài)可以用三維復(fù)向量空間的向量表示，該系統(tǒng)有3個(gè)基矢態(tài)，為|0〉、|1〉和|2〉，三值系統(tǒng)也滿足基矢態(tài)的線性疊加，即

|β〉=β0|0〉+β1|1〉+β2|2〉

(3)

其中，β0、β1和β2為復(fù)數(shù)，且滿足歸一化性質(zhì)

(4)

2 量子電路

2.1 三值量子轉(zhuǎn)換門

在三元域上，任何三值狀態(tài)的改變都可用一位三值量子轉(zhuǎn)換門來(lái)表示，共有6種一位三值量子轉(zhuǎn)換門，分別記作Z(+0)，Z(+1)，Z(+2)，Z(01)，Z(02)和Z(12)。其中Z(+0)可視為不經(jīng)過(guò)任何轉(zhuǎn)換門，化作直線，其量子代價(jià)為0，其余5種量子轉(zhuǎn)換門的量子代價(jià)均為1。任意輸入經(jīng)過(guò)轉(zhuǎn)換門后對(duì)應(yīng)的輸出如表1所示。

表1 轉(zhuǎn)換門的功能

表2表示的為一位轉(zhuǎn)換門Z1經(jīng)過(guò)一位轉(zhuǎn)換門Z2后，可將這兩個(gè)轉(zhuǎn)換門等價(jià)為某種特定轉(zhuǎn)換門。

表2 兩個(gè)一位轉(zhuǎn)換門直接相連等價(jià)表

定理1 若干個(gè)一位三值量子轉(zhuǎn)換門直接相連，可將這若干個(gè)轉(zhuǎn)換門等效為一個(gè)三值量子轉(zhuǎn)換門。

證明n個(gè)一位三值量子轉(zhuǎn)換門Z1，Z2，…，Zn按順序依次相連接，某一輸入狀態(tài)|a〉經(jīng)過(guò)這些門，輸出狀態(tài)為

|b〉=|a〉·(Z1·Z2…Zn)
=|a〉·(Z1,2…Zn)
=|a〉·(Z1,2…n)
=|a〉·Znew

(5)

得證。

2.2 M-S門

M-S門是由Muthukrishan和Stround設(shè)計(jì)出的一位或兩位量子門[5]。M-S門可以組合出任意位量子門，是常用的量子基本門，其量子代價(jià)為1。圖2(a)為一位三值M-S門，圖2(b)為兩位三值M-S門， 位上的轉(zhuǎn)換門為受控門。

圖2 三值M-S門

2.3 三值Feynman門

Khan等人設(shè)計(jì)的三值Feynman門[10]如圖3(a)所示，是一種兩位門，X1位的輸出狀態(tài)與輸入狀態(tài)相同，X2位的輸出為X1位和X2位輸入狀態(tài)的模3加運(yùn)算，即GF(3)加法。任意位數(shù)的門電路均可由M-S門組合而成，圖3(b)為三值Feynman門用M-S門實(shí)現(xiàn)的電路圖，其量子代價(jià)為4。

圖3 三值Feynman門

2.4 三位三值Toffoli門

Khan等人設(shè)計(jì)的三值Toffoli門[10]是一種三位三值量子門，如圖4(a)所示，X1位與X2位的輸出狀態(tài)與輸入狀態(tài)相同，當(dāng)X1位與X2位的輸入狀態(tài)同為|2〉時(shí)，X3位的輸出狀態(tài)為X3·Z，其余情況X3位的輸出狀態(tài)與輸入狀態(tài)相同。圖4(b)為Toffoli門通過(guò)M-S門實(shí)現(xiàn)的電路圖，其量子代價(jià)為5。

圖4 三位三值Toffoli門

擴(kuò)展的三位三值Toffoli門[7]的控制條件不限于|2〉，可以|0〉，|1〉，|2〉中的任意值，圖5(a)表示擴(kuò)展的三位三值Toffoli門,當(dāng)X1位的輸入狀態(tài)為|0〉且X2位的輸入狀態(tài)為|1〉時(shí)，X3位將經(jīng)過(guò)Z門的變換，其M-S門的實(shí)現(xiàn)原理如圖5(b)所示，量子代價(jià)為

5+2×k(0≤k≤2)

(6)

其中，k為控制狀態(tài)非2的個(gè)數(shù)。

圖5 擴(kuò)展的三位三值Toffoli門

3 三值Toffoli門的級(jí)聯(lián)化簡(jiǎn)規(guī)則

Toffoli門是構(gòu)建量子電路的常用門之一，當(dāng)量子電路的規(guī)模逐漸增大，量子代價(jià)也呈幾何倍數(shù)的增加，如何利用Toffoli門的級(jí)聯(lián)化簡(jiǎn)來(lái)減少量子代價(jià)顯得重要。在二值量子電路中已有研究Toffoli門的級(jí)聯(lián)優(yōu)化成果[11-12]，但關(guān)于三值Toffoli門的級(jí)聯(lián)化簡(jiǎn)方法并未提及，下文將介紹三位三值Toffoli門級(jí)聯(lián)化簡(jiǎn)的一般方法。

3.1 三位三值Toffoli門級(jí)聯(lián)刪除規(guī)則

兩個(gè)三位三值Toffoli門級(jí)聯(lián)，滿足何種條件時(shí)可刪除這兩個(gè)Toffoli門，圖6表示兩個(gè)三位三值Toffoli門按位級(jí)聯(lián)。

圖6 兩個(gè)三位三值Toffoli門按位級(jí)聯(lián)

定理2若兩個(gè)三位三值Toffoli門按位級(jí)聯(lián)，且兩個(gè)Toffoli門每一個(gè)控制位的控制條件一樣，且目標(biāo)位的兩個(gè)轉(zhuǎn)換門互為反相門，則可刪除這兩個(gè)Toffoli門。

證明參照?qǐng)D6，若控制位的控制條件一樣，且目標(biāo)位的兩個(gè)轉(zhuǎn)換門互為反相門(級(jí)聯(lián)后等價(jià)為Z(+0))，即

a1=b1,a2=b2,Z1·Z2=Z(+0)

(7)

可推出

(8)

等價(jià)于這兩個(gè)三位三值Toffoli門的功能剛好相反，對(duì)目標(biāo)位的輸入狀態(tài)沒(méi)有改變，可刪除這兩個(gè)三位三值Toffoli門。

得證。

3.2 三位三值Toffoli門級(jí)聯(lián)直接化簡(jiǎn)規(guī)則

結(jié)合三位三值Toffoli級(jí)聯(lián)的特性，提出如下定理。

定理3 按位級(jí)聯(lián)的兩個(gè)三位三值Toffoli門，若控制條件一致，但目標(biāo)位的受控門并非互為反相門，則可合并兩個(gè)Toffoli門，量子代價(jià)減少1/2。

證明根據(jù)條件可假設(shè)

X1=a1=b1,X2=a2=b2,Z1·Z2≠Z(+0)

(9)

X3先經(jīng)過(guò)Z1的轉(zhuǎn)換，再經(jīng)過(guò)Z2的轉(zhuǎn)換，由定理1可知，滿足控制條件時(shí)，X3經(jīng)過(guò)Z1·Z2的轉(zhuǎn)換，可轉(zhuǎn)換為圖7的電路，功能一致，但量子代價(jià)減少1/2。

采用同樣問(wèn)卷調(diào)查員工和游客，除去人口學(xué)特征外，重點(diǎn)圍繞對(duì)園區(qū)旅游的體驗(yàn)與感知共13個(gè)問(wèn)題，研究采用李克特五點(diǎn)量表進(jìn)行，其中“1”表示非常糟糕，“5”表示非常好。游客問(wèn)卷是在結(jié)束游覽之后進(jìn)行，發(fā)放時(shí)間涵蓋工作日與周末；員工問(wèn)卷則是在工作日午間就餐期間進(jìn)行。將問(wèn)卷數(shù)據(jù)錄入Execl并進(jìn)行分析，對(duì)企業(yè)員工和到訪游客樣本相關(guān)變量進(jìn)行比較分析，發(fā)現(xiàn)存在顯著性結(jié)構(gòu)差異，如圖示1。

得證。

圖7 控制條件相同的兩個(gè)三位三值Toffoli門按位級(jí)聯(lián)

定理4 兩個(gè)三位三值Toffoli門級(jí)聯(lián)(控制條件不完全一致)，若有兩個(gè)控制位在一條控制線上且控制條件都不為 ，則可以化簡(jiǎn)其中的M-S門，每有一組，量子代價(jià)減少1～2。

證明兩個(gè)三位三值Toffoli門級(jí)聯(lián)(控制條件不完全一樣)，在一條控制線上兩個(gè)控制門相連，即在M-S門實(shí)現(xiàn)電路圖上它們將有2個(gè)一位M-S門直接相連，如圖8所示，由定理1可知，可將兩個(gè)直接相連的一位M-S門化為一個(gè)一位M-S門，當(dāng)這兩個(gè)控制門的控制條件都不為 時(shí)，合并后量子代價(jià)的減少1，若互為反相門時(shí)，量子代價(jià)減少2。

得證。

圖8 兩個(gè)三位三值Toffoli門級(jí)聯(lián)的M-S門實(shí)現(xiàn)電路

3.3 三位三值Toffoli門級(jí)聯(lián)的優(yōu)化替換

對(duì)兩個(gè)三位三值Toffoli門按位級(jí)聯(lián)時(shí)的特性分析，在特定條件下，可構(gòu)造出一種新型的門電路進(jìn)行等效替換，功能一致但量子代價(jià)有所減少，且優(yōu)化效果在大多數(shù)情況優(yōu)于定理4。

首先構(gòu)造3個(gè)函數(shù)，其中x,a,b,c,d∈{0,1,2}

(10)

(11)

(12)

如圖6所示的兩個(gè)三位三值Toffoli級(jí)聯(lián)，用新型門電路等效替換需要滿足3個(gè)條件：(1)按位級(jí)聯(lián)；(2)受控位M-S門相同，即Z1=Z2=Z；(3)當(dāng)兩個(gè)Toffoli門完全一樣時(shí)，Z1·Z2≠Z(+0)。

共分為4種情況：

(1)當(dāng)a1=b1,a2=b2,Z1·Z2≠Z(+0)時(shí)，可轉(zhuǎn)換為圖9(a)所示，量子代價(jià)為

5+f(a1)+f(a2)

(13)

(2)當(dāng)a1=b1,a2≠b2時(shí)，可以轉(zhuǎn)換為圖9(b)所示, 量子代價(jià)為

9+f(a1)+f(max(a2,b2))

(14)

(3)當(dāng)a1≠b1,a2=b2時(shí)，可以轉(zhuǎn)換為圖9(c)所示, 量子代價(jià)為

9+f(max(a1,b1))+f(a2)

(15)

(4)當(dāng)a1≠b1,a2≠b2時(shí)，可以轉(zhuǎn)換為圖9(d)所示，量子代價(jià)為

11+f(max(a1,b1))+f(h(a1,b1,a2,b2))

(16)

圖9 兩個(gè)三位三值Toffoli門按位級(jí)聯(lián)優(yōu)化替換

結(jié)合兩個(gè)三位三值Toffoli門按位級(jí)聯(lián)的4種情況，可以歸納為圖10所示的綜合模板。

圖10 兩個(gè)三位三值Toffoli門按位級(jí)聯(lián)

其中點(diǎn)實(shí)線模塊為模塊A，實(shí)線模塊為模塊B，虛線模塊為模塊C。表3列出模塊A、B、C出現(xiàn)時(shí)需滿足的條件，打“√”代表出現(xiàn)，打“×”代表不出現(xiàn)。

表3 各模塊出現(xiàn)與否的條件

其中

(17)

量子代價(jià)為

5+f(max(a1,b1))+(max(a2,b2))+λ(a1,b1,a2,b2)

(18)

量子代價(jià)減少的區(qū)間為[1,9],比定理4介紹的直接級(jí)聯(lián)化簡(jiǎn)方法優(yōu)化效果更好。

由上述結(jié)論得出如下定理：

定理5兩個(gè)三位三值Toffoli門按位級(jí)聯(lián)，且受控的轉(zhuǎn)換門一樣，并且滿足兩個(gè)Toffoli門完全一樣時(shí)，目標(biāo)位的轉(zhuǎn)換門與自身而言并非反相門，則可以使用如圖10的模板進(jìn)行電路的優(yōu)化替換，功能保持一致，但量子代價(jià)有所減少。

證明若兩個(gè)三位三值Toffoli門按位級(jí)聯(lián)，當(dāng)它們完全一樣時(shí)目標(biāo)位的轉(zhuǎn)換門與自身而言不是反相門，則符合定理2，可以將這兩個(gè)門刪除。而其余情況，均可以參照?qǐng)D10的模板進(jìn)行電路的等效優(yōu)化替換。

得證。

4 三值量子全加器

4.1 三值量子全加器電路設(shè)計(jì)

加法運(yùn)算的輸入有加數(shù)、被加數(shù)和低位的進(jìn)位，輸出有和數(shù)以及向高位的進(jìn)位(最多為1)。根據(jù)這些規(guī)則，構(gòu)造出一位三值全加器的真值表，如表4所示，Xi為被加數(shù)；Yi為加數(shù)；Ci為低位的進(jìn)位；Si為和數(shù)；Ci+1為向高位的進(jìn)位。和數(shù)計(jì)算公式為

(18)

進(jìn)位計(jì)算公式為

(19)

根據(jù)真值表，發(fā)現(xiàn)有多種情況將會(huì)產(chǎn)生進(jìn)位，利用擴(kuò)展的三位三值Toffoli門可實(shí)現(xiàn)該功能，和數(shù)的計(jì)算方法如式(18)所示，三值Feynman門可實(shí)現(xiàn)三進(jìn)制加法運(yùn)算。基于這些原理設(shè)計(jì)出一位三值量子全加器[14-15]，如圖11所示。n位三值量子全加器是一位三值量子全加器的n次迭代，如圖12所示。

圖11 一位三值量子全加器

圖12 n位三值全加器

4.2 三值量子全加器電路優(yōu)化及分析

圖12所示的一位三值全加器，該電路可以進(jìn)行優(yōu)化，圖中的門①和門②可以利用定理5進(jìn)行優(yōu)化替換，減少3個(gè)量子代價(jià)；門③和門④的可以利用定理4化簡(jiǎn)，減少2個(gè)量子代價(jià)，門⑤和門⑥之間存在直接相連的M-S門，可以利用定理1化簡(jiǎn)，從而減少2個(gè)量子代價(jià)。優(yōu)化前量子代價(jià)總和為34[15],優(yōu)化后的一位三值量子全加器的電路實(shí)現(xiàn)如圖13所示，量子代價(jià)總和為27，合計(jì)減少7個(gè)量子代價(jià)。

圖13 一位三值量子全加器的優(yōu)化實(shí)現(xiàn)電路

基于提出的優(yōu)化規(guī)則，對(duì)一位三值全加器的電路實(shí)現(xiàn)進(jìn)行了優(yōu)化設(shè)計(jì)，量子代價(jià)合計(jì)27。量子代價(jià)方面，與文獻(xiàn)[14]對(duì)比量子代價(jià)要少21，與文獻(xiàn)[15]對(duì)比量子代價(jià)減少了7。輔助線方面，也比文獻(xiàn)[14]要少2條。

由于n位全加器是一位全加器電路的n次迭代，n位三值量子全加器的量子代價(jià)為27n，輔助線為2n條。對(duì)比量子代價(jià)和輔助線，參照表5可知，與同類型電路相比，本文設(shè)計(jì)的n位三值量子全加器擁有最優(yōu)的性能。

表5 n位三值全加器設(shè)計(jì)的性能對(duì)比

5 結(jié)束語(yǔ)

提出并證明了三值量子邏輯門級(jí)聯(lián)的優(yōu)化規(guī)則，并得出一種通用性優(yōu)化模板，基于這些規(guī)則和提出的優(yōu)化模板，應(yīng)用到三值量子全加器上，得到目前使用三值Toffoli門和三值Feynman門設(shè)計(jì)的最優(yōu)的三值量子全加器，為三值量子電路的優(yōu)化提供了積極地借鑒作用。

[1] Nielsen M A,Chuang I L.Quantum computation and quantum information[M].Cambridge:Cambridge University Press,2000.

[2] Richard P Feynman.Simulating physics with computers[J].International Journal of Theoretical Physic,1982,21(6):467-488.

[3] Ashikhmin A,Knill E.Nonbinary quantum stab-ilizer codes[J].IEEE Transactions on Information Theory,2001,47(7):3065-3072.

[4] 孟穎,魏曉馬,汪磊,等.量子加密技術(shù)的物理基礎(chǔ)和理論體系[J].電子制作,2014,19(2):243-243.

[5] Muthuk Rishnan,Stround C R.Multivaluved logic gates for quantum computation[J].Physical Review A,2000,62(5):1-8.

[6] Mozammel H A Khan.Quantum realization of ternary adder circuits[C].Korea:Proceedings of Third International Conference on Electrical and Computer Engineering,2004.

[7] Miller D M,Maslov D,Dueck G W.Synthesis of quantum multiple-valued circuits[J].Journal of Multiple-Valued Logic Soft Computing,2006,12(5-6):1-28.

[8] Mozammel H A Khan,Marek A Perkowski.Q-uantum ternary parallel adder/subtractor with p-artially-look-ahead carry[J].Journal of Systems Architecture,2007,1(7):453-464.

[9] Khan M.Design of reversible/Quantum ternary multiplexer and demultiplexer[J].Engineering Letters,2006,13(2):265-269.

[10] Khan M H,Perkowski M A.Multi-output Ga-lois field sum of products synthesis with new quantum cascades[C].Moskov:Proceedings of the 33rd International Symposium on Multiple Valued Logic,2003.

[11] 程學(xué)云,管致錦,張海豹,等.基于規(guī)則的可逆Toffoli電路優(yōu)化算法[J].計(jì)算機(jī)科學(xué),2013,40(10):32-38.

[12] 方聰,趙曙光,夏凱祥.基于變換的可逆邏輯電路量子代價(jià)優(yōu)化方法[J].電子科技,2014,27(12):166-169.

[13] Lu Hongjun,Zhang Zhike,Xie Guangjun.A quantum error-correction circuit based on c-yclic code[J].Wuhan University Journal of Natural Sciences,2013,18(5):413-417.

[14] Khan M H A,Perkowski M A.Quantum tern-ry parallel adder/subtractor with partially-look-ahead carry[J].Journal of Systems Architecture,2007,53(7):453-464.

[15] 王冬,朱長(zhǎng)江,張曉蕾.三值量子全加器設(shè)計(jì)[J].電子學(xué)報(bào),2014,42(7):1452-1456.

Optimization of Ternary Toffoli Gate’s Cascade and Application

ZHAO Shuguang,LI Zhiwei,WANG Chaozheng,CUI Ping

(School of Information Science and Technology,Donghua University,Shanghai 201620,China)

Ternary Toffoli gate is the basic logic gate in the ternary quantum circuit.Ternary Toffoli gate can be realized by M-S gate, the paper analyzed and summarized relationship between adjacent ternary Toffoli gates, proposed and proven the simplification rules of ternary Toffoli gate’s cascade, quantum costs have been decreased by the simplification rules. In addition, we make improvement on ternary quantum full adder, and quantum costs of this quantum full adder have been decreased. It also proved the validity and application of the simplification rules.

ternary Toffoli gate;M-S gate;simplification rules;full adder

2016- 11- 21

國(guó)家自然科學(xué)基金 (61272224)；上海市教委創(chuàng)新重點(diǎn)項(xiàng)目(1488068)

趙曙光(1965-)，男，博士，教授，博士生導(dǎo)師。研究方向：進(jìn)化電路設(shè)計(jì)。李智偉(1992-)，男，碩士研究生。研究方向：可逆邏輯綜合。

10.16180/j.cnki.issn1007-7820.2017.12.004

TN79+1;TP306.1

A

1007-7820(2017)12-011-06