周日貴，肖天儒

（華東交通大學(xué) 信息工程學(xué)院，江西 南昌330013）

0 引 言

量子原胞自動(dòng)機(jī)作為新型納米器件首先由C.Lent等人提出，與傳統(tǒng)CMOS器件相比，它具有器件超高密度、極低功耗、克服線路共面穿越信號(hào)相互干擾等獨(dú)特的優(yōu)點(diǎn)，因此受到人們廣泛的關(guān)注和研究。近些年來(lái)，人們對(duì)量子原胞自動(dòng)機(jī)的仿真研究進(jìn)展顯著［1－3］，主要焦點(diǎn)在于如何提高仿真的速度以及仿真的精準(zhǔn)度。由于納米元件工作時(shí)是否穩(wěn)定極受溫度的影響，因此有學(xué)者提出用模擬退火的方法［4］對(duì)量子電路進(jìn)行仿真，此方法是把量子細(xì)胞半經(jīng)典化，將細(xì)胞中的電子看作是經(jīng)典力學(xué)中的粒子來(lái)進(jìn)行模擬退火的，這種方式由于增加了對(duì)當(dāng)前最優(yōu)解的記憶功能，因此對(duì)于少數(shù)量子細(xì)胞信號(hào)傳遞的模擬此方法就存在著高復(fù)雜度的計(jì)算問(wèn)題，另外，其仿真結(jié)果正確率也較低，雖然Macucci等人也提到循環(huán)退火可以提高仿真的正確率，但對(duì)于高復(fù)雜度的量子電路［5］而言，利用這種方法依然會(huì)使系統(tǒng)陷入仿真時(shí)間過(guò)長(zhǎng)的局面。遺傳算法與模擬退火算法的結(jié)合對(duì)于尋找全局最優(yōu)解具有一定實(shí)效性［6］，將其用于量子原胞自動(dòng)機(jī)仿真，可以縮短仿真時(shí)間，且在一定程度上提高了量子電路系統(tǒng)的收斂的速率，然而隨著電路規(guī)模的擴(kuò)大仿真的正確率就會(huì)明顯下降。趙曉輝等人將量子遺傳算法應(yīng)用于量子原胞自動(dòng)機(jī)仿真［7］，當(dāng)仿真過(guò)程中出現(xiàn)多極值問(wèn)題時(shí)，此方法有效降低了陷入局部最優(yōu)的概率，在一定程度上解決了仿真正確率不高的問(wèn)題。通過(guò)比較分析上述仿真方法，它們存在共同的弊端，即在處理大規(guī)模量子電路時(shí)，仿真時(shí)間過(guò)長(zhǎng)，仿真精確度不高。

本文針對(duì)量子原胞自動(dòng)機(jī)遺傳模擬退火算法應(yīng)用于較大型QCA 電路效率不高、準(zhǔn)確度較低的問(wèn)題提出了新的解決方法，它主要通過(guò)對(duì)QCA 電路中的可定態(tài)細(xì)胞定態(tài)來(lái)減小遺傳模擬退火處理問(wèn)題的規(guī)模，被減小的規(guī)模部分可利用定態(tài)規(guī)則來(lái)計(jì)算電路的狀態(tài)，這樣就可使得仿真速度更快，仿真結(jié)果更精確。

1 量子原胞自動(dòng)機(jī)概述

1.1 量子細(xì)胞

量子原胞自動(dòng)機(jī)電路的最小單元是量子細(xì)胞，量子細(xì)胞由4個(gè)量子點(diǎn)和兩個(gè)自由電子構(gòu)成，由于庫(kù)侖作用力的排斥作用，兩個(gè)自由電子更易處于對(duì)角線上的兩個(gè)量子點(diǎn)上［8］。如圖1所示，空心圓圈表示量子點(diǎn)，實(shí)心圓表示電子，電子位于左對(duì)角線上時(shí)，細(xì)胞的極化狀態(tài)為＋1，位于右對(duì)角線上時(shí)，極化狀態(tài)為－1。

圖1 量子細(xì)胞

1.2 相互作用能

量子原胞電路中的細(xì)胞負(fù)載的信號(hào)在電路系統(tǒng)處于穩(wěn)定態(tài)時(shí)應(yīng)是讓系統(tǒng)的靜電能處于最小的信號(hào)。量子電路系統(tǒng)總靜電能量的計(jì)算式［9］見(jiàn)式 （1）

其中，qi表示第i個(gè)量子點(diǎn)的電荷量，ε0與ε1分別是真空介電常數(shù)和介質(zhì)相對(duì)介電常數(shù)，rij表示量子點(diǎn)i與j 的距離。

2 定態(tài)規(guī)則與可定態(tài)細(xì)胞

2.1 3×3QCA子系統(tǒng)

王森等人提出了3×3QCA 細(xì)胞模塊化設(shè)計(jì)的方法［10］，3×3QCA 子系統(tǒng)如圖2所示。

2.2 定態(tài)規(guī)則證明

假設(shè)QCA 細(xì)胞被鎖存時(shí)極化率只存在p ＝－1 和p＝＋1兩種狀態(tài)，QCA 細(xì)胞參數(shù)按文獻(xiàn) ［7］進(jìn)行設(shè)置，細(xì)胞尺寸s＝20nm×20nm ，細(xì)胞最小間距d＝20nm ，細(xì)胞內(nèi)相鄰量子點(diǎn)間距a ＝10nm ，細(xì)胞有效影響半徑為r ＝41nm 。

圖2 QCA 模塊子系統(tǒng)

文獻(xiàn)［10］中提到相鄰兩個(gè)細(xì)胞組合共有5種配置能量ei（1≤i≤5），如圖3所示。配置能量的計(jì)算可利用式（2）

圖3 相鄰細(xì)胞不同配置

接下來(lái)，我們通過(guò)比較分析5種配置能量來(lái)確定細(xì)胞極化狀態(tài)判定的規(guī)則，此規(guī)則可以描述為

式中：f、g——可定態(tài)細(xì)胞 （位置5 細(xì)胞）的極化狀態(tài)，A＋（B＋）——2、4、6、8位置極化狀態(tài)為＋1 （－1）的個(gè)數(shù)，A×（B×）——1、3、7、9 位置極化狀態(tài)為＋1 （－1）的個(gè)數(shù)。

下面是規(guī)則的證明過(guò)程，利用式 （2）計(jì)算5種配置能量，結(jié)果見(jiàn)表1。

表1 不同細(xì)胞間距的配置能量

由表1可知e1＝－e2，e3＝e4＝－e5。假設(shè)要求極化狀態(tài)的細(xì)胞位置位于3×3QCA 子系統(tǒng)位置5 （如圖2所示）。其它位置放置極化狀態(tài)已定的細(xì)胞或不放細(xì)胞，如果系統(tǒng)中有i個(gè)e1，j個(gè)e2，m 個(gè)e3，n個(gè)e4，p 個(gè)e5，則子系統(tǒng)總能量為

步驟1 證明位置2、4、6、8的細(xì)胞對(duì)位置5細(xì)胞的影響力權(quán)值要大于1、3、7、9位置的細(xì)胞。

ie1＋je2刻畫了2、4、6、8位置細(xì)胞與位置5細(xì)胞的能量關(guān)系，因?yàn)閑1＝－e2，若2、4、6、8位置上有多個(gè)細(xì)胞，能量會(huì)相互抵消，所以只考慮只存在一個(gè)細(xì)胞的情況，此時(shí)系統(tǒng)能量有式 （6）、式 （7）兩種可能

對(duì)于式 （6），因?yàn)閑1＜0，要體現(xiàn)2、4、6、8的細(xì)胞對(duì)位置5細(xì)胞的影響力更大，則要使1、3、7、9位置的細(xì)胞與位置5的細(xì)胞能量和盡可能的大，于是有

因?yàn)閒1＜0，即1、3、7、9位置的細(xì)胞與位置5細(xì)胞能量總和最大時(shí)，子系統(tǒng)的能量也為負(fù)，說(shuō)明2、4、6、8的細(xì)胞對(duì)位置5 細(xì)胞的影響力要大于1、3、7、9 位置的細(xì)胞。

對(duì)于式 （7），因?yàn)閑2＞0，要體現(xiàn)2、4、6、8的細(xì)胞對(duì)位置5細(xì)胞的影響力更大，則要使1、3、7、9位置的細(xì)胞與位置5的細(xì)胞能量和盡可能的小，于是有

因?yàn)閒2＞0，即1、3、7、9位置的細(xì)胞與位置5細(xì)胞能量總和最小時(shí)，子系統(tǒng)的能量也為正，說(shuō)明2、4、6、8的細(xì)胞對(duì)位置5 細(xì)胞的影響力要大于1、3、7、9 位置的細(xì)胞。

步驟2 證明2、4、6、8位置不放細(xì)胞或放了細(xì)胞能量相抵消，e3、e4個(gè)數(shù)大于e5個(gè)數(shù)的系統(tǒng)能量更大，否則更小。

如果2、4、6、8位置不放細(xì)胞或放了細(xì)胞能量相抵消，則系統(tǒng)能量為

由e3＝e4＝－e5易證e3、e4個(gè)數(shù)大于e5個(gè)數(shù)的系統(tǒng)能量更大，否則更小。

2.3 可定態(tài)細(xì)胞

設(shè)位置5的細(xì)胞為要求極化狀態(tài)的細(xì)胞，那么其鄰域每個(gè)位置有4種情形：極化狀態(tài)為＋1的細(xì)胞、極化狀態(tài)為－1的細(xì)胞、未知極化狀態(tài)的細(xì)胞、沒(méi)有細(xì)胞。不防設(shè)3×3QCA 子系統(tǒng)位置5細(xì)胞鄰域所有環(huán)境為集合A，可定態(tài)細(xì)胞環(huán)境為集合P，不可定態(tài)細(xì)胞環(huán)境為集合U 。設(shè)位置2、4、6、8細(xì)胞極化狀態(tài)為＋1的細(xì)胞個(gè)數(shù)為p1，極化狀態(tài)為－1的細(xì)胞個(gè)數(shù)為n1，極化狀態(tài)未知個(gè)數(shù)為x1，位置1、3、7、9細(xì)胞極化狀態(tài)＋1的細(xì)胞個(gè)數(shù)為p2，極化狀態(tài)為－1的細(xì)胞個(gè)數(shù)為n2，極化狀態(tài)未知個(gè)數(shù)為x2。則不可定態(tài)細(xì)胞環(huán)境可表示為

由于當(dāng)x1，x2大于等于極化狀態(tài)已定的細(xì)胞個(gè)數(shù)時(shí)，即位置5細(xì)胞鄰域大部分位置細(xì)胞狀態(tài)不定，所以其極化狀態(tài)暫時(shí)無(wú)法判斷。

知U 可推出可定態(tài)細(xì)胞環(huán)境集合為P ＝A ∩U ，定義滿足環(huán)境P 的細(xì)胞為可定態(tài)細(xì)胞。

3 遺傳模擬退火算法 （gass）

3.1 編碼方法、適應(yīng)度函數(shù)與退溫函數(shù)

假設(shè)細(xì)胞存在兩種極化狀態(tài)，故編碼方法可用二進(jìn)制編碼。把QCA 電路作為一條染色體，電路中的細(xì)胞作為基因。

退溫函數(shù)采用線性函數(shù)，tk＋1＝αtk，其中α小于并極接近于1，本文設(shè)α＝0.95。

3.2 選擇、交叉和變異過(guò)程

選擇是根據(jù)適應(yīng)函數(shù)的概率分布由高到低優(yōu)先選出概率值最高的新種群的過(guò)程，交叉時(shí)采用變化交配法，由于是二進(jìn)制編碼，因此基因變異的概率較小，可設(shè)基因變異概率為Pm＝0.001。

3.3 中止規(guī)則

最大遺傳代數(shù)設(shè)為MAXGEN ，當(dāng)?shù)螖?shù)達(dá)到最大遺傳代數(shù)MAXGEN 時(shí)算法中止。

3.4 算法偽代碼描述

proc gsaa；

var g，MAXGEN，Maxpop，ej，ei，r；

‘變量定義，g表示迭代次數(shù)，MAXGEN 表示最大遺傳代數(shù)，Maxpop表示最大種群數(shù)目，ej表示新染色體的能量，ei表示舊染色體能量

4 改進(jìn)的遺傳模擬退火算法 （lgass）

4.1 可定態(tài)細(xì)胞的判定

根據(jù)式 （11）通過(guò)尋找細(xì)胞鄰域環(huán)境已知和未知極化狀態(tài)的細(xì)胞的個(gè)數(shù)來(lái)判斷細(xì)胞是否為可定態(tài)細(xì)胞。

4.2 可定態(tài)細(xì)胞極化率計(jì)算

根據(jù)定態(tài)規(guī)則對(duì)可定態(tài)細(xì)胞極化狀態(tài)進(jìn)行計(jì)算。

4.3 改進(jìn)算法偽碼描述

4.3.1 結(jié)構(gòu)體變量定義

4.3.2 函數(shù)的定義

func divByClk（circuit：cell），此函數(shù)的作用是將整個(gè)電路按時(shí)鐘域劃分成4個(gè)量子陣列。

func checkPolar（ccell：cell）：boolean，此函數(shù)用于判斷某個(gè)量子細(xì)胞是否可定態(tài)。

func calPolar（ccell：cell），此函數(shù)用來(lái)計(jì)算量子細(xì)胞的極化狀態(tài)。

func setup（ccell：cell，ncell：cell），此函數(shù)根據(jù)電路環(huán)境對(duì)某個(gè)量子細(xì)胞鄰域環(huán)境進(jìn)行設(shè)置。

func updateCircuit（），此函數(shù)用于更新電路狀態(tài)，當(dāng)某個(gè)細(xì)胞的狀態(tài)發(fā)生改變時(shí)就立即更新電路狀態(tài)。

func make（cirClk：cell，circuit：cell），此函數(shù)按時(shí)鐘域依次確定細(xì)胞極化狀態(tài)。

4.3.3 make函數(shù)偽碼

鑒于divByClk，checkPolar，calPolar，setup，update－Circuit函數(shù)代碼易于實(shí)現(xiàn)，在此只對(duì)make 函數(shù)作偽碼描述。

5 仿真實(shí)驗(yàn)與結(jié)果分析

在進(jìn)行仿真實(shí)驗(yàn)時(shí)，對(duì)量子細(xì)胞參數(shù)設(shè)置如下：細(xì)胞尺寸s＝20nm×20nm ，細(xì)胞最小間距d＝20nm ，細(xì)胞內(nèi)相鄰量子點(diǎn)間距a＝10nm ，細(xì)胞有效影響半徑為r＝41nm。仿真實(shí)驗(yàn)環(huán)境：Windows操作系統(tǒng)，Matlab工具軟件。

5.1 仿真實(shí)驗(yàn)一

為檢驗(yàn)算法的有效性，我們先對(duì)基本的邏輯電路進(jìn)行仿真，4種基本邏輯電路的設(shè)計(jì)如圖4所示。將gsaa與lgsaa分別應(yīng)用于基本電路仿真，為方便對(duì)比，假設(shè)用lgsaa算法處理的電路系統(tǒng)初始為能量最大狀態(tài)，這樣兩種算法對(duì)比得到圖5仿真結(jié)果。

限于文章篇幅，輸入細(xì)胞其它輸入信號(hào)情況在此不作詳細(xì)描述，其它輸入信號(hào)也同樣可得到正確的仿真結(jié)果。gass算法與lgass算法對(duì)4種基本的邏輯電路仿真的正確率見(jiàn)表2。

表2 基本邏輯電路gass與lgass仿真正確率比較

5.2 仿真實(shí)驗(yàn)二

為檢驗(yàn)算法的優(yōu)越性，我們將gsaa與lgsaa分別應(yīng)用于一較大規(guī)模電路 （如圖6所示）。圖7展示了此電路系統(tǒng)收斂過(guò)程兩種算法迭代次數(shù)。lgass算法在迭代次數(shù)到達(dá)100至150之間時(shí)，電路系統(tǒng)將處于能量最低狀態(tài)，而gass算法電路系統(tǒng)能量還處于較高的不穩(wěn)定狀態(tài)。

接下來(lái)，我們比較兩種算法應(yīng)用于大型電路的仿真正確率，利用gass算法與lgass算法對(duì)圖6電路進(jìn)行100次仿真，每次得到的仿真結(jié)果由QCADesigner來(lái)檢驗(yàn)，若得到的結(jié)果與QCADesigner仿真得到的結(jié)果一致，則認(rèn)為仿真正確，否則認(rèn)為仿真不正確。通過(guò)對(duì)比，兩種算法仿真正確率和最大誤差值見(jiàn)表3。

表3 gass與lgass仿真正確率比較

5.3 結(jié)果分析

由圖5和圖7可以看出，lgass算法相比于gass算法能在較少迭代次數(shù)的情況下達(dá)到電路系統(tǒng)能量較低的效果，并且lgass算法曲線波動(dòng)性明顯小于gass曲線，從而可以判斷l(xiāng)gass算法比gass算法收斂速度更快。這就克服了實(shí)際應(yīng)用中系統(tǒng)仿真長(zhǎng)時(shí)間等待的弊端。

由表2與表3可知，lgass算法在提高仿真速度的同時(shí)也大大提高了仿真的精準(zhǔn)度，對(duì)于一些基本的邏輯電路兩種算法都可在較短時(shí)間內(nèi)得到正確率高的仿真結(jié)果，其中l(wèi)gass算法仿真正確率近乎為1。對(duì)于大規(guī)模量子電路而言，在同樣的仿真時(shí)間內(nèi)，gass算法的應(yīng)用會(huì)使仿真正確率明顯下降，而lgass算法卻依然保持了較高的仿真正確率。

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

本文做的主要工作是首先提出了3×3QCA 模塊子系統(tǒng)判斷極化狀態(tài)的規(guī)則，即定態(tài)規(guī)則，并且證明了定態(tài)規(guī)則的正確性，根據(jù)規(guī)則定義了可定態(tài)細(xì)胞，然后設(shè)計(jì)了基于定態(tài)規(guī)則的局部遺傳模擬退火算法 （lgass）并將其應(yīng)用于大型QCA 電路仿真。算法中對(duì)可定態(tài)細(xì)胞的先定態(tài)操作的目的是為了減小模擬退火算法問(wèn)題的處理規(guī)模從而提高電路的仿真效率。從理論上講，遺傳模擬退火算法 （gass）對(duì)大型QCA 電路仿真是可行的，如果算法參數(shù)如遺傳代數(shù)設(shè)置足夠大，退火循環(huán)次數(shù)足夠大，那么QCA 電路仿真的正確率就會(huì)無(wú)限接近于1，然而這在實(shí)際應(yīng)用當(dāng)中不大可能。文章最后利用兩個(gè)仿真實(shí)驗(yàn)驗(yàn)證了lgass算法的有效性，相比gass算法lgass算法收斂速度更快，仿真正確率更高，更有利于大規(guī)模量子電路的仿真。

［1］Jarosaw Adam Miszczak.High－level structures for quantum computing ［J］.Synthesis Lectures on Quantum Computing，2012，4 （1）：1－129.

［2］Miszczak J A.Models of quantum computation and quantum programming languages［J］.Bulletin of the Polish Academy of Sciences：Technical Sciences，2011，59 （3）：305－324.

［3］Ganesh E N，Kishore L.Implementation of quantum cellular automata combinational and sequential circuits using majority logic reduction method ［J］.International Journal of Nanotechnology and Applications，2008，2 （1）：89－106.

［4］ZHU Haodong，ZHONG Yong.A kind of renewed simulated annealing algorithm ［J］.Computer Technology and Development，2009，19 （6）：32－35 （in Chinese）. ［朱顥東，鐘勇.一種改進(jìn)的模擬退火算法 ［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（6）：32－35.］

［5］Bibhash Sen，Manojit Dutta.An efficient multiplexer in quantum－dot cellular automata［G］.LNCS 7373：Progress in VLSI Design and Test，2012：350－351.

［6］XUE Yingchun，XU Wenbo，SUN Jun.Rectangle－packing optimization utilizing hybrid genetic algorithms［J］.Computer Engineering and Design，2007，28 （22）：5457－5460 （in Chinese）.［薛迎春，須文波，孫俊.基于遺傳模擬退火混合算法矩形包絡(luò)求解 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007，28 （22）：

5457－5460.］

［7］ZHAO Xiaohui，CAI Li，ZHANG Peng.Simulation of quantum cellular automata based on quantum genetic algorithm ［J］.Micronanoelectronic Technology，2011，48 （1）：3－9 （in Chinese）.［趙曉輝，蔡莉，張鵬.基于量子遺傳算法的量子細(xì)胞自動(dòng)機(jī)仿真方法 ［J］，微納電子技術(shù)，2011，48 （1）：3－9.］

［8］Cho H，Swartzlander EE.Adder designs and analyses for quantum－dot cellular automata ［J］.IEEE Transactions on Nanotechnology，2007，6 （3）：374－383.

［9］Zhou Rigui，Xiao Tianru.A research on simulation engines of quantum－dot cellular automata［J］.J Comput Inf Syst，2013，9 （3）：977－985.

［10］WANG Sen，CAI Li，SU Fayuan.Design method based on quantum cellular automata ［J］.Nanoelectronic Device and Technology，2007，（44）4：171－174 （in Chinese）. ［王森，蔡莉，蘇發(fā)院.基于量子細(xì)胞自動(dòng)機(jī)的設(shè)計(jì)方法 ［J］.納米器件與技術(shù)，2007，（44）4：171－174.］