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

徐怡然，仝夢楠，王菲，王海燕，沈洋，朱鵬程

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

0 引言

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

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

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

1 相關(guān)工作

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

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

2 量子線路映射問題

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

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

圖1 量子線路映射過程

3 量子比特初始映射算法

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

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

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

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

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

3.2 初始映射算法

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

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

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

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

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

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

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

2.FOR 序列qu中的每個邏輯量子qDO

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

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

5.記錄映射代價最小的Qmin

6.END

7.將q分配至映射代價最小的Qmin

8.END

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

4 量子比特路由算法

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

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

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

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

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

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

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

量子比特路由算法按照量子門的依賴關(guān)系從左向右依次遍歷量子線路中各量子門，若當(dāng)前量子門滿足近鄰交互約束，則該量子門可立即執(zhí)行，即將其從量子線路中刪除；否則，需在多個可用SWAP 門中選擇一個SWAP門用于移動邏輯量子比特，從而使得線路中某些待執(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中的每個量子門gDO

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

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

7.END

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

9.FOR 集合S中的每個SWAP門swDO

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

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

12.END

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

14.END

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

5 實驗與比較

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

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

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

6 結(jié)束語

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