面向二維近鄰架構的啟發式量子線路映射算法

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

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

0 引言

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

在這些NISQ 設備上，每個物理量子比特僅允許和在設備拓撲結構中與其位置相鄰的比特進行交互，這種約束被稱為最近鄰交互約束。最近鄰交互約束要求量子線路中的雙比特量子門僅允許作用在一對相鄰的物理量子比特上，但是量子線路在設計時并未考慮物理設備上的最近鄰約束，導致量子線路通常無法直接在NISQ設備上運行。

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

1 相關工作

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

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

2 量子線路映射問題

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

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

圖1 量子線路映射過程

3 量子比特初始映射算法

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

3.1 量子比特權重系數

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

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

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

3.2 初始映射算法

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

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

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

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

輸入：邏輯量子線路qc，量子設備架構圖G

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

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

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

3.FOR 架構圖G中每個空閑物理量子比特QDO

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

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

6.END

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

8.END

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

4 量子比特路由算法

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

4.1 啟發式代價函數

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

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

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

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

4.2 啟發式量子比特路由算法

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

算法2 啟發式量子比特路由算法

輸入：邏輯量子線路qc，量子設備架構圖G，初始映射π

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

1.為量子線路qc生成量子門依賴關系圖dag

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

3.從依賴關系圖dag中選擇度為零的量子門，構成待執行量子門集合E

4.FOR 待執行量子門集合E中的每個量子門gDO

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

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

7.END

8.根據待執行量子門集合E中的量子門生成可用SWAP門集合S

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

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

11.記錄代價函數值最小的swmin

12.END

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

14.END

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

5 實驗與比較

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

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

表1 映射算法比較結果

6 結束語

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