面向二維近鄰架構(gòu)的啟發(fā)式量子線路映射算法

徐怡然，仝夢(mèng)楠，王菲，王海燕，沈洋，朱鵬程

（宿遷學(xué)院信息工程學(xué)院，江蘇宿遷 223800)

0 引言

近年來(lái)，量子計(jì)算技術(shù)發(fā)展迅猛，IBM[1]、Google[2]以及中國(guó)科學(xué)技術(shù)大學(xué)[3-4]等多個(gè)科研機(jī)構(gòu)相繼發(fā)布了多種量子計(jì)算原型設(shè)備。這些設(shè)備由于量子比特資源有限以及量子操作易受噪聲影響，通常也被稱為中等規(guī)模帶噪聲量子設(shè)備[5]，簡(jiǎn)稱為NISQ(Noisy Intermediate-Scale Quantum)設(shè)備。

在這些NISQ 設(shè)備上，每個(gè)物理量子比特僅允許和在設(shè)備拓?fù)浣Y(jié)構(gòu)中與其位置相鄰的比特進(jìn)行交互，這種約束被稱為最近鄰交互約束。最近鄰交互約束要求量子線路中的雙比特量子門僅允許作用在一對(duì)相鄰的物理量子比特上，但是量子線路在設(shè)計(jì)時(shí)并未考慮物理設(shè)備上的最近鄰約束，導(dǎo)致量子線路通常無(wú)法直接在NISQ設(shè)備上運(yùn)行。

為了在NISQ 設(shè)備上運(yùn)行量子線路，需要通過(guò)插入輔助量子門（如SWAP 門）的方式使得量子線路中雙比特量子門均滿足最近鄰交互約束，將這種適配物理設(shè)備近鄰交互約束所需的量子線路變換稱為量子線路映射。量子線路映射對(duì)量子計(jì)算的實(shí)現(xiàn)代價(jià)和成功率有著重要影響，其是量子計(jì)算基礎(chǔ)核心軟件中必不可缺的組件。

1 相關(guān)工作

早期的量子線路映射研究主要面向此類一維的線性最近鄰架構(gòu)[6-11]，但隨著量子計(jì)算技術(shù)的發(fā)展，目前基于超導(dǎo)電路以及離子阱等技術(shù)的量子計(jì)算設(shè)備通常采用二維最近鄰架構(gòu)，即量子比特分布在二維的平面架構(gòu)圖中。二維最近鄰架構(gòu)更復(fù)雜的連通性使得此前面向線性最近鄰架構(gòu)的量子線路映射方法通常不能直接適用于二維近鄰架構(gòu)。二維近鄰架構(gòu)上的量子線路映射已被證明是一種具有NP完全復(fù)雜性的計(jì)算難題[12]，目前關(guān)于面向二維架構(gòu)的量子線路映射仍處于探索階段，已有的研究存在較多有待完善之處。文獻(xiàn)[12-13]將量子線路映射問(wèn)題轉(zhuǎn)換為PBO(pseudo Boolean optimization)問(wèn)題，并通過(guò)SAT(Boolean satisfiability, SAT)/SMT(satisfiability modulo theories)求解器進(jìn)行求解；文獻(xiàn)[14-15]將映射問(wèn)題形式化為CP(Constrained Planning)問(wèn)題，并通過(guò)相應(yīng)的TP/CP算法進(jìn)行求解。以上方法由于指數(shù)級(jí)的時(shí)間復(fù)雜度，通常僅適用于求解規(guī)模極小的量子線路映射問(wèn)題。IBM 的量子計(jì)算軟件包Qiskit[16]提供了幾種適用于大規(guī)模量子線路的啟發(fā)式映射算法，其中性能最好的一種映射算法（簡(jiǎn)稱SABRE)源于文獻(xiàn)[17]，該方法基于對(duì)量子線路的正反向遍歷技術(shù)對(duì)量子比特初始分配作全局優(yōu)化，并構(gòu)建了一種具有前瞻能力的加權(quán)代價(jià)函數(shù)和啟發(fā)式映射規(guī)則。文獻(xiàn)[12]的研究表明，現(xiàn)有的啟發(fā)式方法由于其在搜索策略方面的局限性，仍存在很大的優(yōu)化空間，特別是在較大型量子計(jì)算設(shè)備上，所得結(jié)果和最優(yōu)結(jié)果之間的差距達(dá)5～45倍。

量子線路映射所需的輔助量子門數(shù)對(duì)量子線路的執(zhí)行時(shí)間開(kāi)銷和成功率有著重要影響，為了在現(xiàn)有研究基礎(chǔ)上進(jìn)一步減少量子門數(shù)，本文對(duì)量子比特的初始分配策略和量子比特的動(dòng)態(tài)路由策略進(jìn)行了研究，并提出了基于量子比特權(quán)重優(yōu)先級(jí)的初始映射算法和基于雙重展望窗口的量子比特路由算法，實(shí)驗(yàn)結(jié)果表明，該方法可以有效降低映射插入的SWAP門數(shù)。

2 量子線路映射問(wèn)題

量子線路映射通常包含兩個(gè)關(guān)鍵工藝：量子比特初始映射和量子比特路由。其中初始映射用于將量子線路中的邏輯量子比特映射到設(shè)備上的物理量子比特上。在目前的NISQ 設(shè)備上，雙比特量子門僅允許作用在位置相鄰的一對(duì)物理比特上。初始映射對(duì)于最終量子線路的執(zhí)行代價(jià)有著巨大影響，在不同初始映射下，執(zhí)行線路中的雙比特量子門所需的輔助量子門數(shù)存在巨大差異。由于量子線路中通常包含著多個(gè)雙比特量子門，這些雙比特量子門可能作用在不同的量子比特上，以及可能出現(xiàn)在線路中任意一個(gè)位置，所以多數(shù)情況下很難找到一個(gè)初始映射使得量子線路中所有雙比特量子門均符合最近鄰約束，在此情況下要通過(guò)插入SWAP門[16]在物理設(shè)備上移動(dòng)邏輯量子比特，從而使得每個(gè)雙比特量子門符合最近鄰約束，將該過(guò)程稱為量子比特路由。

將如圖1 所示，量子線路映射到如圖1(a)所示的二維網(wǎng)格型量子計(jì)算架構(gòu)上，其中，圖1(a)給出了量子比特初始映射，即{q0 →Q0, q1 →Q1, q2 →Q2,q3 →Q3, q4 →Q4, q5 →Q5, q6 →Q6, q7 →Q7,q8 →Q8}；圖1(b)給出了量子比特路由過(guò)程，為執(zhí)行該量子線路中的雙比特量子門，共插入了4個(gè)SWAP門。

圖1 量子線路映射過(guò)程

3 量子比特初始映射算法

量子比特初始映射用于為量子線路中的邏輯量子比特唯一且互斥的分配NISQ設(shè)備上的物理量子比特，本節(jié)將重點(diǎn)介紹用于生成量子比特初始映射的算法。

3.1 量子比特權(quán)重系數(shù)

在量子線路中，每個(gè)量子比特可能和多個(gè)雙比特量子門相關(guān)，在生成初始映射時(shí)，優(yōu)先考慮關(guān)聯(lián)量子門數(shù)較多的量子比特有助于降低映射代價(jià)，因此，可以使用所關(guān)聯(lián)的雙比特量子門數(shù)作為確定邏輯量子比特優(yōu)先級(jí)權(quán)重的重要因素。另外，量子門的執(zhí)行有嚴(yán)格的時(shí)序約束，量子比特權(quán)重系數(shù)同樣也要考慮量子門的時(shí)序信息。基于以上因素，對(duì)于一個(gè)包含M個(gè)量子比特和N個(gè)量子門的量子線路，假設(shè)其第j個(gè)量子比特和第i個(gè)量子門相關(guān)聯(lián)，其中，i(1<=i<=N)表示量子門的時(shí)序信息，j(0<=j

對(duì)于每個(gè)量子比特而言，與其關(guān)聯(lián)的量子門賦予其的權(quán)重之和便是該量子比特的權(quán)重系數(shù)，如公式(2)所示。

量子比特權(quán)重系數(shù)決定了其在初始映射中的優(yōu)先級(jí)，權(quán)重系數(shù)越大的量子比特對(duì)于降低量子線路映射代價(jià)具有更重要的作用，因此在初始映射時(shí)，將對(duì)線路中的邏輯量子比特按照其權(quán)重系數(shù)作降序排列，然后從前到后依次為序列中的各量子比特分配物理位置。

3.2 初始映射算法

在確定邏輯量子比特的權(quán)重優(yōu)先順序后，便可依次為每個(gè)邏輯量子比特分配設(shè)備上的物理量子比特。在分配邏輯量子比特qi時(shí)，在耦合上可能存在多個(gè)候選物理量子比特。為降低量子線路映射開(kāi)銷，應(yīng)盡量將交互的邏輯比特分配至設(shè)備上的近鄰位置。假定所有已分配的邏輯量子比特qx構(gòu)成一個(gè)集合P，其中，邏輯量子比特qx對(duì)應(yīng)的物理量子比特為Qloc(qx)，在將邏輯量子比特qi分配到物理量子比特Qj時(shí)所需的映射開(kāi)銷如公式(3)所示。

其中，d(Qi,Qj)表示物理量子比特Qi和Qj在設(shè)備架構(gòu)圖上的最短距離。x(i,j)表示量子比特qi和qj是否存在交互，即是否作為同一個(gè)雙比特量子門的輸入，若存在，則取值為1，否則取值為0。顯然，公式(3)所示的代價(jià)函數(shù)越小，所需映射的映射開(kāi)銷也越少。

基于邏輯量子比特的權(quán)重序列以及公式(3)所示的映射代價(jià)函數(shù)，提出量子比特初始映射算法，如算法1所示。該算法的基本思想如下：為量子線路中的每個(gè)邏輯量子比特計(jì)算權(quán)重系數(shù)（公式(2))，并將邏輯量子比特按照權(quán)重系數(shù)降序排列；按照權(quán)重排序，每次選擇一個(gè)邏輯量子比特，此時(shí)設(shè)備架構(gòu)上所有空閑的物理量子比特均可作為該邏輯量子比特的目標(biāo)位置，為選擇最佳位置，為每個(gè)空閑物理量子比特計(jì)算映射代價(jià)函數(shù)（公式(3))，并將邏輯量子比特分配至映射代價(jià)最小的物理位置。

算法1 量子比特初始映射算法

輸入：邏輯量子線路qc，量子設(shè)備架構(gòu)圖G

輸出：量子比特的初始映射

1.根據(jù)公式(2)，為量子線路qc中的量子比特生成優(yōu)先排序序列qu

2.FOR 序列qu中的每個(gè)邏輯量子qDO

3.FOR 架構(gòu)圖G中每個(gè)空閑物理量子比特QDO

4.根據(jù)公式(3)，計(jì)算將q分配Q的映射代價(jià)

5.記錄映射代價(jià)最小的Qmin

6.END

7.將q分配至映射代價(jià)最小的Qmin

8.END

9.輸出邏輯量子比特到物理量子比特的初始映射

4 量子比特路由算法

在給定的初始映射下，量子線路中可能仍然存在不滿足近鄰交互約束的雙比特量子門，此時(shí)需要通過(guò)量子比特路由插入SWAP門，使得每個(gè)量子門均滿足近鄰約束。本節(jié)重點(diǎn)介紹量子比特路由相關(guān)的代價(jià)函數(shù)、規(guī)則以及算法。

4.1 啟發(fā)式代價(jià)函數(shù)

給定量子比特初始映射π，一個(gè)量子門g 的映射代價(jià)如公式(4)所示。

其中，q1和q2表示量子門g 相關(guān)的兩個(gè)邏輯量子比特；π(q)表示在初始映射π下邏輯比特q對(duì)應(yīng)的物理比特；d()函數(shù)的含義和公式(3)相同，即表示兩個(gè)物理量子比特在設(shè)備架構(gòu)圖上的最短距離。代價(jià)函數(shù)C(g)越小，則使該量子門滿足近鄰約束插入的SWAP門數(shù)越小。

在量子線路映射過(guò)程中，插入的SWAP門將交換所在物理量子比特上的邏輯量子比特，從而實(shí)現(xiàn)移動(dòng)邏輯量子比特的效果。SWAP門對(duì)邏輯量子比特的移動(dòng)將對(duì)后續(xù)量子門的映射代價(jià)產(chǎn)生連鎖影響，因此為準(zhǔn)確評(píng)價(jià)SWAP門的作用效果，需要考慮該門對(duì)其后所有量子門的影響，但對(duì)大規(guī)模量子線路而言這種做法的時(shí)間開(kāi)銷太高。因此，為在時(shí)間和代價(jià)之間取得平衡，通常僅考慮后續(xù)固定數(shù)目的量子門。為此引入展望窗口的概念，只有在展望窗口中包含的量子門才在計(jì)算映射代價(jià)時(shí)考慮。將應(yīng)用SWAP門后，在展望窗口中所有量子門的映射代價(jià)（如公式(4))之和作為衡量一個(gè)SWAP門作用效果的代價(jià)函數(shù)。另外，量子線路中量子門的執(zhí)行有著嚴(yán)格的時(shí)序關(guān)系，SWAP 門的作用代價(jià)函數(shù)應(yīng)該更優(yōu)先考慮執(zhí)行時(shí)序靠前的量子門。基于該考慮，將展望窗口分為兩級(jí)：第一級(jí)展望窗口F1包含量子線路中的前兩層子線路；而第二級(jí)展望窗口F2包含量子線路中的第3～5 層子線路。從而得到如公式(5)所示的SWAP門代價(jià)函數(shù)。

其中，|F1|和|F2|分別是表示展望窗口F1和F2中包含的雙比特量子門數(shù)；C(g)如公式(4)所示，表示雙比特量子門的映射代價(jià)；ω 是一個(gè)權(quán)重因子，在實(shí)驗(yàn)時(shí)設(shè)置為0.8，表示代價(jià)函數(shù)優(yōu)先考慮第一級(jí)展望窗口中的量子門。

4.2 啟發(fā)式量子比特路由算法

量子比特路由算法按照量子門的依賴關(guān)系從左向右依次遍歷量子線路中各量子門，若當(dāng)前量子門滿足近鄰交互約束，則該量子門可立即執(zhí)行，即將其從量子線路中刪除；否則，需在多個(gè)可用SWAP 門中選擇一個(gè)SWAP門用于移動(dòng)邏輯量子比特，從而使得線路中某些待執(zhí)行量子門逐步向著可執(zhí)行狀態(tài)轉(zhuǎn)變。

算法2 啟發(fā)式量子比特路由算法

輸入：邏輯量子線路qc，量子設(shè)備架構(gòu)圖G，初始映射π

輸出：滿足近鄰約束的物理量子線路

1.為量子線路qc生成量子門依賴關(guān)系圖dag

2.WHILE 量子線路qc不為空DO

3.從依賴關(guān)系圖dag中選擇度為零的量子門，構(gòu)成待執(zhí)行量子門集合E

4.FOR 待執(zhí)行量子門集合E中的每個(gè)量子門gDO

5.IF量子門g滿足近鄰約束THEN

6.從量子線路qc中刪除量子門g，并跳轉(zhuǎn)至第2行

7.END

8.根據(jù)待執(zhí)行量子門集合E中的量子門生成可用SWAP門集合S

9.FOR 集合S中的每個(gè)SWAP門swDO

10.根據(jù)公式(5)，計(jì)算將SWAP門sw的代價(jià)函數(shù)

11.記錄代價(jià)函數(shù)值最小的swmin

12.END

13.插入swmin，并更新初始映射π

14.END

本文提出的啟發(fā)式量子比特路由算法如算法2所示，其中第3～7行用于執(zhí)行在當(dāng)前初始映射下滿足近鄰約束和量子門依賴關(guān)系的所有量子門；第8行中可選SWAP門集合S由設(shè)備所支持且至少和一個(gè)待執(zhí)行量子門相關(guān)的SWAP 門組成；第9～13 行根據(jù)如公式(5)所示的代價(jià)函數(shù)在可用SWAP 門集合中選擇一個(gè)代價(jià)函數(shù)值最小的SWAP門，將其插入量子線路并同時(shí)更新初始映射。當(dāng)量子線路中的所有量子門均執(zhí)行完成后，算法2終止運(yùn)行。

5 實(shí)驗(yàn)與比較

本文所提全部算法均使用Python語(yǔ)言實(shí)現(xiàn)，運(yùn)行環(huán)境為：Windows 10 操作系統(tǒng)、英特爾酷睿i5 處理器和8GB 內(nèi)存。為檢驗(yàn)本文映射算法的性能，將其和Qiskit 中集成的映射算法[16-17]作比較，即SABRE 算法。另外，所有實(shí)驗(yàn)中均采用了文獻(xiàn)[16]相同的基準(zhǔn)測(cè)試線路以及量子計(jì)算架構(gòu)(IMB Q20)。由于在量子計(jì)算設(shè)備上SWAP 門需被分解成3 個(gè)CNOT 門，因此以CNOT門數(shù)實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)。

SABRE 算法通過(guò)輸入電路的迭代雙向遍歷對(duì)映射結(jié)果作優(yōu)化，該方法具有很大的隨機(jī)性，因此需要多次運(yùn)行才能獲得較好結(jié)果。為保證比較的公平性，實(shí)驗(yàn)中運(yùn)行SABRE算法10次并取最優(yōu)結(jié)果。具體實(shí)驗(yàn)結(jié)果如表1所示，本文所提方法和SABRE算法相比，在多數(shù)基準(zhǔn)線路上實(shí)現(xiàn)了門數(shù)的減少，平均優(yōu)化率可達(dá)到26.88%。另外，實(shí)驗(yàn)中兩種方法運(yùn)行的時(shí)間均非常短（幾秒以內(nèi)），但本文算法運(yùn)行時(shí)間還是普遍少于SABRE。由于空間限制，未在表1給出運(yùn)行時(shí)間。

表1 映射算法比較結(jié)果

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

為降低量子線路映射過(guò)程插入的輔助量子門數(shù)，本文提出了一種基于量子比特權(quán)重系數(shù)的初始映射算法，并提出了一種基于雙層展望窗口的啟發(fā)式動(dòng)態(tài)路由算法。實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法可以快速生成量子線路映射結(jié)果，且較已有方法可以有效減少映射所需的輔助量子門數(shù)。