基于NCV門庫的可逆邏輯門進化設計與優(yōu)化

趙曙光，崔 平，羅 霄，李智偉

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

基于NCV門庫的可逆邏輯門進化設計與優(yōu)化

趙曙光，崔 平，羅 霄，李智偉

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

提出和實現(xiàn)了一種基于遺傳算法的可逆邏輯門的設計方法。其特點是預先求出并存儲所需功能的可逆邏輯門的真值表，并對NCV基本門庫中的控制V門，控制V+門，控制非門，非門進行編碼，通過這些基本門的級聯(lián)，構成染色體暨可逆邏輯門，在逐代進化中按照既定邏輯功能和優(yōu)化目標進行適應度評估，再利用遺傳換代中的選擇，交叉，變異等功能進行遺傳操作，進而找到功能和性能均符合預定目標的可逆邏輯門。實驗結果證明，此方法的可行性、有效性，與傳統(tǒng)手工設計可逆邏輯門相比，其在求解速度和能力方面有顯著提高。

可逆邏輯門；可逆邏輯；NCV門庫；遺傳算法

量子計算機具有眾多優(yōu)點，其理論基礎和技術關鍵是可逆邏輯門以及可逆邏輯電路。可逆邏輯電路由可逆邏輯門組合與級聯(lián)構成，因此可以說可逆邏輯門的種類豐富程度直接關系到量子計算機的進步與發(fā)展。多年來，眾多種可逆邏輯門已被提出，常用的有控制非門[1]、Toffoli[2]門、Fredkin門[3]、Peres門等。隨著可逆邏輯技術的不斷發(fā)展，現(xiàn)有的可逆邏輯門的種類與功能已經(jīng)難以滿足科研與生產(chǎn)的需求。

NCV門庫中包含有控制V門，控制V+門，控制非門以及非門這4種量子基本門，當每條量子線輸入均為二元基態(tài)時，輸出卻有可能是疊加態(tài)[4-5]。量子邏輯基本門的這一特點，使得利用該門庫構建可逆邏輯門困難重重?；诹孔舆壿嬮T的3量子綜合算法相對較多[6-8]，但是基于量子非邏輯門的可逆邏輯門設計算法并不多見。盡管一些專家已經(jīng)提出了幾種基于NCV門庫的多量子綜合算法[9-12]，但是都存在一定的局限性。

基于上述問題并結合遺傳算法，本文提出了基于NCV門庫的可逆邏輯門優(yōu)化設計算法。該算法給出了新的編碼方案，簡化了算法適應度計算的復雜度，一定程度上提高了算法效率，這對新門的發(fā)現(xiàn)以及現(xiàn)有可逆邏輯門庫的擴充均有一定意義。

1 可逆邏輯門遺傳算法模型的建立

1.1 門庫器件以及其選擇

Deutsch等人已經(jīng)證明了低位量子門通過串、并聯(lián)等方式可實現(xiàn)所有量子門[13]。從理論上來說NCV門庫中的量子門完全可以實現(xiàn)所有可逆邏輯門。參照Benchmark[14]標準庫里現(xiàn)有可逆邏輯門NCV實現(xiàn)中所用到的基本門種類并以減少收索規(guī)模、提高搜索效率為目標，本文選擇非門，控制非門，控制V+門，控制V門作為設計與優(yōu)化可逆邏輯門的基石。

圖1 量子門

圖1給出了NCV門庫中量子門的圖形符號其功能概述如下：

CNOT(CN)門的函數(shù)T({c};t)：目標位t翻轉的條件是控制位c輸入為1。

除NOT門外，以上各個量子門在不滿足控制位為1的條件時，輸出值與輸入值相同。

表1 控制量子門的真值表

CV、CV+以及CN的真真值表如表1所示。其中,x1是控制端輸入;x2是受控端輸入;y1是控制端輸出;y2是受控端輸出。該表證明CV門和CV+互為共軛轉置矩陣，即這兩個量子非邏輯門自身或者彼此相連，那么該結構就可以優(yōu)化。它們的具體基本運算關系如下

V×V=V+×V+=NOT

(1)

V×V+=V+×V=I

(2)

1.2 NCV門的編碼

利用進化算法設計可逆邏輯門，需要對所選器件進行編碼。結合文獻[11]中編碼方式，本文提出了另一種編碼方式。

除非門外，NCV門庫中其余量子門均由兩部分組成，分別是控制端和受控端。根據(jù)的量子門的這一結構特點以及量子比特在通過量子門時運算的特性，本文提出的編碼方案中，也將一個量子門分成控制端和受控端兩個部分。為表述方便，本文用字符C表示量子門的控制端，編碼方案中用1表示；用字符V+、V、N分別表示量子門CV+、CV、CN的受控端，編碼方案中分別用2，3，4表示；NOT門用5表示，直通則用0表示。

對于n輸入可逆邏輯門，其每位量子門均可用一個n位列數(shù)組{…,x,…,y,… }T表示。該數(shù)組中“…”表示n-2個0；如果該量子門為NOT門，則x取0、y取5，其余情況下x、y中一個取1，另一個取2～4中的一個整數(shù)值。m組此類數(shù)組級聯(lián)，就可以表示一個 的邏輯門。這種編碼方式可使得一個復雜的可逆邏輯門完全可以用一個二維數(shù)組存儲起來。以圖2所示的Toffoli門為例，按照本文提出的編碼方案編碼，其NCV實現(xiàn)方式的染色體編碼是：chr={{1,4,0,1,4},{0,1,1,0,1},{3,0,3,2,0}}。

圖2 Toffoli門的編碼示意圖

1.3 建立遺傳算法模型

1.3.1 模型的基本元素

基因：一個基因代表一個量子門。

染色體：一個染色體由多個基因級聯(lián)組成，表示一個量子門級聯(lián)結構。

種群：種群由若干染色體組成，其實質是一個量子門級聯(lián)結構的集合，種群大小由初始生成的種群大小決定。

適應度：適應度是染色體與預期目標的符合程度，本文中表示邏輯門的功能與其預期功能符合程度。

1.3.2 適應度評估準則

對于n輸入的染色體，其適應度評估準則如下：

準則1 將初始輸入值迭代加載到染色體的各個基因計算輸出結果。既染色體頭部的第一個基因以初始輸入作為輸入，之后的基因都以其左相鄰基因的輸出作為輸入根據(jù)量子門的真值表計算輸出。最后一個基因的輸出就是染色體最終的輸出，若其等于預期輸出，則適應度增加n，記為fit1。

準則2 邏輯門的可逆性。NCV門庫中的量子門隨機生成的染色體不一定具有可逆的性質，大部分初始染色體內部還會出現(xiàn)量子糾纏現(xiàn)象即該染色體沒有完整并確定的輸出[9]。因此，把初始輸入從染色體的頭端(以圖2為例，其頭端是CV門)開始迭代得到輸出結果，然后將輸出的結果從染色體的尾端(以圖2為例，其頭端是CNOT門)開始反向迭代得到輸出結果。對比初始輸入與第二次輸出結果，如果二者相同，則適應度增加n,記為fit2。

準則3 由上述討論可知，如果染色體相鄰兩個基因相同，或者CV+、CV相連并且它們級聯(lián)方式也相同，則此染色體還可以進一步優(yōu)化。同一條染色體中這種結構每出現(xiàn)一次適應度減少1，記為fit。

按照此3條評價準則以n輸入輸出的染色體來計算，其適應度計算公式為

(3)

1.3.3 染色體內部量子糾纏的處理

NCV門庫中量子門的控制端輸入為邏輯值，即控制端的輸入均為 或者 時，通過該量子門的量子之間才不會發(fā)生量子糾纏[15]。但是隨機生成的染色體中各個量子門的級聯(lián)方式千變萬化，量子門之間運算時難免會發(fā)生糾纏。這種情況下，量子門輸出結果是隨機的，表1中通用的真值表不再生效，這將導致可逆邏輯門的設計與優(yōu)化無法繼續(xù)。

將初始輸入值迭代加載到染色體的各個基因，計算量子門個體適應度這一過程中，需要動態(tài)的處理染色體中量子糾纏現(xiàn)象，以便得到內部不發(fā)生量子糾纏的染色體。用一個全新的染色體替換當前發(fā)生量子糾纏的染色體顯然是不現(xiàn)實的，這種替換不能確保新的染色體內部不發(fā)生量子糾纏。

為解決這一難題，本文設計了一種強制變異方法：當發(fā)生量子糾纏時，在不改變基因種類的情況下隨機改該變基因的級聯(lián)方式，并重新計算該量子門的適應度，直到變異后的染色體內部不再發(fā)生量子糾纏。量子糾纏處理流程圖如圖3所示。

圖3 量子糾纏處理流程圖

1.4 遺傳算法的實現(xiàn)

本文選用輪盤賭法來實現(xiàn)對交叉變異個體的選擇。在種群適應度計算完成后程序進入交叉變異階段。

為保證變異結果能順利保留到下一代，變異與否直接發(fā)生在所選擇的兩個染色體上。如果滿足變異條件，則對該染色體進行變異處理。本設計中實現(xiàn)了兩種或不同的變異方式，一種是對單個染色體中的某個基因進行變異操作，即變異過程直接替換該基因；另一種方式是對對種群中的某個染色體進行變異操作，即直接替換掉整個染色體。兩種不同的變異方式充分保證了種群的多樣性，避免了種群早熟的不良結果。

同理，如果不滿足變異條件，則直接進入交叉階段。交叉發(fā)生在經(jīng)過變異之后的染色體對上。根據(jù)染色體的長度，在染色體上隨機選取一個交叉位置，兩個染色體在該位置互換部分基因完成交叉操作。本代交叉變異之后整個種群進入到下一代遴選，直至得到預期的結果或者程序運行到最大迭代次數(shù)這一結束條件，程序退出循環(huán)。

2 實驗結果分析

實驗在VS2012平臺上用C語言編程實現(xiàn)。

Benchmark標準庫中給出了常見可逆邏輯門的一種NCV實現(xiàn)，利用本算法可以得到該標準庫中各個邏輯門的不同的NCV實現(xiàn)形式。

2.1 Toffoli門的通用NCV構成

經(jīng)過多次實驗，本文得出如圖4所示的Toffoli門的通用NCV實現(xiàn)方式。

圖4 Toffoli門的通用NCV構成形式

該圖中G1、G2須分別選擇CV或者CV+中的一種。量子門B與C，C與D可互換位置，但不能同時互換；輸入端I3可與I1、I2互換位置，以改變受控位位置。

2.2 Fredkin門的通用NCV構成

與Toffoli門類似，實驗中也得到了多種Fredkin門的實現(xiàn)形式。圖5展示了Fredkin門的兩種通用實現(xiàn)方式。這兩種實現(xiàn)方式中G1、G2也是分別選擇CV或者CV+中的一種。方式1中量子門B與C，C與D，F(xiàn)與G可互換位置，但是B與C，C與D可不可同時互換位置；方式2中量子門B與C可互換位置其余量子門位置相對固定，不能互換。同理，兩種方式中輸入端位置可以互換，以改變控制位的相對位置。

圖5 Fredkin門的通用NCV構成形式

2.3 或異或門

該算法不僅是在已有邏輯門的異構形式設計中有較好的表現(xiàn)，在具有新功能的可逆邏輯門設計方面也有較理想的作用

(4)

式(4)定義了一種新的邏輯功能，控制位為A、B，目標位為C。該結構在功能方面實現(xiàn)了C′= (A+B)⊕C，但其具體構成方式未知。經(jīng)過計算可得該邏輯功能的真值表，如表2所示。

表2 量子邏輯門的真值表

將該真值表輸入到本文提出的算法程序中，經(jīng)過程序的運行可得到該邏輯功能的具體NCV實現(xiàn)，如圖6所示。

圖6 量子邏輯門的NCV實現(xiàn)

該實現(xiàn)中G1可選擇CV或者CV+中的任意一種。該實現(xiàn)中量子門B與C，C與D可互換位置，其余量子門位置相對固定。

事實上，經(jīng)過對實驗結果進行分析，得出結論：可逆邏輯門中相鄰的兩個量子門，如果它們的控制端在同一條線上，或者受控端在同一條線上，或者控制端與受控端都不在同一條線上，互換這兩個量子門的位置可逆邏輯門的功能不變。

3 結束語

針對NCV門庫中的量子門的特點，設計了較好的編碼方式；經(jīng)過對遺傳算法的改進，適應度評估方法的優(yōu)化，以及量子糾纏的處理，得到了得到了較為優(yōu)化的量子可逆邏輯門的自動化設計與優(yōu)化的方法。該算法不依賴先驗知識、不需要人工干預，只要給出所需要的邏輯功能真值表，程序即可生成滿足該功能的量子門級聯(lián)結構，因此其具有較高的搜索、全局優(yōu)化能力。這為可逆邏輯門庫的擴充以、現(xiàn)有可逆邏輯門的優(yōu)化及新門的設計提供了參考。

[1] Feynman R.Quantum mechanical computer[J].Optic News,1986,16(6): 11-20.

[2] Toffoli T.Reversible computing[D].MA,USA:MIT Lab for Computer Science,1980.

[3] Ekert A K.Quantum cryptography based on Bell’s theorem[J].Physics Review Letter,1991,67(6):661-663.

[4] Zheng Y Z,Ye P,Guo G C.Probabilistic implementation of non-local CNOT operation and entanglement purification [J].Chin Physics Letter,2004,21(4):9-11.

[5] Gao G L, Cai G C, Huang S S, et al. 1→N quantum controlled phase gate realized in a circuit QED system[J]. Science China Physics, Mechanics & Astronomy, 2012, 55(8):1422-1426.

[6] Fredkin E,Toffoli T.Conservative logic[J]. International Journal of Theoretical Physics,1982,21(3):219-253.

[7] 李志強,陳漢武.量子可逆邏輯電路最小代價綜合算法[J].東南大學學報,2008,38(2):249-254.

[8] Maslov D,Miler D M.Comparison of the cost metrics through investigation of the relation between optimal NCV and optimal NCT three-qubit reversible circuits[J].IET Computer & digital Techniques,2007,1(2):98-104.

[9] 陳漢武,李文騫,阮越.基于漢明距離遞減變換的可逆邏輯綜合算法[J].計算機學報,2014,8(37):1839-1845.

[10] 李志強,陳漢武,劉文杰.基于新型量子邏輯門庫的最優(yōu)NCV三量子電路快速綜合算法[J].電子學報,2013,4(4):690-697.

[11] 俞經(jīng)龍,趙曙光,王祥.可逆邏輯門進化設計方法及其CUDA實現(xiàn)[J].電子科技,2015,1(4):12-15.

[12] Wille R.Fast exact Toffoli network synthesis of reversible logic[C]. Grace:International Conference on CAD, 2007.

[13] Miller D M.Lower cost quantum gate realization of multiple-control Toffoli gate[C].PacRim:IEEE Pacific Rim Conference on Communications and Signal Processing,2009.

[14] Wille R, Groβe D, Teuber L, et al. RevLib: An online resource for reversible functions and reversible circuits[C]. Germany:International Conference on CAD, 2008.

[15] 張國鋒.量子糾纏的若干問題研究[D].太原:山西大學,2004.

Research on the Evolutionary Design and Optimization Method of Reversible Logic Gates Based on NCV Gate Library

ZHAO Shuguang，CUI Ping，LUO Xiao，LI Zhiwei

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

A design method of reversible logic gates based on genetic algorithm is proposed and implemented in this paper. Its feature is that given and stored the truth tables in advance of the needed reversible logic gate. Encoding quantum NOT, CNOT, Controlled-V and Controlled-V+ (NCV). Using the base logic gates to construct chromosomes (reversible logic gates). Evaluation fitness according to expect logic function and optimization objectives, and running genetic operations such as selection, crossover and mutation. Thus we can find the reversible logic gate which has corrected function and optimal form. The experimental results give some prove of feasibility and effectiveness of this method. This method is more advantage than traditional manual design in capability and speed.

reversible logic;reversible logic gates;NCV gate library;genetic algorithm

2016- 11- 16

國家自然科學基金(61272224)

趙曙光(1965-)，男，博士，教授。研究方向: 電子設計自動化等。崔平(1990-)，男，碩士研究生。研究方向：可逆邏輯門的自動化設計等。

10.16180/j.cnki.issn1007-7820.2017.09.001

TN79;TP302.2

A

1007-7820(2017)09-001-05