俞經(jīng)龍，趙曙光，王 祥

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

隨著可逆電路研究的深入，出現(xiàn)了眾多可逆電路的綜合方法［1－2］，但這些設計方法普遍針對整個邏輯電路進行綜合優(yōu)化設計，對作為其基礎構件量子邏輯門的研究甚少，而基礎邏輯門的最優(yōu)化將直接影響量子邏輯電路的整體優(yōu)化程度。因此，若能對其進行自動進化，獲得性能更好、邏輯功能更齊全和量子代價最小的門結構，將對整個電路的優(yōu)化設計起到重要作用。

本文基于NCV門庫［3］，利用遺傳算法對可逆邏輯門進行優(yōu)化設計。同時，為了充分發(fā)揮遺傳算法運用在可逆邏輯門優(yōu)化設計的優(yōu)勢［4］，利用(NVIDIA)CUDA并行計算架構［5］，將可逆邏輯門的進化設計方法改編為并行化的算法，令其以“CPU與GPU協(xié)同處理”，借助GPU的并行處理能力，在不增加額外成本的情況下大幅提升了程序的運行速度和相應的求解能力。這對于可逆邏輯門的設計優(yōu)化，新型門的發(fā)現(xiàn)及對現(xiàn)有門庫的擴充均有著重要意義。

1 可逆邏輯門進化設計方案

1.1 門級器件庫選用

Deutsch和Lloyd等人已證明所有的量子門在物理實現(xiàn)上均可有基本的一位和二位量子門的實現(xiàn)［6］。同時，為減少問題的搜索規(guī)模和提高求解效率，并考慮量子邏輯門的通用性，本文選擇包含以下4種基本量子門的NCV門庫。

CNOT門T({c};t):當控制位c為1時，目標位t才翻轉。

Controlled－V門V({c};t):若控制位c為1，目標位t根據(jù)酉矩陣所描述的操作執(zhí)行。

Controlled－V+門V+({c};t):當控制位c為1，目標位t根據(jù)酉矩陣所描述的操作執(zhí)行?？煽闯鯲+門是V門的共軛轉置矩陣。

1.2 編碼

利用遺傳算法對可逆邏輯門進行優(yōu)化設計。如對NOT、CNOT、Controlled－V、Controlled －V+，基本門構建通用且完備的門庫進行編碼，其會隨著電路輸入的增大，所需的量子門庫規(guī)模將以指數(shù)冪增加，且在功能判定時，隨著輸入位數(shù)的增大，其電路的真值表規(guī)模以2的指數(shù)冪增大，這也增加了電路功能判定的難度。為此，文中設計了一種新的編碼方法，可避免建立量子門庫的過程，且通用性較強。

根據(jù)信息位傳輸路徑對電路的分級，每級電路需包含一個量子門，且用一組實數(shù)位串表示，該位串分為3部分:(1)表示本級電路的功能，用量子門編號表示，設定0表示NOT門，1表示CNOT門，2表示Controlled－V門，3表示Controlled－V+門。(2)表示各量子門的目標位所在連線編號。(3)表示各量子門的所在連接線的具體位置，若直通則用－1表示，否則在其相應的位置上寫入所在的連線編號。以圖1所示的Toffoli門的NCV實現(xiàn)為例分析其編碼為Initial_chromosome={320 －12，1101 －1，32 －112，1101 －1，22 －112}。此染色體包含5個基因，每個基因由5個數(shù)字組成:第1位數(shù)字表示所選基本門的種類，第2位數(shù)字表示目標位所在位置，后3位則表示量子門所在連線的具體位置。

圖1 Toffli門的NCV實現(xiàn)

1.3 適應度評估

由于可逆邏輯門進化是典型的多目標優(yōu)化問題，本文對適應度函數(shù)進行了專門設計，利用“加權和”形式，將多目標優(yōu)化問題轉換為單目標進化算法求解問題，其中涉及到以下子目標:功能適應度

量子代價適應度

量子門數(shù)適應度

垃圾位適應度

將多目標優(yōu)化問題轉化為單目標進化算法求解的等效問題，其實現(xiàn)形式為

其中，fiti(X)為個體X關于子目標fi(X)的歸一化適應度;wi(t)為第t代種群中的非負權重系數(shù)，其取值應滿足

在此基礎上，為兼顧全部子目標，通過借鑒參照人工神經(jīng)網(wǎng)絡中的后向傳播(Back－Progagation)學習算法，令權重系數(shù)wi隨fi(X)的優(yōu)化程度動態(tài)更新，如式(7)所示

2 算法的CUDA實現(xiàn)

2.1 遺傳算法的并行化模型

當種群規(guī)模較大時，將其分解為若干個子種群，并為每個子種群分配一個線程塊，鑒于線程塊之間不能進行數(shù)據(jù)通信，而遺傳算法中的選擇、交叉和變異操作均有數(shù)據(jù)交換。為解決此矛盾，當每個線程塊完成子種群進化任務后，讓各自線程塊的最優(yōu)染色體遷移到相鄰的線程中去，并淘汰其中最差的染色體，但其只能是單方向遷移。對于單個子種群，每一代的最優(yōu)染色體，將與上一代的最優(yōu)染色體相比較，若染色體的適應度不如上一代的最優(yōu)染色體，則上一代的最優(yōu)染色體將取代當代的最差染色體，以防最優(yōu)染色體在進化過程中被淘汰［4］。

如種群大小為512×128=65 536，開啟128個線程塊，每個線程塊中有512個線程。一個線程塊負責一個子種群的進化任務。當進化完成后，在CPU串行代碼中完成最優(yōu)染色體的遷移。種群結構模型如圖2所示。

2.2 遺傳算子的并行化實現(xiàn)

(1)選擇算子并行化。選用輪盤賭選擇法，可將其中的求適應度總和與求個體相對適應度這兩個步驟并行化實現(xiàn)。在求適應度的總和步驟上，其求和操作可用歸約算法并行實現(xiàn)。如子種群規(guī)模為512，串行求和需執(zhí)行511次加法操作，然并行化求和只需9次循環(huán)求解，便可得到適應度總和。理論上，其計算速度是串行求解的511/9倍［7－8］。另外，在求個體的相對適應度時，開啟512個線程同時運行，分別將個體的適應度除以適應度總和，子種群512個個體只需一次求解，便可得到個體的相對適應度。理論上，其計算速度是串行計算的512倍，選擇操作具體流程如圖3所示。

圖3 并行化選擇操作流程圖

(2)交叉算子并行化。交叉操作在CUDA并行化中的具體實現(xiàn)如下:首先將子種群中的512個染色體順序打亂，為保證交叉的隨機性，其順序的打亂由隨機數(shù)實現(xiàn)。然后產(chǎn)生隨機數(shù)表示隨機概率，與交叉率Pc進行比較，若隨機數(shù)小于交叉率，則進行交叉，否則不交叉。

在線程塊中開啟256個線程分別進行交叉操作。讓第個染色體和第256個染色體交叉，第2個染色體和第257個染色體交叉，依次類推，交叉操作一次即可完成。理論上，其交叉執(zhí)行速度是串行化實現(xiàn)的256倍，其具體操作流程如圖4所示。

圖4 并行化交叉操作流程圖

(3)變異算子并行化。針對電路編碼的特點，設計了3種染色體變異操作量子門的功能變異、有無量子門變異及量子門的位置變異。其CUDA具體實現(xiàn)如下:首先在每個線程中產(chǎn)生隨機數(shù)作為隨機概率，將其與變異概率Pm相比較，若隨機概率小于變異概率Pm，則代表某個基因達到了變異條件，再產(chǎn)生0～2的隨機數(shù)分別代表上述3種不同方式的變異，并根據(jù)此隨機數(shù)選擇相應形式的變異。子種群共有512個個體，開啟512個線程同時進行變異操作。理論上，其變異執(zhí)行速度是串行化實現(xiàn)的512倍。具體流程如圖5所示，每個線程執(zhí)行相同的操作。

圖5 并行化變異操作流程圖

3 實驗結果與分析

實驗在VS2010平臺上用CUDA C語言編程實現(xiàn);所用顯卡為Nvidia公司GeForce GT610。

3.1 Toffoli門的NCV實現(xiàn)

參數(shù)設置:設置種群大小為128×512=65 536，染色體長度為25，即一個染色體包含5個基因，基因長度為5位，最大進化代數(shù)是MaxGeneration=10;遺傳操作參數(shù)，交叉概率Pc=0.65、變異概率Pm=0.1;適應度函數(shù)中各子函數(shù)的權重系數(shù)初值為w1(0)=0.4，w2(0)=w3(0)=w4(0)=0.2，即滿足 α =0.9。

運行結果:320－12，1101－1，32－112，1101－1，22－112。根據(jù)上述可逆電路的編解碼方案，得到Toffoli門NCV實現(xiàn)的具體電路，如圖6所示。

圖6 Toffoli門的NCV實現(xiàn)

由于 NOT、CNOT、controlled－V與 Controlled－V+量子代價均為1，可得Toffoli門物理實現(xiàn)的最小量子代價為5。

3.2 可逆基準電路3_17的NCV實現(xiàn)

設置種群大小為128×512=65 536，染色體長度為100，即一個染色體包含10個基因，基因長度為5位，其他參數(shù)設置如上。所得結果為:02－1－12，120－12，200 1－1，300 －12，11 －112，2001 －2，22 －112，22 －112，1101－1，32－112。通過解碼得到可逆基準電路3_17的NCV實現(xiàn)具體電路，如圖7所示。

圖7 可逆基準電路3_17的NCV實現(xiàn)

可逆基準電路3_17的NCT門庫實現(xiàn)如圖8所示，其量子代價消耗為14，而本文基于NCV門庫的電路進化算法所生成的最優(yōu)電路的量子代價為10。經(jīng)細致研究，發(fā)現(xiàn)Toffoli門可用Peres門和CNOT門級聯(lián)得到。同時，可用NCV門庫生成3種類似Peres門的新型量子可逆邏輯門，其構造如圖9所示。

圖8 可逆基準電路3_17的NCT實現(xiàn)

圖9 基于NCV的新型量子可逆邏輯門構造圖

其中，G1、G2、G3處分別選擇 Controlled－V 或 Controlled－V+門，根據(jù) I0、I1、I2的給定值判定選擇何種門，實現(xiàn)不同的邏輯功能，如表1所示。

表1 新型量子邏輯門庫的構造表

選用易于物理實現(xiàn)的NOT、CNOT、Controlled－V、Controlled－V+基礎門構建完備且通用的門庫，根據(jù)可逆邏輯電路的特點，采用位串的編碼方案，并改進了適應度評估方法，使可逆邏輯門優(yōu)化得到較為全面的評估。鑒于遺傳算法本質上具有并行特性，將其改造為CUDA架構下的并行算法應用于可逆邏輯門優(yōu)化。最后通過兩個具體實例，驗證了其設計方案的可行性。本文所提出的將遺傳算法與CUDA結合應用于可逆邏輯門的優(yōu)化，不僅可發(fā)揮電路進化設計的全局優(yōu)化能力，且明顯提高了電路的搜索速度。進化設計無需依賴先驗知識和人工干預的條件下通過進化來獲得滿足預定目標的電路與系統(tǒng)結構，這對新型門的發(fā)現(xiàn)及對現(xiàn)有門庫的擴充均具有重要意義。

［1］管致錦.可逆邏輯綜合［M］.北京:科學出版社，2011.

［2］Lu Hongjun，Guo Junwang，Peng Fei，et al.N － bit quantum gate accomplished by two － bit quantum gates［J］.Chinese Journal of Quantum Electronics，2010，27(1):26 －30.

［3］Barenco A，Bennett CH，Cleve R，et al.Elementary gates for quantum computation［J］.Elementary Gates for Quantum Computation，1995，52(5):3457 －3466.

［4］Tan Caifeng，Ma Anguo，Xing Zuocheng.Genetic algorithms parallel implementation study based on CUDA platform［J］.Computer Engineering and Science，2009，31(A1):68 －72.

［5］張舒，褚艷麗.GPU高性能運算之CUDA［M］.北京:北京水利水電出版社，2009.

［6］Miller D M.Lower cost quantum gate realizations of multiple－ control Toffoli gates［C］.PacRim:IEEE Pacific Rim Conference on Communications，Computers and Signal Processing，2009:308 －313.

［7］高磊，陳則王.基于PPRM表達式的快速可逆邏輯電路綜合算法［J］.電子科技，2011，24(10):75 －76，80.

［8］董亞清.基于GPU的線性調頻信號脈沖壓縮算法實現(xiàn)［J］.電子科技，2013，26(12):12 －16.