王藝臻, 管致錦,2*, 管海宇

(1 南通大學(xué)信息科學(xué)技術(shù)學(xué)院, 江蘇 南通 226019;2 江蘇省專用集成電路重點(diǎn)實(shí)驗(yàn)室, 江蘇 南通 226019)

0 引 言

量子電路綜合源于對(duì)量子計(jì)算機(jī)的研究。隨著量子信息技術(shù)的發(fā)展,量子邏輯綜合的問題得到越來越多的關(guān)注。在量子電路邏輯綜合問題的研究中,不只是為了找到量子電路有效的級(jí)聯(lián)方法,同時(shí)還要求綜合結(jié)果中盡可能找到實(shí)現(xiàn)量子電路具有的最低量子代價(jià)和最少量子門數(shù)。

在量子計(jì)算技術(shù)實(shí)現(xiàn)過程中,受到諸多實(shí)際限制。流行的一些量子技術(shù)要求只有相鄰的量子位才能產(chǎn)生相互影響[1],量子位被約束到沿著某一陣列,并且僅在相鄰位置之間的量子位彼此交互,這種結(jié)構(gòu)稱為線性最近鄰(Liner nearest neighbor,LNN)[2]結(jié)構(gòu)。

為了滿足量子技術(shù)的LNN 約束,構(gòu)建LNN 架構(gòu)的量子電路。迄今為止,已有幾種將非LNN 架構(gòu)量子電路轉(zhuǎn)化為LNN 架構(gòu)量子電路的方法[2-5]。在非LNN 架構(gòu)的量子電路中可以通過添加交換門以達(dá)到目標(biāo)位和控制位相近鄰的目的,或使用換線操作來構(gòu)造線性最近鄰結(jié)構(gòu)的量子電路,Chakrabarti 等[3]運(yùn)用尋求最短路徑的方法對(duì)量子電路線順序的重排序來求解LNN 架構(gòu)的量子電路。為了降低由于線性最近鄰增加的量子代價(jià),Saeedi 等[4]提出了一種模板匹配的思路以消除量子電路中的冗余交換門,達(dá)到減少量子電路的量子代價(jià)的目的;對(duì)于在非LNN 架構(gòu)的量子電路中,通過添加大量的交換門使其轉(zhuǎn)換為線性最近鄰架構(gòu)的量子電路中,在此過程中優(yōu)化交換門的數(shù)量也是降低量子代價(jià)的方法之一。如何在實(shí)現(xiàn)LNN 結(jié)構(gòu)的量子電路中添加交換門的數(shù)量最少、量子電路的量子代價(jià)最小,是相關(guān)研究最關(guān)注的問題。

為了構(gòu)造LNN 架構(gòu)下的最優(yōu)量子電路,本文完成的工作主要包括:(1)為了降低電路的最近鄰代價(jià)(Nearest neighbor cost,NNC),使用量子電路最優(yōu)評(píng)估算法對(duì)整個(gè)電路線的順序進(jìn)行全排列,找出最近鄰代價(jià)最小的量子電路;(2)為了使原始的量子電路達(dá)到線性最近鄰結(jié)構(gòu),需要在(1)的基礎(chǔ)上完成效果最佳的添加交換門方法,實(shí)現(xiàn)對(duì)量子電路線性最近鄰結(jié)構(gòu)的轉(zhuǎn)換,方便電路的物理實(shí)現(xiàn);(3)為了降低量子電路的量子代價(jià),使添加的交換門數(shù)量盡可能少,提出了解決量子電路優(yōu)化問題的相關(guān)算法。

1 基本概念與相關(guān)理論

1.1 量子邏輯綜合

量子邏輯綜合[4],就是用給定的量子邏輯門,按照量子電路無扇出、無反饋、滿足量子電路實(shí)現(xiàn)技術(shù)要求等約束條件和限制,實(shí)現(xiàn)相應(yīng)的量子電路,并使得在某種統(tǒng)一代價(jià)模型條件下優(yōu)化量子電路,使其量子代價(jià)盡可能小。

1.2 量子邏輯門

組成量子電路的基本元素是量子邏輯門。在量子電路的計(jì)算模型中,一個(gè)量子門(或稱量子邏輯門)是一個(gè)基本的操作,基本的量子門來自相應(yīng)的量子門庫。此處采用的量子門庫為NCV 門庫[5]。由文獻(xiàn)[6]可知,由NOT 門、CNOT 門、controlled-V 門、controlled-V+門構(gòu)成的NCV 門庫對(duì)一般量子電路是完備的,即可以使用NCV 門庫構(gòu)造任意量子電路。

NCV 門庫包含一個(gè)單量子通用邏輯門(NOT 門)、一個(gè)雙量子通用邏輯門(CNOT 門)、兩個(gè)雙量子通用量子門(controlled-V 門,controlled-V+門),如Fig.1 所示。

1.3 量子代價(jià)

量子計(jì)算的時(shí)間取決于量子電路中門的數(shù)量以及實(shí)現(xiàn)每個(gè)門所需物理操作的數(shù)量,將其稱為量子代價(jià)[6]。外部環(huán)境的干擾會(huì)導(dǎo)致量子系統(tǒng)的退相干,所以量子計(jì)算必須在有限的相干時(shí)間內(nèi)完成。這就要求量子電路的量子代價(jià)最小化,實(shí)現(xiàn)某一特定功能的量子代價(jià)最小的電路稱為最優(yōu)電路[7]。

此處采用NCV-111 量子代價(jià)標(biāo)準(zhǔn)[8],即認(rèn)為NCV 門庫中每個(gè)門的量子代價(jià)都為1,由NCV 門庫構(gòu)造的電路的量子代價(jià)是電路中門的數(shù)量,也就是電路的深度。

圖1 NCV 門庫Fig.1 NCV gate library

1.4 量子電路

量子電路由量子門和其相應(yīng)的信息通路構(gòu)造而成。n量子比特電路可以表示成n條水平線的形式,從上往下依次記為l1,l2,··· ,ln;量子門按照從左到右在電路中的位置(可用從左到右的垂線表示)依次執(zhí)行,該位置分別記為h1,h2,··· ,hm。

用Un(c,t,k)表示n水平線的電路(n輸入/輸出電路)中的一個(gè)量子門,其中U表示門的類別,n表示n水平線的量子電路,c表示其控制位所在的水平線,t表示其目標(biāo)位所在的水平線,k表示門所在電路從左到右的位置(即垂線)。Fig.2 為一個(gè)含有m個(gè)量子門的n量子比特電路圖,其中虛線框中的門可表示為Un(j,i,k)。不帶有任何量子門的電路稱為恒等電路。

圖2 電路中量子門的位置表示Fig.2 Representation of location of gate in circuits

1.5 交換門

交換門即SWAP 門,是一個(gè)有兩目標(biāo)位、沒有控制位的量子門,記為交換門的作用是交換量子電路中平行線的位置,即在量子電路中經(jīng)過SWAP 門作用后的兩目標(biāo)位的量子比特狀態(tài)發(fā)生了交換。添加交換門可以使量子電路中某些非近鄰量子門轉(zhuǎn)化為近鄰量子門,但同時(shí)也會(huì)使原來的電路平行線順序被打亂,也可能會(huì)增加電路的量子代價(jià)。

一個(gè)交換門可以通過三個(gè)二量子位的最近鄰量子門實(shí)現(xiàn),如Fig.3 所示。由此可知,一個(gè)交換門的量子代價(jià)相當(dāng)于三個(gè)二量子位的量子門的量子代價(jià),即量子代價(jià)為3。因此,一般量子電路通過添加交換門轉(zhuǎn)換為線性最近鄰電路時(shí),為了降低電路的量子代價(jià),需要盡可能減少交換門使用的數(shù)量[9,10],或者通過相關(guān)規(guī)則[11]消除冗余的交換門。

在n條量子比特量子電路中,如果存在交換門S(li,lj,k)和S(li,lj,k+1),稱這兩個(gè)交換門為冗余交換門對(duì)。如果兩個(gè)交換門為冗余交換門對(duì),則該冗余交換門對(duì)可以從該量子電路中移除,如Fig.4 所示。

圖3 SWAP 門的最近鄰實(shí)現(xiàn)Fig.3 The nearest neighbor implementation of SWAP gate

1.6 全局換線

由NCV 門庫構(gòu)成的量子電路中,在對(duì)量子電路的輸入/輸出值沒有影響的前提條件下,把對(duì)于量子電路水平線之間的順序交換的一組操作稱為全局換線。全局換線操作可以對(duì)量子電路中的所有量子門產(chǎn)生影響,或拉近量子門目標(biāo)位與控制位的距離,或拉遠(yuǎn)量子門目標(biāo)位與控制位距離,即縮小或增大量子門的NNC 代價(jià)值。

定理1 在由NCV 門庫構(gòu)成的量子電路中,單個(gè)非近鄰量子門轉(zhuǎn)換為近鄰量子門時(shí)所添加交換門的最少數(shù)量等于該非近鄰量子門的NNC 代價(jià)值。Fig.5 是一個(gè)非近鄰量子門添加最小數(shù)量的交換門轉(zhuǎn)換為近鄰量子門的示例。

添加交換門的最小數(shù)量與非近鄰量子門NNC 代價(jià)值之間的關(guān)系為

式中Sc為添加交換門的最小數(shù)量,Gnnc為單個(gè)量子門的NNC 代價(jià)。

證明:

在由NCV 門庫構(gòu)成的量子電路中,若存在一個(gè)非近鄰量子門Un(li,lj,k),則|i-j| ＞1。由交換門的定義可知,需要至少添加|i-j|-1 個(gè)交換門,使得該非近鄰量子門轉(zhuǎn)換為近鄰量子門,即所添加交換門的最小數(shù)量為|i-j|-1,根據(jù)非近鄰量子門的NNC 代價(jià)的定義,該非近鄰量子門的NNC 代價(jià)值為|i-j|-1。

由上述分析可知,NCV 門庫構(gòu)成的量子電路中,單個(gè)非近鄰量子門轉(zhuǎn)換為近鄰量子門時(shí)所添加的交換門最少數(shù)量等于該非近鄰量子門的NNC 代價(jià)值。

定義1在由NCV 門庫構(gòu)成的量子電路中,若存在某一量子門可以通過比較i和j的數(shù)值大小關(guān)系,來確定該量子門的高/低量子位。如果i＜j,那么li表示低量子位,lj表示高量子位;如果i＞j,那么lj表示低量子位,li表示高量子位;如果i=j,那么該量子門為NOT 門,NOT 門不存在高/低量子位。

圖4 SWAP 門的化簡Fig.4 Simplification of SWAP gate

圖5 最小的SWAP 門添加數(shù)量Fig.5 The minimal number of additive swap gates

定義2階梯結(jié)構(gòu),在量子電路中若存在x個(gè)交換門滿足jx=i(x+1)關(guān)系,把交換門構(gòu)成的這種結(jié)構(gòu)稱為階梯結(jié)構(gòu),如Fig.6 所示。

圖6 SWAP 門構(gòu)成的階梯結(jié)構(gòu)Fig.6 Ladder structure of SWAP gate

在由NCV 門庫構(gòu)成的量子電路中,單個(gè)非近鄰量子門在轉(zhuǎn)換成近鄰量子門時(shí),該量子門的某一量子位在添加交換門時(shí),將非近鄰量子門轉(zhuǎn)換成近鄰量子門時(shí)所添加的最少交換門個(gè)數(shù)稱為階梯層數(shù)。在由NCV 門庫構(gòu)成的量子電路中,單個(gè)非近鄰量子門在轉(zhuǎn)換成近鄰量子門時(shí)只允許在高/低量子位的一側(cè)添加交換門的操作稱為階梯型添加交換門,階梯型添加交換門的數(shù)量取決于階梯層數(shù)。階梯型添加交換門方法又可以分為上階梯添加交換門方法和下階梯添加交換門方法,如Fig.7 所示。

規(guī)則由NCV 門庫構(gòu)成的量子電路中,對(duì)單個(gè)非近鄰量子門的某一量子位添加交換門構(gòu)成階梯結(jié)構(gòu)時(shí),如果可以與量子電路中已存在的交換門構(gòu)成冗余交換門對(duì),那么可以將冗余交換門對(duì)從量子電路中移除,且此時(shí)該量子位處于量子位相消狀態(tài);如果不能與量子電路中已存在的交換門構(gòu)成冗余交換門對(duì),則該量子位處于量子位關(guān)閉狀態(tài)。

圖7 添加SWAP 門到上階梯結(jié)構(gòu)(a)和下階梯結(jié)構(gòu)(b)的方法Fig.7 Methods of adding SWAP gate to upper ladder structure(a)and lower ladder structure(b)

2 基于預(yù)評(píng)價(jià)的線性最近鄰量子邏輯綜合算法

2.1 綜合算法

所提出綜合算法從兩個(gè)方面優(yōu)化最近鄰量子電路。一方面,在換線過程中使量子電路的量子門盡量保持近鄰結(jié)構(gòu),綜合評(píng)估量子電路的線性最近鄰代價(jià)值和混亂值最優(yōu)結(jié)果,從而使添加的交換門盡可能少。提出了一種啟發(fā)式算法來評(píng)估量子電路NNC 代價(jià)值與混亂值和的最小結(jié)果集合,在這個(gè)結(jié)果集中的量子電路,本身就具有線性最近鄰代價(jià)小、混亂值小的特點(diǎn)。由定理1 知,對(duì)結(jié)果集中的量子電路添加交換門時(shí)交換門的個(gè)數(shù)必然也會(huì)小。另一方面,對(duì)非近鄰量子門添加交換門操作時(shí),考慮該量子門在當(dāng)前量子電路中所處的環(huán)境,使新添加的交換門盡可能多地與量子電路中已存在的交換門產(chǎn)生冗余交換門對(duì),然后再消除該冗余交換門對(duì),以達(dá)到減少量子電路中交換門的目的。

圖8 電路劃分示意圖Fig.8 Schematic diagram of circuit division

對(duì)于一個(gè)已知的非近鄰量子電路,以電路中從左到右第一個(gè)非近鄰量子門為中軸,該非近鄰量子門左側(cè)的量子電路級(jí)聯(lián)網(wǎng)絡(luò)為Nl(不包括該非近鄰量子門);該非近鄰量子門右側(cè)的量子電路部分為Nr(包括該非近鄰量子門);Nm是為了使Nl與Nr兩個(gè)局部量子電路級(jí)聯(lián)起來所需要的一組只含交換門的量子電路。Fig.8 是按照這種依據(jù)劃分量子電路結(jié)構(gòu)的一個(gè)局部實(shí)例?；靵y值是指Nl與Nr兩部分量子電路級(jí)聯(lián)所需要的一組只含交換門量子電路Nm的交換門個(gè)數(shù),最小混亂值是指Nm結(jié)構(gòu)中交換門個(gè)數(shù)的最小數(shù)值。

具體算法描述如下:

第一步:初始化Nl為空、Nm為空、Nr=N。

第二步:掃描,由量子電路Nr的輸入端開始,尋找量子電路的第一個(gè)非近鄰量子門(即量子電路中第一個(gè)近鄰代價(jià)不為0 的量子門),若存在則設(shè)為gl,執(zhí)行第三步,否則執(zhí)行第七步。

第三步:以該量子門gl為界,gl左側(cè)的量子電路為Nl(不包括gl),gl與其右側(cè)的量子電路部分為Nr。

第四步:換線,對(duì)量子電路Nr進(jìn)行非重復(fù)全局換線操作,產(chǎn)生量子電路集合Nr(i)和交換門組集合Nm(i),i表示集合中的第幾個(gè)元素,下同。

第五步:近鄰化,把量子電路集合Nr(i)中的第一個(gè)非近鄰門gl(i)轉(zhuǎn)化為近鄰門,采用添加交換門算法處理,算法處理完成后將i值相同的Nm(i) 與Nr(i)量子電路級(jí)聯(lián)。

第六步:計(jì)算并選擇qc值,每次近鄰化操作,計(jì)算Nr(i)量子代價(jià)qc(i) 的值;最終選擇使得相應(yīng)qc(i)值最小的Nr(i)作為Nr(如果是多個(gè)量子代價(jià)最小值,選擇其中一個(gè)),然后轉(zhuǎn)至第二步。

第七步:整理,對(duì)已經(jīng)構(gòu)造好的線性最近鄰量子電路進(jìn)行最終的冗余交換門排查檢測(cè),消除量子電路中一些冗余的交換門。

第八步:算法結(jié)束。

2.2 量子電路最優(yōu)評(píng)估算法

由NCV 門庫構(gòu)成的量子電路中,在量子電路輸入/輸出真值保持不變的前提條件下,通過啟發(fā)式算法(多次利用全局換線操作)對(duì)量子電路NNC 代價(jià)值與混亂值的和進(jìn)行評(píng)估,求出最小結(jié)果集。

具體算法描述如下:

第一步:初始化,計(jì)算量子電路Nr的NNC 代價(jià)值,運(yùn)用最小混亂值算法求出Nm結(jié)構(gòu)的最小混亂值;將上述兩個(gè)值求和記為SUM,SUM 為最小值標(biāo)記變量。

第二步:換線,對(duì)量子電路Nr進(jìn)行一次全局換線操作。

第三步:計(jì)算,計(jì)算量子電路Nr的NNC 代價(jià)值,運(yùn)用最小混亂值算法求出Nm結(jié)構(gòu)的最小混亂值;將上述兩個(gè)值求和記為SUM(i),i代表量子電路Nr進(jìn)行的第i次非重復(fù)的換線操作。

第四步:比較,將每次計(jì)算出的SUM(i)值與最小值SUM 標(biāo)記變量進(jìn)行比較,如果SUM(i)的值小于或者等于該標(biāo)記變量,那么將SUM(i)值相對(duì)應(yīng)的Nl(i)、Nm(i)、Nr(i)局部量子電路一同暫時(shí)存入最優(yōu)結(jié)果集棧中,并且將SUM(i)的值賦值給最小值SUM 標(biāo)記變量,然后執(zhí)行第五步;如果SUM(i)的值大于該標(biāo)記變量,直接執(zhí)行第五步。

第五步:判斷循環(huán)是否結(jié)束,判斷量子電路Nr是否完成了全部的換線操作,如果換線操作全部完成則循環(huán)結(jié)束執(zhí)行第六步,否則執(zhí)行第四步。

第六步:將最優(yōu)結(jié)果集棧中的Nl、Nm、Nr局部量子電路從棧中取出并級(jí)聯(lián)起來記為L(i)。

第七步:算法結(jié)束。

2.3 求最小混亂值算法

為了找到一種合適的Nm結(jié)構(gòu)去級(jí)聯(lián)Nl與Nr,以解決量子電路線序的重新排布問題并計(jì)算出Nm的混亂值,此處給出一種求最小混亂值算法。最小混亂值算法基于“逆序數(shù)”的思想,已知兩種線數(shù)相同的任意線序集origin、target,在這兩個(gè)線序集中,線序重新排布能且僅能通過添加SWAP 門完成,當(dāng)origin線序重新排布為target 線序時(shí)至少需要添加t個(gè)門,t即最終結(jié)果,即為最小混亂值。算法的主要思想即t值的計(jì)算,設(shè)理想的電路線順序用數(shù)組target[n]表示,當(dāng)前的電路線順序用數(shù)組origin[n]表示,計(jì)算所得線序中單個(gè)元素的逆序數(shù)用數(shù)組t[n]表示,逆序數(shù)結(jié)果之和記為t,即為最小混亂值。

具體算法描述如下:

第一步:從n=0 開始,讀取origin[n]的元素。

第二步:判斷讀取的元素是否為origin[n]的最后一個(gè)元素,如果不是最后一個(gè)元素,執(zhí)行第三步;否則執(zhí)行第五步。

第三步:將origin[n]在target[n]數(shù)組中的位置信息存儲(chǔ)在t[n]中。

第四步:刪除target[n]數(shù)組中該位置上的元素(后續(xù)位置元素前移);執(zhí)行第二步。

第五步:刪除target[n]中全部元素;計(jì)算t[n]中所有元素和,記為t。

第六步:算法結(jié)束。

例如:origin[n] = {d,c,b,a},target[n] = {a,b,c,d},origin[0] =d,origin[n]中第一個(gè)元素編號(hào)為0,查找d在target[n]中位置為3,即t[0] = 3,然后將origin[0]對(duì)應(yīng)的字母d從target[n]中刪除,對(duì)剩余的元素重新從0 開始編號(hào),這是一次完整的操作。按照上述方法不斷地進(jìn)行查找與刪除,直到讀取完origin[n]最后一個(gè)元素,此時(shí)target[n]中的元素將被完全刪除,t[n]中的所有元素求和記為t,t即為最小混亂值。

2.4 添加交換門算法

提出了一種對(duì)非近鄰量子門添加交換門的方法,可以準(zhǔn)確地計(jì)算出每一個(gè)非近鄰量子門是否具有可以刪除的冗余交換門對(duì),并能計(jì)算出可以刪除多少對(duì)冗余交換門對(duì)。利用添加交換門算法就可以得到添加最少的交換門,從而得到量子代價(jià)最小的量子電路。

在算法中,盡可能在對(duì)非近鄰量子門添加交換門的同時(shí),與該量子電路中已經(jīng)存在的交換門組合成一種冗余交換門對(duì),這樣不但可以在對(duì)該非近鄰量子門添加交換門時(shí)減少一個(gè)交換門代價(jià),還能消除該量子電路中的一個(gè)原有交換門。

Nm結(jié)構(gòu)中的交換門與添加交換門算法中添加的交換門,可以產(chǎn)生一些冗余交換門對(duì),將其從量子電路中移除,可以達(dá)到降低量子代價(jià)的目的。

具體算法描述如下:

第二步:判斷低量子位的量子狀態(tài),如果處于量子關(guān)閉狀態(tài),執(zhí)行第五步。

第三步:計(jì)算其量子位相消層數(shù)i,添加相應(yīng)的i個(gè)交換門,并消除這i組冗余交換門對(duì),更新gl量子門近鄰代價(jià)nl的值。

第四步:判斷當(dāng)前nl的值是否為0,如果是則轉(zhuǎn)第七步。

第五步:判斷高量子位的量子狀態(tài),如果處于量子關(guān)閉狀態(tài),執(zhí)行第六步;否則,執(zhí)行第三步。

第六步:根據(jù)nl的值,添加必要的最少的交換門,使非近鄰量子門變成近鄰化。

第七步:算法結(jié)束。

3 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證算法的有效性和可行性并對(duì)算法的實(shí)際性能進(jìn)行分析,所提出算法均使用標(biāo)準(zhǔn)C++語言實(shí)現(xiàn)。測(cè)試環(huán)境為64 位Windows 7 操作系統(tǒng),Intel(R)Core(TM)i5-2450M CPU@2.50 GHz 處理器,內(nèi)存為4 GB。使用revlib[12]中的benchmark 電路進(jìn)行測(cè)試,測(cè)試數(shù)據(jù)共31 組,分別涵蓋3～8 線的量子電路,測(cè)試數(shù)據(jù)中量子門數(shù)量在0～50 之間。Table 1 給出了此處的實(shí)驗(yàn)結(jié)果與具有代表性的文獻(xiàn)[7]的對(duì)比分析。表中Benchmark 為標(biāo)準(zhǔn)量子電路名稱,n為量子電路線數(shù),Gate 為量子門的數(shù)量(不包含一元量子門),S為在量子電路線序不變的前提條件下普通構(gòu)造LNN 架構(gòu)添加交換門的數(shù)量,s-1 為參考文獻(xiàn)[7]中的算法為構(gòu)造LNN 架構(gòu)添加的交換門數(shù)量,s-2 為所提出算法構(gòu)造LNN 架構(gòu)添加的交換門數(shù)量,%s-1 為參考文獻(xiàn)[7]中的算法為構(gòu)造LNN 架構(gòu)添加的交換門數(shù)量的優(yōu)化率,%s-2 為所提出算法構(gòu)造LNN 架構(gòu)添加的交換門數(shù)量的優(yōu)化率,Time-1 為參考文獻(xiàn)[7]在CPU 內(nèi)運(yùn)行時(shí)間(單位為s),Time-2為所提出算法CPU 內(nèi)運(yùn)行時(shí)間(單位為s),%t為所提出算法相比參考文獻(xiàn)[7]算法在CPU 內(nèi)運(yùn)行時(shí)間的優(yōu)化率,qc為量子電路的量子代價(jià)值,○表示參考文獻(xiàn)[7]中沒有做到實(shí)驗(yàn),而本文做的一些量子電路優(yōu)化實(shí)驗(yàn)。

表1 實(shí)驗(yàn)對(duì)比結(jié)果Table 1 Experimental comparison results

從Table 1 中可以看出,所提出算法在8 線以內(nèi),CPU 運(yùn)行時(shí)間都在“s”數(shù)量級(jí)以內(nèi),算法在運(yùn)行時(shí)間上的優(yōu)化效果顯著,平均時(shí)間優(yōu)化率達(dá)到99.9%以上。從對(duì)量子電路添加交換門數(shù)量的對(duì)比分析發(fā)現(xiàn),在相同的24 測(cè)試數(shù)據(jù)中,有4 組實(shí)驗(yàn)數(shù)據(jù)添加交換門數(shù)量比文獻(xiàn)[7]少(其中1 組實(shí)驗(yàn)數(shù)據(jù)添加交換門數(shù)量比文獻(xiàn)[7]少3 個(gè);2 組實(shí)驗(yàn)數(shù)據(jù)添加交換門數(shù)量比文獻(xiàn)[7]少6 個(gè);1 組實(shí)驗(yàn)數(shù)據(jù)添加交換門數(shù)量比文獻(xiàn)[7]少11 個(gè));10 組實(shí)驗(yàn)數(shù)據(jù)添加交換門數(shù)量與文獻(xiàn)[7]相同;10 組實(shí)驗(yàn)數(shù)據(jù)添加交換門數(shù)量比文獻(xiàn)[7]略高(其中3 組實(shí)驗(yàn)數(shù)據(jù)添加交換門數(shù)量比文獻(xiàn)[7]多1 個(gè);4 組實(shí)驗(yàn)數(shù)據(jù)添加交換門數(shù)量比文獻(xiàn)[7]多2 個(gè);3 組實(shí)驗(yàn)數(shù)據(jù)添加交換們數(shù)量比文獻(xiàn)[7]多3 個(gè))。

Fig.9 為所提出算法與文獻(xiàn)[7] 中算法在構(gòu)建不同規(guī)模量子電路的LNN 架構(gòu)過程中減少插入的SWAP 門數(shù)量的對(duì)比圖,橫軸代表量子電路的規(guī)模,縱軸代表該算法相較于普通方法構(gòu)造LNN 架構(gòu)降低添加的SWAP 門數(shù)量;如圖例中所示,點(diǎn)型柱狀圖代表所提出算法的實(shí)驗(yàn)結(jié)果,網(wǎng)格型柱狀圖代表文獻(xiàn)[7]中算法的對(duì)比結(jié)果。從圖中可以看出,對(duì)于3 線量子線路,所提出算法降低的SWAP 門數(shù)量略低于文獻(xiàn)[7];對(duì)于4 ～5 線的量子電路,所提出算法降低的SWAP 門數(shù)量高于文獻(xiàn)[7];相比于文獻(xiàn)[7]只能處理5 線以內(nèi)的量子電路,所提出算法適用的量子電路規(guī)模為4 ～8 線,且隨著量子電路規(guī)模的增加,所提出算法在構(gòu)建LNN 架構(gòu)過程中減少插入的SWAP 門數(shù)量呈上升趨勢(shì),相較于文獻(xiàn)[7]具有明顯優(yōu)勢(shì)。結(jié)合Table 1 中的數(shù)據(jù)進(jìn)行分析,所提出算法添加交換門數(shù)量的優(yōu)化率穩(wěn)定且優(yōu)化效果良好,平均優(yōu)化率達(dá)到為62.41%,算法可以處理的量子門數(shù)量級(jí)別也可以更高;在搜索空間呈指數(shù)增長的前提條件下,所提出算法的CPU 運(yùn)行時(shí)間也具有明顯優(yōu)勢(shì)。

所提出算法可以應(yīng)用于包含MCT 門或Toffoli 門的級(jí)聯(lián)電路,雖然其解決的問題是針對(duì)NCV 門庫構(gòu)成的二量子位量子電路,但算法的適用性已經(jīng)做了相應(yīng)擴(kuò)展,可以滿足對(duì)revlib 中所有數(shù)據(jù)測(cè)試要求。在NCV-111 量子代價(jià)標(biāo)準(zhǔn)[8]基礎(chǔ)上研究量子電路線性最近鄰問題,近鄰化過程中算法的量子代價(jià)的變化,取決于近鄰化過程中添加的交換門數(shù)量。近鄰化過程中插入的交換門數(shù)量最小,其量子代價(jià)亦即最小。近鄰化過程中,也可以使用如Fig.3 所示CNOT 門的組合方式替代SWAP 門,每個(gè)CNOT 門的量子代價(jià)是交換門量子代價(jià)的1/3,但由于所提出算法改造后使用CNOT 門組合進(jìn)行近鄰化,每次需要使用3個(gè)CNOT 門,所以量子代價(jià)總體上不會(huì)發(fā)生變化。

圖9 降低SWAP 門數(shù)對(duì)比圖Fig.9 Swap gate reduction comparison chart

4 結(jié) 論

提出了一種將非近鄰量子門轉(zhuǎn)換為最近鄰狀態(tài)添加交換門的方法,算法將近鄰化過程中新添加的交換門盡可能與原量子電路中已經(jīng)存在的交換門組成“冗余交換門對(duì)”,通過準(zhǔn)確計(jì)算出非近鄰量子門是否具有可以刪除的冗余交換門對(duì)以及可以刪除冗余交換門對(duì)的數(shù)量,得到近鄰化過程中所需添加的最少的交換門數(shù)。這種方法在降低新添加的交換門數(shù)量的同時(shí)消除電路中原有的交換門,能夠以較短的時(shí)間花費(fèi)得到量子代價(jià)最小的最近鄰量子電路。由于應(yīng)用啟發(fā)式算法時(shí)將一些量子電路線序以中間變量的形式保存在內(nèi)存中,在大規(guī)模量子電路線性最近鄰過程中,占用內(nèi)存過大,搜索時(shí)間較長。希望在下一步工作中減少內(nèi)存空間占用率,縮小運(yùn)行時(shí)間。