研究量子可逆邏輯電路優(yōu)化設(shè)計問題,提出一種量子可逆邏輯電路自動合成的方法�？墒褂�"圖"的結(jié)構(gòu)來對量子可逆邏輯電路進(jìn)行編碼,并且專門設(shè)計了幾種變異操作算子來直接修改"圖"的結(jié)構(gòu),并實(shí)現(xiàn)了利用"圖"編碼的克隆選擇,最終完成了量子可逆邏輯電路的自動合成。實(shí)驗(yàn)結(jié)果表明所提出的量子可逆邏輯電路自動合成的方法是可行的,具有較高的合成效率,能夠以較快的收斂速度獲取所需合成的量子可逆邏輯電路的的最優(yōu)解。 

【文章來源】：計算機(jī)仿真. 2012,29(12)北大核心CSCD

【文章頁數(shù)】：6 頁

【部分圖文】：

通用7}di(7(G7)

。則輸出值變化規(guī)則如下:若?m∈{1，2，…，n－1}，xim=0?∏n－1k=1xik=0，則yin=xin;若?m∈{1，2，…，n－1}，xim=1?∏n－1k=1xik=1，則yin=xin．圖1Toffoli量子門如圖1所示，根據(jù)控制端數(shù)量的不同，Toffoli量子門可以分為非門、控制非門、標(biāo)準(zhǔn)Toffoli門以及通用Toffoli門四種。其中●表示控制端，⊕表示受控端。本文為了描述方便，將端子總數(shù)量為N的Toffoli量子門稱為N階TOF門。量子可逆邏輯電路的邏輯功能可以用真值表表示，也可以用整數(shù)集合的置換表示。例如，圖2的(a)和(b)分別對應(yīng)的是一個三變量的量子可逆邏輯電路的電路圖及其真值表。圖2三變量量子可逆邏輯電路及其真值表為了描述方便，文中將該電路的邏輯功能簡單表示為以下形式:F(0，1，2，3，4，5，6，7)=(4，5，6，1，0，3，2，7)．3量子可逆邏輯電路的自動合成3．1量子可逆邏輯電路編碼方案的設(shè)計量子可逆邏輯電路由輸入、輸出、量子邏輯門以及連接線路四部分構(gòu)成。在用“圖”編碼的量子可逆邏輯電路中，輸入、輸出以及量子邏輯門分別用輸入頂點(diǎn)、輸出頂點(diǎn)、中間頂點(diǎn)表示，連接線路則用有向邊表示。輸入頂點(diǎn)、輸出頂點(diǎn)和中間頂點(diǎn)統(tǒng)稱為頂點(diǎn)，通過有向邊來實(shí)現(xiàn)頂點(diǎn)之間的連接即可構(gòu)成“圖”。一個頂點(diǎn)v可以定義為Name［I，O，Q］，Name為頂點(diǎn)v的編號，I代表頂點(diǎn)v的輸入端的數(shù)量，O代表頂點(diǎn)v的輸出端的數(shù)量，Q是預(yù)先設(shè)定的頂點(diǎn)v的功能碼。在本文所提出的電路自動合成方法中，被編碼的頂點(diǎn)類型如表1所示。表1被定義的頂點(diǎn)類型頂點(diǎn)描述門的個數(shù)IOQ輸入0010輸出0101一階TOF門1112二階TOF門1223三階TOF門1334四階TOF門1445五階TOF門1556—414—

改圖結(jié)構(gòu)的變異操作算子。這些變異操作算子的介紹如下:①添加頂點(diǎn)操作:該算子執(zhí)行的操作是往“圖”中添加一個新的中間頂點(diǎn)，中間頂點(diǎn)的類型以及添加的位置均隨機(jī)選取，新的中間頂點(diǎn)的輸入端和輸出端通過添加有向邊與其它頂點(diǎn)建立連接。例如，在圖3的頂點(diǎn)E與頂點(diǎn)F之間添加一個新的頂點(diǎn)G［3，3，4］，其操作結(jié)果如圖4(a)所示。②修改頂點(diǎn)操作:該算子執(zhí)行的操作是隨機(jī)選中“圖”的一個中間頂點(diǎn)并對其類型進(jìn)行修改。中間頂點(diǎn)類型的修改會導(dǎo)致該頂點(diǎn)輸入端和輸出端的數(shù)量變化，因此，還需要添加或者刪除部分有向邊。例如，將圖3中的頂點(diǎn)D［3，3，4］修改成為D［2，2，3］，其操作結(jié)果如圖4(b)所示。③頂點(diǎn)互換操作:該算子執(zhí)行的操作是隨機(jī)選中“圖”的兩個中間頂點(diǎn)并將這兩個中間頂點(diǎn)的位置互換。在交換兩中間頂點(diǎn)位置后，還需要對兩個中間頂點(diǎn)的輸入邊和輸出邊執(zhí)行相應(yīng)的修改操作。例如，將圖3中的頂點(diǎn)D［3，3，4］與頂點(diǎn)F［1，1，2］位置互換，操作完成后其結(jié)果如圖4(c)所示。圖4修改圖結(jié)構(gòu)的變異操作算子④刪除頂點(diǎn)操作:該算子執(zhí)行的操作是隨機(jī)選中“圖”中的一個中間頂點(diǎn)并將其刪除。另外，所有與該頂點(diǎn)相連接的有向邊也將被刪除，被刪除的有向邊所連接的其它頂點(diǎn)之間則通過添加有向邊來建立新的連接。例如，將圖3中的頂點(diǎn)E刪除，其操作結(jié)果如圖4(d)所示。⑤有向邊互換操作:該算子執(zhí)行的操作是首先隨機(jī)選中“圖”中的一個中間頂點(diǎn)，然后再隨機(jī)選中該頂點(diǎn)的一個控制端，最后將該控制端和受控端這兩個端子的輸入邊的起始位置進(jìn)行互換，并且將這兩個端子的輸出邊的終止位置進(jìn)行互換。例如，將圖3中頂點(diǎn)E［3，3，4］的編號為1的控制端和編號為3的受控端所連接的有向邊進(jìn)行互換，其操作結(jié)果如圖4(e)所示。6)替換評估種群Ac

【參考文獻(xiàn)】：
期刊論文
[1]基于位運(yùn)算的量子可逆邏輯電路快速綜合算法[J]. 李志強(qiáng),陳漢武,李文騫.  計算機(jī)科學(xué). 2008(03)
[2]基于Reed-Muller量子可逆邏輯電路的綜合快速算法[J]. 李志強(qiáng),陳漢武.  揚(yáng)州大學(xué)學(xué)報(自然科學(xué)版). 2006(04)



本文編號：3455379