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

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

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

0 引 言

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

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

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

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

1.1 量子邏輯綜合

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

1.2 量子邏輯門(mén)

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

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

1.3 量子代價(jià)

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

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

圖1 NCV 門(mén)庫(kù)Fig.1 NCV gate library

1.4 量子電路

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

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

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

1.5 交換門(mén)

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

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

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

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

1.6 全局換線

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

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

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

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

證明:

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

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

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

圖4 SWAP 門(mén)的化簡(jiǎn)Fig.4 Simplification of SWAP gate

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

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

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

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

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

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

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

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

具體算法描述如下:

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

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

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

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

第五步:近鄰化,把量子電路集合Nr(i)中的第一個(gè)非近鄰門(mén)gl(i)轉(zhuǎn)化為近鄰門(mén),采用添加交換門(mé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)行最終的冗余交換門(mén)排查檢測(cè),消除量子電路中一些冗余的交換門(mén)。

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

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

由NCV 門(mén)庫(kù)構(gòu)成的量子電路中,在量子電路輸入/輸出真值保持不變的前提條件下,通過(guò)啟發(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)記為L(zhǎng)(i)。

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

2.3 求最小混亂值算法

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

具體算法描述如下:

第一步:從n=0 開(kāi)始,讀取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 開(kāi)始編號(hào),這是一次完整的操作。按照上述方法不斷地進(jìn)行查找與刪除,直到讀取完origin[n]最后一個(gè)元素,此時(shí)target[n]中的元素將被完全刪除,t[n]中的所有元素求和記為t,t即為最小混亂值。

2.4 添加交換門(mén)算法

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

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

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

具體算法描述如下:

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

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

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

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

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

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

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

為了驗(yàn)證算法的有效性和可行性并對(duì)算法的實(shí)際性能進(jìn)行分析,所提出算法均使用標(biāo)準(zhǔn)C++語(yǔ)言實(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ù)中量子門(mén)數(shù)量在0～50 之間。Table 1 給出了此處的實(shí)驗(yàn)結(jié)果與具有代表性的文獻(xiàn)[7]的對(duì)比分析。表中Benchmark 為標(biāo)準(zhǔn)量子電路名稱(chēng),n為量子電路線數(shù),Gate 為量子門(mén)的數(shù)量(不包含一元量子門(mén)),S為在量子電路線序不變的前提條件下普通構(gòu)造LNN 架構(gòu)添加交換門(mén)的數(shù)量,s-1 為參考文獻(xiàn)[7]中的算法為構(gòu)造LNN 架構(gòu)添加的交換門(mén)數(shù)量,s-2 為所提出算法構(gòu)造LNN 架構(gòu)添加的交換門(mén)數(shù)量,%s-1 為參考文獻(xiàn)[7]中的算法為構(gòu)造LNN 架構(gòu)添加的交換門(mén)數(shù)量的優(yōu)化率,%s-2 為所提出算法構(gòu)造LNN 架構(gòu)添加的交換門(mén)數(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]中沒(méi)有做到實(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ì)量子電路添加交換門(mén)數(shù)量的對(duì)比分析發(fā)現(xiàn),在相同的24 測(cè)試數(shù)據(jù)中,有4 組實(shí)驗(yàn)數(shù)據(jù)添加交換門(mén)數(shù)量比文獻(xiàn)[7]少(其中1 組實(shí)驗(yàn)數(shù)據(jù)添加交換門(mén)數(shù)量比文獻(xiàn)[7]少3 個(gè);2 組實(shí)驗(yàn)數(shù)據(jù)添加交換門(mén)數(shù)量比文獻(xiàn)[7]少6 個(gè);1 組實(shí)驗(yàn)數(shù)據(jù)添加交換門(mén)數(shù)量比文獻(xiàn)[7]少11 個(gè));10 組實(shí)驗(yàn)數(shù)據(jù)添加交換門(mén)數(shù)量與文獻(xiàn)[7]相同;10 組實(shí)驗(yàn)數(shù)據(jù)添加交換門(mén)數(shù)量比文獻(xiàn)[7]略高(其中3 組實(shí)驗(yàn)數(shù)據(jù)添加交換門(mén)數(shù)量比文獻(xiàn)[7]多1 個(gè);4 組實(shí)驗(yàn)數(shù)據(jù)添加交換門(mén)數(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)過(guò)程中減少插入的SWAP 門(mén)數(shù)量的對(duì)比圖,橫軸代表量子電路的規(guī)模,縱軸代表該算法相較于普通方法構(gòu)造LNN 架構(gòu)降低添加的SWAP 門(mén)數(shù)量;如圖例中所示,點(diǎn)型柱狀圖代表所提出算法的實(shí)驗(yàn)結(jié)果,網(wǎng)格型柱狀圖代表文獻(xiàn)[7]中算法的對(duì)比結(jié)果。從圖中可以看出,對(duì)于3 線量子線路,所提出算法降低的SWAP 門(mén)數(shù)量略低于文獻(xiàn)[7];對(duì)于4 ～5 線的量子電路,所提出算法降低的SWAP 門(mén)數(shù)量高于文獻(xiàn)[7];相比于文獻(xiàn)[7]只能處理5 線以內(nèi)的量子電路,所提出算法適用的量子電路規(guī)模為4 ～8 線,且隨著量子電路規(guī)模的增加,所提出算法在構(gòu)建LNN 架構(gòu)過(guò)程中減少插入的SWAP 門(mén)數(shù)量呈上升趨勢(shì),相較于文獻(xiàn)[7]具有明顯優(yōu)勢(shì)。結(jié)合Table 1 中的數(shù)據(jù)進(jìn)行分析,所提出算法添加交換門(mén)數(shù)量的優(yōu)化率穩(wěn)定且優(yōu)化效果良好,平均優(yōu)化率達(dá)到為62.41%,算法可以處理的量子門(mén)數(shù)量級(jí)別也可以更高;在搜索空間呈指數(shù)增長(zhǎng)的前提條件下,所提出算法的CPU 運(yùn)行時(shí)間也具有明顯優(yōu)勢(shì)。

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

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

4 結(jié) 論

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