竇星磊 劉 磊 陳岳濤

(計算機體系結(jié)構(gòu)國家重點實驗室(中國科學院計算技術研究所) 北京 100190) (中國科學院計算技術研究所 北京 100190)

量子計算在近年來蓬勃發(fā)展，它針對特定計算任務展現(xiàn)出了強大的計算加速能力，可用于加速求解經(jīng)典計算中的難解問題，如數(shù)據(jù)庫搜索[1]、機器學習[2-3]、化學反應模擬[4-5]、加密解密[6]、優(yōu)化問題[7]等.量子計算機(量子芯片)是實施量子計算的物理設備，量子位是量子計算機的基本運算單元，量子門操作用于操控量子位狀態(tài)，由量子門操作序列組成的量子程序可完成特定的量子計算任務.Intel,Google,IBM等企業(yè)已相繼發(fā)布了5～72量子位的量子計算機[8-10].IBM提供了量子計算云服務[11]，用戶可通過接口向云服務提交執(zhí)行量子計算任務.在過去數(shù)10年中，量子計算的理論研究取得了較大進展；但量子計算機物理機的相關研究卻始終難以克服噪聲問題帶來的影響.現(xiàn)在的量子計算機屬于中等規(guī)模帶噪聲量子計算機(noisy intermediate-scale quantum computer,NISQ computer)類型的量子計算機[12].在該類量子計算機中，量子位狀態(tài)不穩(wěn)定，量子門操作可能出現(xiàn)錯誤.雖然量子糾錯編碼可以使量子計算機獲得容錯能力，但其成本太高(構(gòu)造一個容錯量子位需要20～100個物理量子位)，無法在現(xiàn)階段的量子計算機上實施.

量子計算機有超導[13]、離子阱[14]、光量子[15]等物理實現(xiàn)方式.本文主要關注超導量子計算機.面向超導量子計算機的量子程序映射策略可將高級語言編寫的量子算法轉(zhuǎn)換為能在超導量子計算機上直接執(zhí)行的量子門操作指令序列.通常，量子程序映射策略的優(yōu)化目標包括：1)將量子程序映射至具有低錯誤率的量子位和連接上執(zhí)行，以提升量子程序的執(zhí)行保真度.2)縮減映射過程中插入的SWAP操作數(shù)，降低映射后量子線路的復雜度，間接提升執(zhí)行保真度.3)縮減映射后量子線路深度，以減少由較短的量子位狀態(tài)保持時間引發(fā)的錯誤.

量子計算云服務的出現(xiàn)和興起為傳統(tǒng)量子程序映射策略[16-19]帶來了新的挑戰(zhàn).傳統(tǒng)量子程序映射策略通常僅支持映射單個量子程序.在執(zhí)行量子程序時，量子計算機上未被分配的物理量子位會被閑置，這導致量子計算機中的資源未得到充分利用.此外，對量子計算云服務的訪問請求越來越多，延長了服務等待時間.因此有必要通過并發(fā)機制，同時映射、執(zhí)行多個量子程序來提升量子計算機的通量和資源利用率.然而并發(fā)量子程序映射帶來了不可忽視的可靠性下降的問題.這是由于：量子計算機中健壯資源稀缺，不足以為每個量子程序分配足夠的健壯資源；并發(fā)量子程序之間的串擾[20]；映射并發(fā)量子程序時，啟發(fā)式搜索的搜索空間被限制，造成更高的量子程序映射開銷.先前的工作[21]表明，同時執(zhí)行2個并發(fā)量子程序會導致平均保真度降低12%.

本文重點討論面向超導量子計算機的量子程序映射技術，對先前技術進行歸納、分析和對比.針對并發(fā)量子程序映射問題，本文提出一種新的并發(fā)量子程序映射策略，在提升量子計算機通量的前提下盡可能保證量子程序的執(zhí)行保真度.本文的主要貢獻可以歸納為3點：

1)深入分析了近年來面向超導量子計算機的量子程序映射工作，并進行分類，深入剖析了不同類別映射策略的特點.

2)揭示了并發(fā)量子程序映射可能導致映射成本提升和保真度下降的問題；據(jù)此設計并發(fā)量子程序映射策略，包括社區(qū)發(fā)現(xiàn)輔助的量子位劃分(community detection assisted qubit partition,CDAQP)算法、引入跨程序SWAP操作的映射轉(zhuǎn)換算法X-SWAP，幫助提升并發(fā)量子程序的執(zhí)行保真度，降低映射成本.

3)提出了量子程序映射任務調(diào)度器，可從待執(zhí)行任務隊列中選擇最佳量子程序組合并發(fā)執(zhí)行；允許在量子計算機通量和保真度2方面進行權衡.

本文設計的系統(tǒng)是一個初步的面向NISQ量子計算機的操作系統(tǒng)原型(quantum operating system,QuOS).

1 量子計算概述

1.1 量子計算

量子位是量子計算機中的基本運算單元.如圖1所示，布洛赫球面用于表示單個量子位的狀態(tài).布洛赫球面上下2個極點分別代表2個量子計算基態(tài)：|0〉和|1〉.一個量子位的狀態(tài)為2個基態(tài)|0〉和|1〉的疊加，即|ψ〉=α|0〉+β|1〉.其中，α和β為復數(shù)，且滿足|α|2+|β|2=1,α和β分別為該量子位|0〉和|1〉兩個量子基態(tài)對應的概率幅.當采用讀出操作對量子位狀態(tài)進行測量時，測量結(jié)果為0的概率為|α|2，測量結(jié)果為1的概率為|β|2.類似地，2個量子位的狀態(tài)可以表示為4個量子計算基態(tài)的疊加：|ψ〉=α00|00〉+α01|01〉+α10|10〉+α11|11〉.單量子位門操作(如H，X，Y，Z門等)可改變單個量子位的狀態(tài).受控非(controlled-not,CNOT)門為雙量子位門操作，它作用于2個量子位.若其中控制量子位被置為1，目標位的狀態(tài)將會被翻轉(zhuǎn).涉及3個或更多量子位的門操作可被分解為單量子位門和雙量子位門操作的組合序列[22].

Fig.1 The Bloch representation of a single qubit圖1 單量子位的布洛赫球面表示

1.2 量子計算機

IBM系列量子計算機屬于超導量子計算機，具有基于約瑟夫森環(huán)結(jié)的transmon量子位[13]和基于微波的量子門操作[23].超導量子計算機僅在相鄰物理量子位之間存在連接.涉及2個量子位的雙量子位門操作僅能在具有相互連接的2個相鄰物理量子位上執(zhí)行.圖2展示了IBMQ Melbourne(后文稱IBM-Q16)超導量子計算機的量子位拓撲結(jié)構(gòu).

Fig.2 Qubit topology of IBMQ Melbourne圖2 IBMQ Melbourne的量子位拓撲結(jié)構(gòu)

1.3 量子計算機中的錯誤

由于量子計算機的物理量子位狀態(tài)不穩(wěn)定，量子位間的連接脆弱且易受干擾.在量子計算機上運行的量子程序可能會發(fā)生3種類型的錯誤：1)由較短的量子位狀態(tài)保持時間導致的保持錯誤.保持錯誤主要受到在量子計算機上執(zhí)行的量子程序深度的影響.量子程序深度越深，執(zhí)行時間越長，可靠性就越低.2)由易錯的量子門操作導致的操作錯誤.操作錯誤主要受到在量子計算機上執(zhí)行的量子程序復雜度的影響.量子程序中包含的門操作越多，出錯的概率越高.3)測量操作帶來的讀出錯誤.量子程序在執(zhí)行結(jié)束后需要執(zhí)行測量操作以獲取量子位狀態(tài).測量操作不可靠，可能讀出錯誤的狀態(tài).

IBM量子計算云服務提供了錯誤率標定數(shù)據(jù)，可通過接口獲取.標定數(shù)據(jù)約每24 h更新一次.

1.4 量子程序映射

量子程序由一系列量子門操作組成，可用量子線路表示.圖3(a)展示了三量子位Toffoli門操作分解為單、雙量子位門操作序列后的量子線路.其中每條橫線代表一個邏輯量子位，橫線上的節(jié)點代表單、雙量子位門操作.圖3(b)展示了該量子線路的有向無環(huán)圖(directed acyclic graph,DAG).DAG用于表示量子程序中量子門操作的執(zhí)行順序依賴關系，其中每個節(jié)點代表一個量子門操作.當一個量子門操作在DAG中有前驅(qū)節(jié)點未被執(zhí)行時，該量子門操作無法執(zhí)行.當一個量子門操作在DAG中沒有未執(zhí)行的前驅(qū)節(jié)點時，它在邏輯上才可被執(zhí)行.

Fig.3 The quantum circuit and DAG of decomposed Toffoli gate圖3 Toffoli門分解后的量子線路和DAG

求解量子程序映射問題需要遵循3個約束：1)每個邏輯量子位都需要被映射至量子計算機中的一個物理量子位上，且該物理量子位不能再映射其他的邏輯量子位.2)若一個量子門操作未執(zhí)行，其后繼的量子門操作也不能被執(zhí)行.3)當一個雙量子位門操作涉及到的邏輯量子位的映射位置在物理上相鄰時，該雙量子位門操作才能被執(zhí)行，否則可在量子線路中插入SWAP操作(一個SWAP操作由3個CNOT操作組成，用于交換2個邏輯量子位的映射位置)，使涉及到的邏輯量子位在物理上相鄰.

解決量子程序映射問題一般包括構(gòu)建初始映射和映射轉(zhuǎn)換2個步驟：

1)構(gòu)建初始映射.即把每個邏輯量子位映射至一個物理量子位.初始映射對量子程序的后續(xù)映射成本和執(zhí)行保真度具有重要影響.初始映射需要滿足：程序被分配在量子計算機中最健壯的量子位上；初始分配的量子位鄰近，便于節(jié)約后續(xù)映射成本.

2)映射轉(zhuǎn)換.即在量子線路中插入SWAP操作，滿足所有雙量子位門操作的邏輯量子位映射位置約束，使所有雙量子位門操作均可執(zhí)行.映射轉(zhuǎn)換時插入的SWAP操作會導致量子程序執(zhí)行保真度降低，因此需保證插入的SWAP操作盡可能少，且盡可能使用量子計算機中的健壯資源.

1.5 量子操作系統(tǒng)

量子操作系統(tǒng)是量子計算機中軟硬件資源的管理者，負責管理、配置具有不同物理實現(xiàn)方式的量子位；調(diào)度量子程序；為量子程序提供最可靠的映射方案.量子計算機操作系統(tǒng)與經(jīng)典計算機操作系統(tǒng)在設計原則和設計目標上具有較大區(qū)別.本文設計的系統(tǒng)是一個初步的面向NISQ量子計算機的操作系統(tǒng)原型QuOS.在后續(xù)工作中，作者將進一步對量子操作系統(tǒng)和量子計算技術棧中的其他技術進行探索.

2 量子程序映射技術概覽

量子程序映射技術屬于量子計算技術棧[24]中的軟件棧層次，位于高級語言(用于表示特定的量子算法)和量子計算機系統(tǒng)結(jié)構(gòu)(包括量子位、量子門操作、量子糾錯等)層次之間.量子計算軟件棧覆蓋范圍廣，涉及多量子位門操作分解[22,25]、量子線路映射前/后優(yōu)化[26-27]、量子程序調(diào)試與斷言[28-29]、量子緩存[30]、并發(fā)量子程序映射[21,31-32]等問題.本文針對量子程序映射問題進行研究，假設量子線路中的多量子位門操作已被分解，線路中的門操作均能在目標量子計算機上執(zhí)行；不進行映射前/后優(yōu)化；僅考慮在量子線路中插入SWAP操作，滿足所有雙量子位門操作的邏輯量子位映射位置約束.

量子程序映射問題已被證明為NP-完全問題(NP-Complete problem)[33-34].文獻[35]綜述了常見的量子計算機物理實現(xiàn)技術及相應的量子位拓撲結(jié)構(gòu)，包括一維、二維拓撲結(jié)構(gòu).針對具體的物理量子位拓撲結(jié)構(gòu)，以保真度或插入SWAP數(shù)為優(yōu)化目標的量子程序映射策略陸續(xù)被提出.這些量子程序映射技術可分為2類：

1)基于數(shù)學問題求解器的最優(yōu)化方法.該類方法可根據(jù)量子程序映射問題設計約束條件和優(yōu)化目標，將量子程序映射問題轉(zhuǎn)換為等價的數(shù)學優(yōu)化問題，并采用求解器求解.這類方法可求得小型量子程序映射問題的最優(yōu)解或近似最優(yōu)解.但算法時間復雜度高，運行時間長，無法支持求解大型量子程序(具有數(shù)十個以上量子位的量子程序)映射問題.此外，該類方法難以同時對多個優(yōu)化目標進行優(yōu)化，且難以實現(xiàn)多個優(yōu)化目標之間的權衡.

2)啟發(fā)式方法.啟發(fā)式方法采用啟發(fā)式信息輔助搜索.量子程序映射策略依據(jù)啟發(fā)式信息或貪心策略確定邏輯量子位初始映射位置，后根據(jù)啟發(fā)式信息篩選出最合適的SWAP操作插入程序進行映射轉(zhuǎn)換.啟發(fā)式方法更為靈活，具有更佳的可擴展性，不受限于量子芯片和量子程序的規(guī)模，有處理更大規(guī)模量子程序映射問題的能力.然而啟發(fā)式策略無法保證求解所得的結(jié)果為最優(yōu)解.可能存在保真度更高、映射成本更低的映射方案.

2.1 最優(yōu)化方法

本文對具有代表性的最優(yōu)化方法進行了整理匯總，如表1所示.現(xiàn)有工作中，量子程序映射問題可等價轉(zhuǎn)化為如下類型數(shù)學問題：可滿足性(Boolean satisfiability,SAT)問題、可滿足性模理論(satis-fiability modulo theories,SMT)問題、偽布爾優(yōu)化(pseudo Boolean optimization,PBO)問題、動態(tài)規(guī)劃(dynamic programming,DP)問題、時序規(guī)劃(temporal planning,TP)問題、約束規(guī)劃(constrained planning,CP)問題、整數(shù)線性規(guī)劃(integer linear programming,ILP)問題、混合整數(shù)規(guī)劃(mixed integer programming,MIP)問題等.

Table 1 Optimization Methods for Quantum Program Mapping表1 量子程序映射最優(yōu)化方法

若從量子程序映射問題轉(zhuǎn)化為等價數(shù)學優(yōu)化問題，需轉(zhuǎn)化的內(nèi)容一般包括：1)待優(yōu)化變量.量子程序映射過程中，邏輯量子位的映射位置、門操作的執(zhí)行時刻、SWAP路徑均需轉(zhuǎn)換為等價數(shù)學優(yōu)化問題中的待優(yōu)化變量，以便于求解.2)約束條件.須將量子程序映射問題中的限制條件(如門操作需順序執(zhí)行、每個物理量子位僅允許映射一個邏輯量子位等)轉(zhuǎn)換為等價數(shù)學優(yōu)化問題中的限制條件.3)優(yōu)化目標.優(yōu)化目標通常包括程序執(zhí)行保真度、映射過程中插入的SWAP操作數(shù)目、映射后線路深度(或程序執(zhí)行時間)3種.

文獻[36]將量子程序映射問題轉(zhuǎn)化為MIP問題.該策略將量子線路按照數(shù)據(jù)依賴關系劃分為多個層，每層中的門操作不涉及相同的邏輯量子位，可同時執(zhí)行.該映射策略首先確定初始映射，然后利用求解器確定相鄰2層之間的映射轉(zhuǎn)換SWAP操作.映射所需的SWAP數(shù)目作為優(yōu)化目標.MUQUT[40]根據(jù)量子程序映射問題構(gòu)造ILP問題，并采用求解器Gurobi[44]求解.該策略同樣采用將量子線路分層并在層間插入SWAP的方法進行量子程序映射.線路深度作為優(yōu)化目標.該策略將量子程序映射位置所占矩形區(qū)域在量子芯片上滑動，來搜索可靠性最高的映射位置.

Wille等人[37]實現(xiàn)了量子程序映射問題到PBO問題的轉(zhuǎn)化，實現(xiàn)了最優(yōu)化方法與啟發(fā)式方法的對比，為啟發(fā)式方法結(jié)果的評價提供了依據(jù)，并在后續(xù)工作中[38]給出了與啟發(fā)式方法對比的實際案例.

Booth等人[39]將量子程序映射問題轉(zhuǎn)換為TP問題，結(jié)合線路深度和插入SWAP數(shù)，構(gòu)建加權優(yōu)化目標函數(shù).該策略將TP問題和CP問題進行結(jié)合.首先求解TP問題，提供可靠的初始解決方案，在此基礎上求解CP問題，進一步提升解決方案的質(zhì)量.

Siraichi等人[33]對比了最優(yōu)化方法與啟發(fā)式方法，并給出了基于DP的最優(yōu)化量子程序映射算法實現(xiàn).DP執(zhí)行過程中可存儲中間結(jié)果，避免重復計算，提升計算效率.

文獻[18,20,41-43]采用SMT求解器求解量子程序映射問題.常見SMT求解器包括Z3[45],vZ[46].文獻[18]分別設計了T-SMT和R-SMT.T-SMT以程序執(zhí)行時間為優(yōu)化目標，使門操作序列中最后一個門操作的完成時間最小化.而R-SMT以程序執(zhí)行保真度為優(yōu)化目標，結(jié)合CNOT門和讀出操作錯誤率數(shù)據(jù)，設計了CNOT錯誤率與讀出操作錯誤率的加權目標函數(shù)，允許為不同種類的錯誤分配不同的權重.文獻[20]對量子程序執(zhí)行時的串擾錯誤進行了精準建模，并將串擾錯誤率結(jié)合至目標函數(shù)中，采用SMT求解器最小化串擾錯誤.文獻[43]介紹了一種最優(yōu)化方法OLSQ和近似最優(yōu)化方法TB-OLSQ，可對程序執(zhí)行保真度、插入SWAP數(shù)目、映射后線路深度三者中任一優(yōu)化目標進行優(yōu)化.TB-OLSQ在可被連續(xù)執(zhí)行的門操作集合之間插入SWAP操作，提升求解器求解效率，求得近似最優(yōu)解，保證程序執(zhí)行的保真度.TB-OLSQ針對量子近似優(yōu)化算法(quantum approximate optimization algorithm,QAOA)進行了特殊優(yōu)化，可縮減映射成本及映射后線路深度.TriQ[42]構(gòu)建了兩兩物理量子位之間交互的可靠性矩陣，并據(jù)此轉(zhuǎn)化量子程序映射問題為SMT問題，優(yōu)化程序的執(zhí)行保真度.TriQ對比了多個量子程序在不同量子計算平臺上的性能，揭示了量子芯片結(jié)構(gòu)對性能的影響.

2.2 啟發(fā)式方法

啟發(fā)式方法的代表性工作如表2所示.針對目標平臺，啟發(fā)式方法可分為2類：

Table 2 Heuristic Methods for Quantum Program Mapping表2 量子程序映射啟發(fā)式方法

1)針對簡化模型的啟發(fā)式算法.該類算法通常將量子芯片的拓撲結(jié)構(gòu)簡化為1D線性模型或2D網(wǎng)格模型.Shafaei等人依據(jù)最小線性排序(minimum linear arrangement,MinLA)問題，設計啟發(fā)式策略[47]，縮減映射時所需的SWAP操作數(shù)目.該策略將量子線路分割為多個子圖，并在每個子圖中應用MinLA問題求解最佳SWAP路徑.Wille等人[48]采用前瞻算法，對1D和2D兩種簡化模型，優(yōu)化插入的SWAP操作數(shù)，降低了56%的SWAP成本.Bhattacharjee等人[49]面向2D量子芯片網(wǎng)格模型，以插入的SWAP操作數(shù)為優(yōu)化目標，設計新的啟發(fā)式量子程序映射策略.通過3個步驟：選擇量子位、映射量子位和插入SWAP，降低了映射開銷.QURE[17]在為量子程序確定初始映射后，搜索2D網(wǎng)格模型中的同構(gòu)子圖.即在量子芯片上滑動包括了映射位置的矩形區(qū)域，預估不同位置下量子程序的執(zhí)行保真度.選擇可靠性最高的區(qū)域作為量子程序的最終映射區(qū)域.

2)針對特定量子芯片結(jié)構(gòu)的啟發(fā)式算法.該類算法可根據(jù)具體量子芯片架構(gòu)和錯誤率數(shù)據(jù)完成映射.Siraichi等人提出啟發(fā)式方法[33]，相比于最優(yōu)化方法，能處理更大規(guī)模的量子程序映射問題.該策略在初始映射中，最大化已滿足映射相鄰關系的雙量子位門數(shù)，之后插入SWAP進行映射轉(zhuǎn)換.Zulehner等人針對任意量子線路，設計啟發(fā)式映射策略[50].類似于文獻[36,40]，該策略首先根據(jù)數(shù)據(jù)依賴關系將量子線路劃分為多個相互獨立的層，每個層中的門操作可同時執(zhí)行；之后采用A*算法搜索相鄰層之間成本最低的映射轉(zhuǎn)換SWAP操作.此后，Zulehner等人針對特殊的SU(4)程序?qū)τ成洳呗赃M行了改進[27].該策略通過預處理步驟，對程序內(nèi)門操作進行分組，減小映射復雜度.之后采用A*算法進行映射，并進行映射后優(yōu)化，提升SU(4)程序執(zhí)行保真度.Tannu等人的工作[19]在文獻[50]的基礎上，引入了對量子計算機中錯誤率數(shù)據(jù)的分析，提出了考慮噪聲的量子程序映射算法，利用了健壯資源，提升了程序執(zhí)行保真度.Smith等人[51]利用連通樹映射算法，尋找最優(yōu)SWAP路徑，并在多個量子計算平臺上進行了評測，策略適用于不同的量子芯片拓撲結(jié)構(gòu).Siraichi等人[52]將量子位映射問題轉(zhuǎn)化為子圖同構(gòu)問題和令牌交換問題的組合，簡化量子位映射問題，利用已有的啟發(fā)式策略進行求解.SABRE[16]通過對量子程序映射轉(zhuǎn)換問題的精準建模，縮減了啟發(fā)式搜索空間，提供了更有效的SWAP操作，為量子程序映射算法帶來了指數(shù)級別的加速.Murali等人的工作[18]中進行了不同種啟發(fā)式策略和最優(yōu)化策略的對比.對比了2種啟發(fā)式映射方案的性能，分別為：優(yōu)先映射最頻繁使用的量子位和優(yōu)先映射最頻繁使用的連接.該工作認為啟發(fā)式方法具有更高的可擴展性，具有處理更大型量子程序映射問題的能力.Ding等人提出啟發(fā)式算法[53]，指導動態(tài)分配和回收量子位，利用量子位的局部性、量子程序的模塊性和并行性，復用量子位，將量子程序的執(zhí)行保真度提升了1.47倍.

3 基于社區(qū)劃分的初始映射構(gòu)建

3.1 先前策略的問題

量子程序的初始映射極為關鍵.對于單個量子程序而言，合適的初始映射可以幫助節(jié)約后續(xù)映射成本，提升量子程序的執(zhí)行保真度.而對于并發(fā)量子程序映射問題，合適的初始映射不僅可以縮減映射成本，還可以盡可能地利用量子計算機中的健壯資源，避免資源浪費，減小并發(fā)量子程序之間的干擾，提升整體執(zhí)行保真度.

量子計算機中健壯資源分布和物理拓撲結(jié)構(gòu)各不相同，先前的量子位初始映射策略通常利用貪心算法或啟發(fā)式搜索算法，將一個量子程序分配至量子計算機中最健壯的區(qū)域.圖4中虛線連接代表具有高錯誤率的不可靠連接，虛線框代表量子程序的映射位置.若一個具有4個量子位的量子程序需要被映射至如圖4所示的量子計算機上，它將會被映射至物理量子位Q1，Q2，Q5，Q6.映射策略通常選擇具有可靠連接的物理量子位，以提升執(zhí)行保真度.

Fig.4 An example for qubit mapping圖4 量子位映射示例

為了提升量子計算機的通量和資源利用率，并發(fā)量子程序映射策略應運而生[21].然而并發(fā)量子程序映射也為傳統(tǒng)量子程序映射策略帶來了新的挑戰(zhàn).盡管可以將并發(fā)量子程序合并為一個量子程序，采用傳統(tǒng)的面向單個量子程序的映射策略[16,18]進行映射.但傳統(tǒng)映射策略并不適合處理并發(fā)量子程序映射任務，可能導致3個問題：1)無法保證并發(fā)量子程序的執(zhí)行保真度.量子計算機中健壯資源有限，無法保證不同規(guī)模的量子程序都被分配足夠健壯的資源.2)并發(fā)量子程序數(shù)目無法在線進行調(diào)整.例如當并發(fā)量子程序執(zhí)行時，其中一個量子程序保真度大幅降低，傳統(tǒng)映射策略無法將并發(fā)量子程序組合回退為單獨執(zhí)行.3)傳統(tǒng)映射策略無法利用并發(fā)量子程序映射問題中新的優(yōu)化契機.例如，采用跨程序SWAP操作可減少并發(fā)量子程序的映射成本.

現(xiàn)有的并發(fā)量子程序映射策略[21]允許并發(fā)執(zhí)行2個量子程序，但其資源利用率和執(zhí)行保真度仍有待提升.下面在圖5中以一個例子來說明現(xiàn)有的并發(fā)量子程序映射策略面臨資源利用率低的問題.使用現(xiàn)有的并發(fā)量子程序映射算法時，大規(guī)模的健壯物理量子位集合可能會被割裂為規(guī)模較小的量子位集合碎片.這些碎片中僅包含很少的物理量子位，不足以映射任何量子程序，導致健壯資源未被利用.

Fig.5 Previous initial mapping technique incurs resource under-utilization圖5 先前的初始映射策略導致資源利用率低

圖5展示了采用先前工作[21]中提出的FRP策略構(gòu)建量子程序初始映射的例子.圖5中有2個量子程序P1(5量子位)和P2(4量子位)需被映射至IBM-Q16上.圖5中展示了量子計算機IBM-Q16的物理結(jié)構(gòu)圖，其錯誤率標定數(shù)據(jù)采集于2019年12月27日.具有較高錯誤率的不可靠連接在圖中被標注為虛線，不可靠的量子位同樣進行了標注.P1先被映射.FRP策略從量子計算機中的一個具有足夠多高utility值的鄰居的量子位開始，擴展分配區(qū)域.該策略定義指標utility為：一個量子位所包含的連接數(shù)/連接上CNOT操作錯誤率之和[21].因此，物理量子位Q3，Q4，Q5，Q9和Q10被用于映射量子程序P1.P1映射完成后，映射策略無法為P2找到映射位置.因為在Q0～Q2，Q11～Q14中無法找到一個具有足夠多健壯鄰居的分配起點；而Q6～Q8僅包含3個量子位，無法供P2分配，造成了資源浪費.實際上存在更好的映射方法，能使量子計算機中的可靠資源得到充分利用，減少資源浪費.

3.2 算法設計

對于并發(fā)量子程序映射，我們觀察到3點現(xiàn)象：1)量子芯片上的健壯量子位和連接是有限的.2)量子芯片上的某些量子位與周圍的量子位有更多的連接.如圖2所示，Q1與3個相鄰的物理量子位相連，而Q7僅與1個量子位相連.3)一個量子程序的量子位應當被映射到鄰近的物理量子位上.并發(fā)量子程序之間的初始映射應避免相互干擾，公平利用量子計算機中的健壯資源.

本文針對并發(fā)量子程序映射問題提出了一種新的映射策略，即社區(qū)發(fā)現(xiàn)輔助的量子位劃分(CDAQP)算法.該算法首先構(gòu)造一棵由量子位組成的層次樹，協(xié)助搜索量子計算機中緊密連接的健壯量子位集合.圖6展示了CDAQP算法的框架.CDAQP根據(jù)從IBMQ接口[11]獲得的量子芯片拓撲結(jié)構(gòu)和錯誤率標定數(shù)據(jù)構(gòu)建層次樹.在層次樹中，葉節(jié)點表示特定的物理量子位；中間節(jié)點表示其子節(jié)點的并集.層次樹構(gòu)建完成之后，CDAQP自底向上迭代層次樹，查找可用于初始分配的社區(qū).最后，根據(jù)貪心策略分配量子位.詳細說明如下.

Fig.6 Qubit mapping framework by using CDAQP algorithm圖6 CDAQP算法量子位映射框架

1)層次樹構(gòu)建

層次樹是對量子芯片中健壯資源分布的建模，有助于定位量子芯片上健壯的量子位和連接.算法1基于fast-Newman(FN)社區(qū)檢測算法[54]構(gòu)建層次樹.該算法將物理量子位劃分為社區(qū).一個社區(qū)中的物理量子位具有可靠且緊密的相互連接.相反，社區(qū)與社區(qū)之間的連接具有相對較低的可靠度.

算法1.層次樹構(gòu)建算法.

輸入：量子計算機拓撲結(jié)構(gòu)圖、錯誤率標定數(shù)據(jù)；

輸出：層次樹HT.

①HT←list()；/*初始化HT為空列表*/

② 為每個量子位在HT中創(chuàng)建一個葉節(jié)點；

③ whileHT.length>1 do

④ 選擇HT中能使f(A,B)值最大的

2項A和B；

⑤ 合并A，B為新節(jié)點New_Node，并將A，

B分別設置為New_Node的左右子樹；

⑥HT.append(New_Node)；

⑦HT.remove(A)；

⑧HT.remove(B)；

⑨ end while

⑩ returnHT.

算法初始化時，每個物理量子位對應一個社區(qū)，即層次樹中的一個葉節(jié)點.算法不斷合并能夠使獎勵函數(shù)f最大化的2個社區(qū)，直到最終只剩下一個包含所有物理量子位的社區(qū).在該過程中，每個社區(qū)對應層次樹中的一個節(jié)點，該節(jié)點是可用于分配量子位的一個候選區(qū)域.獎勵函數(shù)f被定義為合并2個社區(qū)所帶來的收益：

f=Qmerged-Qorigin+ωEV,

(1)

層次樹有3個特點：1)層次樹中的每一個節(jié)點都是可用于初始映射的候選量子位集合.2)在一個社區(qū)中的物理量子位相互連接緊密，能夠幫助減小量子程序映射成本.3)具有低讀出操作錯誤率和健壯連接的量子位會優(yōu)先被合并.因此量子位集合越健壯，其在層次樹中的深度就越深.層次樹的這些特點能夠幫助定位量子計算機上的健壯資源，為量子程序提供更優(yōu)秀的初始映射.

接下來，采用圖6中的例子解釋為何層次樹能幫助選擇健壯的初始映射.圖6中，左側(cè)展示了IBMQ London的物理結(jié)構(gòu)圖，每個節(jié)點對應的數(shù)值代表該物理量子位上讀出操作的錯誤率，在連接上的數(shù)值代表該連接上的CNOT操作錯誤率.接著展示了根據(jù)拓撲結(jié)構(gòu)和錯誤率數(shù)據(jù)構(gòu)建出的層次樹.層次樹構(gòu)建過程為：①Q(mào)0和Q1之間具有最低的錯誤率，因此它們被首先合并為一個社區(qū).②雖然Q1，Q3間的CNOT操作錯誤率低于Q1，Q2間的CNOT操作錯誤率，但Q2被首先加入社區(qū){Q0，Q1}.這是因為算法傾向于將連接緊密的量子位合并為一個社區(qū)，從而避免量子計算機中健壯資源的浪費.同樣，Q3，Q4也被合并為一個社區(qū).③所有的物理量子位被合并為一個社區(qū)，形成層次樹的根節(jié)點.算法不僅考慮量子計算機中的資源可靠性，也同樣考慮量子計算機的物理拓撲結(jié)構(gòu)，選取連接緊密的量子位.這可以避免量子計算機中健壯資源的浪費，提高資源利用率，能使量子計算機映射更多的量子程序.

錯誤率標定數(shù)據(jù)并非隨時改變，IBM量子計算云服務約每24 h標定一次錯誤率數(shù)據(jù).因此在錯誤率標定的一個周期內(nèi)，構(gòu)建的層次樹可被存儲，以供重復使用，不會造成不可接受的運算開銷.

2)量子位劃分和分配

算法2根據(jù)層次樹將量子位劃分為多個區(qū)域供并發(fā)量子程序進行初始映射.算法優(yōu)先為具有高CNOTdensity的量子程序劃分區(qū)域.CNOTdensity被定義為一個程序內(nèi)CNOT操作數(shù)/該程序內(nèi)量子位數(shù).對于每個量子程序，算法自底向上搜索層次樹，找到可供分配的量子位集合.選擇具有最低平均錯誤率的候選量子位集合用于映射該程序.最后，使用最大權重邊優(yōu)先(greatest weighted edge first)策略[18]進行量子位映射.該策略將量子程序中交互數(shù)目最高的2個邏輯量子位映射到量子芯片上最健壯的邊上，有助于生成具有高可靠性和低映射開銷的初始映射.

算法2.量子位劃分算法.

輸入：層次樹HT、量子程序programs；

輸出：量子位劃分partition.

① 將programs按CNOTdensity降序排序；

② forprograminprograms

③C←set()；

/*初始化候選節(jié)點C為空集*/

④ forlinHT.leaves

/*對于HT中的每個葉節(jié)點l*/

⑤candidate←search(l)；/*從l起自底向上搜索層次樹，得到量子位數(shù)目滿足待映射程序要求的節(jié)點candidate*/

⑥C.add(candidate)；

⑦ end for

⑧ ifC為空

⑨ 失敗，回退至單獨執(zhí)行；

⑩ end if

他節(jié)點的路徑

3.3 權重參數(shù)選擇

在式(1)中，E表示量子位之間連接的可靠性，V表示量子位讀出操作的可靠性.該設計能幫助在每次迭代中，將具有健壯連接和較低讀出錯誤率的可靠量子位合并到一個特定的社區(qū)中.不可靠的量子位最終才將被添加到社區(qū)中.在執(zhí)行量子位分配時，CDAQP自底向上搜索層次樹，查找初始分配的候選區(qū)域.不可靠的量子位不易被選擇，提高了整體可靠性.

使用CDAQP可能會導致分配給一個量子程序的物理量子位數(shù)目大于該量子程序真正所需的物理量子位數(shù)目.例如一個具有4個邏輯量子位的量子程序被映射到圖6中所示的量子芯片上.唯一可能的分配區(qū)域是該層次樹的根節(jié)點：{Q0，Q1，Q2，Q3，Q4}.這會導致一個量子位冗余.為了避免浪費，未被使用的冗余量子位會被標記，它們可以被添加到相鄰的社區(qū)，用于其他量子程序的初始映射.

對于層次樹中的一個節(jié)點，本文定義最大冗余量子位數(shù)，代表當一個量子位集合(一個層次樹節(jié)點)被分配給一個量子程序進行初始映射時，可能導致的最大未被使用的物理量子位數(shù)目.一個層次樹節(jié)點node對應的最大冗余量子位數(shù)可計算為：node.n_qubits-(1+max(node.left.n_qubits,node.right.n_qubits)).

獎勵函數(shù)f中的權重參數(shù)ω的增大會導致層次樹的退化，即層次樹的每次合并過程中，僅有一個包含一個物理量子位的葉節(jié)點被合并入新社區(qū).這時，新社區(qū)對應的層次樹節(jié)點的最大冗余量子位數(shù)為0.即ω的增大可以導致平均最大冗余量子位數(shù)的減小.我們連續(xù)21天采集了IBM-Q16的錯誤率標定數(shù)據(jù).對于每天的錯誤率標定數(shù)據(jù)，按0.05的步長從0～2.5變化ω的值，執(zhí)行算法1，并記錄層次樹中冗余量子位的平均數(shù)量，如圖7所示.圖7中節(jié)點顏色越深代表越多結(jié)果重疊在該位置上.采取肘部原則，取ω=0.95.在這種情況下，CDAQP算法既考慮了物理拓撲結(jié)構(gòu)，又考慮了錯誤率數(shù)據(jù).平均冗余量子位數(shù)在這種情況下為0.29.在IBM-Q50上進行了相同的實驗，ω=0.40.此外，CDAQP不僅可以為并發(fā)量子程序提供可靠的初始映射，同樣可以處理只有一個量子程序需要映射的問題.

Fig.7 Select the knee solution as ω圖7 選取肘部方案為ω的值

4 跨程序SWAP映射轉(zhuǎn)換

4.1 跨程序SWAP操作優(yōu)勢分析

并發(fā)量子程序映射問題為傳統(tǒng)映射轉(zhuǎn)換策略帶來了新的挑戰(zhàn).當多個量子程序同時運行時，映射轉(zhuǎn)換所需插入的SWAP數(shù)目可能增加.先前的并發(fā)量子程序映射轉(zhuǎn)換策略[21]順序處理每一個量子程序，后被處理的程序只能使用未被其他程序占用的量子位.對于一個特定量子程序來說，要使用SWAP操作移動量子位，使2個量子位相鄰，最短SWAP路徑可能涉及到多個量子位.SWAP操作只在相鄰的量子位之間進行.如果最短SWAP路徑上的任何一個量子位被其他程序占用，將引入更多的SWAP操作，導致整體的可靠性下降.

優(yōu)秀的映射轉(zhuǎn)換策略應當能夠更好地利用所有可能的SWAP操作，在最大程度上降低量子程序映射轉(zhuǎn)換的開銷.本文提出了引入跨程序SWAP操作的映射轉(zhuǎn)換算法X-SWAP.與先前映射轉(zhuǎn)換策略不同，該算法并非單獨處理每個量子程序，而是對所有并發(fā)量子程序同時進行映射轉(zhuǎn)換.X-SWAP既允許程序內(nèi)SWAP操作，又允許跨程序SWAP操作.SWAP操作涉及到的2個物理量子位可能分別屬于2個量子程序(跨程序SWAP)，也可能只屬于1個量子程序(程序內(nèi)SWAP).SWAP所涉及到的邏輯量子位上的后續(xù)門操作都需在SWAP操作之后執(zhí)行.

該算法允許在所有物理量子位上執(zhí)行SWAP，避免了先前策略中由于量子位被占用而導致的額外SWAP開銷.另外，當2個量子程序映射相鄰時，啟用跨程序SWAP操作能夠幫助縮減映射轉(zhuǎn)換成本.X-SWAP相比于之前的映射轉(zhuǎn)換策略的主要優(yōu)點在于擴大了啟發(fā)式搜索空間，涵蓋了更多的量子位，引入更多可能的SWAP操作.

在下面2種情況下，跨程序SWAP操作優(yōu)于程序內(nèi)SWAP操作：

1)1個跨程序SWAP操作可以替代2個程序內(nèi)SWAP操作.圖8展示了將2個量子程序映射到具有6個物理量子位的量子計算機上的例子.圖8(a)展示了需要映射的2個量子程序，圖8(b)展示了2個量子程序的初始映射，以及在不允許跨程序SWAP操作情況下的映射過程.對于量子程序P1，g1和g2可以直接執(zhí)行，無需插入SWAP操作，但g3卻不能直接執(zhí)行，需在q2和q3之間插入SWAP操作.同理，對于量子程序P2，為了使g6能夠執(zhí)行，需要在q4和q6之間插入SWAP操作.

Fig.8 An inter-program SWAP can replace two intra-program SWAPs圖8 跨程序SWAP操作可替換2個程序內(nèi)SWAP操作

然而，如果2個程序同時映射，可以引入跨程序SWAP操作降低量子程序的映射成本.圖8(c)展示了使用跨程序SWAP操作進行映射轉(zhuǎn)換的例子，只需要在q1與q5之間插入一個SWAP操作，即可完成映射轉(zhuǎn)換.在這種情況下，q1與q5之間的一個SWAP操作代替了2個SWAP操作，降低了量子程序的映射成本，間接提升了量子程序執(zhí)行保真度.

2)在進行映射轉(zhuǎn)換時，跨程序SWAP操作可采取捷徑.圖9中，P1和P2被映射到具有9個物理量子位的量子計算機上.接下來需要處理門操作CNOTq1q5.如圖9(b)所示，先前工作中的映射轉(zhuǎn)換策略[21]需引入{q1，q2}，{q1，q3}，{q1，q4}這3個SWAP操作才能完成映射轉(zhuǎn)換，而跨程序SWAP操作僅需引入一個SWAP操作{q1，q9}.

Fig.9 Inter-program SWAPs take shortcuts圖9 跨程序SWAP可采取捷徑

4.2 啟發(fā)式搜索空間設計

由于單量子位門操作可以直接執(zhí)行，無需SWAP操作.因此在映射轉(zhuǎn)換過程中僅考慮CNOT門操作.對于一個量子程序P，圖10展示了P中的關鍵門(critical gates,CG)操作.該量子線路的CNOT門操作可以分為4層(即l1～l4).同一層中的門操作不涉及相同的邏輯量子位，可以同時執(zhí)行.l1是P的首層門操作(front layer，記為F)，它表示P的有向無環(huán)圖(DAG)中沒有未執(zhí)行前驅(qū)節(jié)點的CNOT門操作的集合.DAG展示了P的數(shù)據(jù)依賴關系.關鍵門操作CG表示F中在第2層(l2)上擁有后繼節(jié)點的門操作的集合.例如，在F中，g1在l2中擁有后繼節(jié)點g3，而g2沒有后繼.因此，g1屬于關鍵門操作，但g2不屬于.如果執(zhí)行了關鍵門操作g1，并將其從DAG中移除，g3就可被執(zhí)行，首層門操作集合F也同時被更新.相比之下，優(yōu)先處理g2不會幫助更新首層門操作F.

Fig.10 Critical gates圖10 關鍵門

對于每個程序Pi，如果其首層門操作集合中存在滿足映射位置約束條件可直接執(zhí)行的門操作，則執(zhí)行該門操作，將其從DAGi中移除，并更新首層門操作集合.當所有程序的首層門操作集合中都沒有可以直接執(zhí)行的門操作時，需要插入SWAP，交換邏輯量子位的映射位置，將不可執(zhí)行的門操作涉及的邏輯量子位移動到相鄰的映射位置，從而使該門操作能被執(zhí)行.為了快速更新首層門操作，縮小映射后線路深度，需要優(yōu)先處理關鍵門操作.本文中的方法僅搜索與關鍵門操作涉及到的邏輯量子位相關的SWAP操作.

圖11展示了一個量子程序映射轉(zhuǎn)換的例子，其中g1和g3為關鍵門操作，所有與g1和g3中涉及到的邏輯量子位相關的SWAP操作被加入到候選SWAP操作中，通過啟發(fā)式函數(shù)選出候選SWAP操作中的最優(yōu)SWAP操作.當該SWAP操作被插入原線路后，量子程序映射被更新，一些原先不可執(zhí)行的CNOT門操作可能變?yōu)榭蓤?zhí)行.重復迭代該過程，直到DAG中的所有CNOT操作都可執(zhí)行.

Fig.11 SWAPs associated with critical gates圖11 與關鍵門操作相關的SWAP操作

4.3 啟發(fā)式成本函數(shù)設計

啟發(fā)式函數(shù)負責從啟發(fā)式搜索空間中所有的候選SWAP操作中找到最佳SWAP.本文設計了新的啟發(fā)式成本函數(shù)，利用并發(fā)量子程序映射問題的特點，鼓勵高效跨程序SWAP操作的執(zhí)行.

量子程序映射策略應使每個量子程序中各個量子位的映射位置相互靠近.否則，若2個量子位映射位置較遠，如果要在這2個量子位之間執(zhí)行CNOT操作，會引發(fā)很高的SWAP開銷.SABRE[16]中使用了最近鄰成本(nearest neighbor cost,NNC)函數(shù)來估算SWAP成本，進行量子程序映射.本文將SABRE[16]使用的NNC函數(shù)H用作啟發(fā)式函數(shù)的一部分.H表示首層門操作集合的成本和擴展門操作集合的成本之和.擴展門操作集合是DAG中在首層門操作集合之后執(zhí)行的n個(n默認等于邏輯量子位數(shù))CNOT門操作的集合.每個門操作集合的成本計算為該集合中所有CNOT門的平均SWAP路徑長度.

例如，在圖9(b)中，由于需要1個跨程序SWAP或3個程序內(nèi)SWAP來滿足CNOTq1，q5的約束，

(2)

定義啟發(fā)式函數(shù)為

score(SWAP)=H(SWAP)+

(3)

因為不同首層門操作集合的大小不同，因此采用首層門操作的大小對gain進行標準化.當SWAP處于門操作g的最短SWAP路徑上時，指示函數(shù)I(SWAP,g)=1，否則指示函數(shù)I(SWAP,g)=0.在最短路上的SWAP操作被鼓勵執(zhí)行.候選SWAP中具有最小啟發(fā)式函數(shù)值的SWAP操作是最優(yōu)的SWAP操作.跨程序SWAP量子程序映射轉(zhuǎn)換算法如算法3所示.

算法3.量子程序映射轉(zhuǎn)換算法.

輸入：量子芯片拓撲結(jié)構(gòu)G、量子程序programs、初始映射mapping；

輸出：最終調(diào)度schedule.

① 為每個程序生成一個DAG；

② 為每個DAG生成一個首層門操作集合F；

③ while 并非所有的CNOT門操作都可執(zhí)行

④ if 在F中存在能夠直接執(zhí)行的門操作

⑤ 添加能直接執(zhí)行的門操作到schedule；

⑥ 將能直接執(zhí)行的門操作從DAG中移除，更新F；

⑦ else

⑧ for eachF

⑨ 將F中在第2層有鄰接CNOT操作的CNOT操作添加入關鍵門操作集合CG；

⑩ end for

SWAP操作到候選SWAP集合；

score(SWAP)最小的SWAP；

5 映射任務調(diào)度器

盡管已有針對并發(fā)量子程序映射的機制[21]，但選擇并發(fā)量子程序組合仍有挑戰(zhàn)性.現(xiàn)在的并發(fā)量子程序組合由用戶指定，這可能導致3個問題：1)量子計算機資源未得到充分利用.2)隨機選擇的組合可能會導致保真度大幅降低.3)必須引入結(jié)果驗證機制，這會帶來額外的系統(tǒng)修改開銷.本文提出了一種并發(fā)量子程序映射任務調(diào)度器的設計，用來選擇合適的并發(fā)量子程序組合.圖12展示了其工作流程.

Fig.12 The framework of the quantum program mapping task scheduler圖12 量子程序映射任務調(diào)度器框架

我們的設計選擇最優(yōu)的量子程序組合，最大限度地提高了量子程序的執(zhí)行保真度和量子計算機的資源利用率.對于調(diào)度隊列首的任務，調(diào)度器檢查任務隊列中是否存在能夠與隊列首任務并發(fā)執(zhí)行，且造成的保真度損失可被接受的其他量子程序.如果存在，則將它們與隊列首任務同時映射到量子計算機上執(zhí)行；否則，單獨映射并執(zhí)行隊列首任務.

本文提出了預估實驗成功率(estimated pro-bability of a successful trial,EPST)，用來估計在特定量子芯片上執(zhí)行量子程序的保真度.Sep_EPST表示程序單獨映射時可以達到的最高EPST.為了計算Sep_EPST，需要對任務集合中的每個量子程序單獨調(diào)用一次算法2，為其分配一個物理量子位集合.而Co_EPST表示多個程序共同映射在量子芯片上時的EPST.為了計算Co_EPST，需要調(diào)用算法2，為集合中所有的并發(fā)量子程序共同劃分初始映射區(qū)域.EPST定義為

(4)

其中,r2q,r1q和rro分別表示CNOT、單量子位門操作和所分配的物理量子位的讀出操作的平均可靠度.|CNOTs|，|1q gates|和|qubits|分別表示量子程序的CNOT門數(shù)、單量子位門數(shù)和邏輯量子位數(shù).EPST高表示量子程序被映射到更健壯的區(qū)域，并且在實際執(zhí)行期間程序的執(zhí)行保真度更高.

對于特定的量子程序組合，調(diào)度器根據(jù)Sep_EPST和Co_EPST計算預估實驗成功率損失EPST_violation.如果EPST_violation小于閾值ε，則該量子程序組合可以并發(fā)執(zhí)行.該調(diào)度器支持在1臺量子計算機上并發(fā)執(zhí)行2個以上的程序.為了確保調(diào)度器的效率和調(diào)度的公平性，僅搜索任務隊列中的前N個任務(默認N=10)，限制并發(fā)程序數(shù)目不超過M(默認M=3).更多細節(jié)見算法4.

算法4.映射任務調(diào)度算法.

輸入：調(diào)度任務隊列J.

① whileJ中仍有任務未被調(diào)度

② 初始化cur_job_set為僅包含J中第1項任務的列表；

③idx←1；

④ whileidx

cur_job_set.length

⑤cur_job_set.append(J[idx]);

⑥ forjobincur_job_set

⑦ 計算job的Sep_EPST，Co_EPST;

⑧ 計算job的EPST_violation=1-(Co_EPST/Sep_EPST);

⑨ ifEPST_violation>ε

⑩cur_job_set.remove(J[idx]);

6 實驗評測

6.1 評測方法

1)評測指標

① 實驗成功率(probability of a successful trial,PST).PST用于評估量子程序執(zhí)行保真度，PST被定義為實驗中能夠產(chǎn)生正確結(jié)果的執(zhí)行次數(shù)占總執(zhí)行次數(shù)的比例.我們在量子計算機上對每個工作負載進行映射，執(zhí)行8 024次，統(tǒng)計PST.

② 映射后量子門數(shù)量.我們使用映射后CNOT門操作的數(shù)量來評估映射策略在映射并發(fā)量子程序時縮減映射成本的能力.

③ 映射后量子線路深度.我們使用映射后量子程序的線路深度評估映射策略緩減保持性錯誤的能力.

④ 執(zhí)行次數(shù)減小因數(shù)(trial reduction factor,TRF).TRF用于評估并發(fā)量子程序映射策略帶來的通量的提升.TRF被定義為獨立執(zhí)行多個程序時所需的執(zhí)行次數(shù)與啟用并發(fā)量子程序映射時所需的執(zhí)行次數(shù)之比.

2)量子芯片

我們在IBM-Q16[11]和IBM-Q50[11]上進行評估，它們的量子位拓撲結(jié)構(gòu)分別如圖2和圖13所示，其中IBM-Q16可通過IBM接口[11]訪問.而IBM-Q50并不公開，我們模擬了IBM-Q50芯片用于映射成本評估.模擬芯片包括拓撲信息和錯誤率數(shù)據(jù).我們使用均勻分布隨機模型，在IBM-Q16每個屬性最大值和最小值的范圍內(nèi)生成了IBM-Q50的錯誤率數(shù)據(jù).

Fig.13 Qubit topology of IBM-Q50圖13 IBM-Q50的量子位拓撲結(jié)構(gòu)

3)數(shù)據(jù)集

我們采用先前研究中使用的數(shù)據(jù)集，包括SABRE[16],QASM-Bench[55],RevLib[56]和文獻[50]中使用的數(shù)據(jù)集.如表3所示，微型/小型量子程序大約有5個量子位和數(shù)十個CNOT門；大型程序大約有10個量子位和數(shù)百個CNOT門.

Table 3 Benchmarks Used in the Evaluation表3 實驗評測中所用的工作集

4)對比實驗

① 單獨執(zhí)行.使用Qiskit[26]中優(yōu)化級別最高的算法分別映射和執(zhí)行工作負載中的每個程序.它們代表最可靠的情況，沒有并發(fā)程序之間的干擾.

② 并發(fā)基準.采用文獻[21]中提出的策略，用FRP策略生成并發(fā)量子程序的初始映射，用引進基于錯誤率的優(yōu)化的SABRE進行映射轉(zhuǎn)換.

③ SABRE[16].SABRE是一種以SWAP操作數(shù)為優(yōu)化目標的啟發(fā)式映射方法.該策略被用于映射多個并發(fā)量子程序合并成的量子線路.

本文中的策略被細分為：僅使用CDAQP、僅使用X-SWAP，以及同時使用CDAQP和X-SWAP.其中，僅使用CDAQP的方法采用了與SABRE相同的映射轉(zhuǎn)換方法，僅使用X-SWAP的方法使用了與SABRE相同的初始映射策略.

6.2 程序執(zhí)行保真度評測

本文使用微型/小型量子程序組合進行保真度評測.表4展示了在IBM-Q16上執(zhí)行的包含2個程序的工作負載的PST.相同程序組合下的實驗均在IBM-Q16的一個錯誤率標定周期內(nèi)完成，即量子計算機的錯誤率標定數(shù)據(jù)相同.量子程序的兩兩組合可以使量子計算機的通量提高一倍.但是，由于資源沖突和串擾，量子程序的執(zhí)行可靠性可能會降低.在大多數(shù)情況下，并發(fā)量子程序映射的平均PST低于單獨執(zhí)行情況下的平均PST.但本文的方法仍優(yōu)于其他并發(fā)量子程序映射策略.對于微型程序組合，本文的方法(CDAQP+X-SWAP)、單獨執(zhí)行、SABRE和并發(fā)基準的平均PST分別為58.2%，69.8%，44.8%和45.3%；對于小型工作負載，相應的平均PST分別為16.8%，23.8%，10.3%和12.4%.本文方法的執(zhí)行保真度比SABRE和并發(fā)基準分別平均高出9.9%和8.6%.這表明本文的方法提供了更可靠的結(jié)果，并且減少了保真度的損失.

Table 4 PST Comparison Between Multiple Strategies on IBM-Q16表4 IBM-Q16上多種策略PST的對比 %

本文的方法主要受益于CDAQP策略.CDAQP提供了更好的初始映射來提高保真度，這使得并發(fā)量子程序執(zhí)行時的保真度接近甚至超過單獨執(zhí)行情況下的保真度.如表4所示，在bv_n3和fredkin_3組合中，僅使用CDAQP的策略通過提供更好的初始映射，使保真度比并發(fā)基準顯著提高了19.1%.CDAQP相對于并發(fā)基準的優(yōu)勢來自2個方面：1)在可靠量子位和連接上運行的量子門具有較低的錯誤率.2)較好的初始分配降低了映射轉(zhuǎn)換時的SWAP開銷.總體上，僅使用CDAQP的策略減少了并發(fā)量子程序映射帶來的保真度下降，保真度相較于并發(fā)基準高出4.7%.

僅使用X-SWAP的策略在提升保真度方面沒有體現(xiàn)出顯著優(yōu)勢，這是因為：1)映射小型量子程序需要很少的SWAP操作，因此X-SWAP在這種情況下很難節(jié)省SWAP.2)在IBM-Q16這種結(jié)構(gòu)簡單的量子芯片上，初始映射對小型量子程序的可靠性有很大影響.3)量子程序映射位置可能不相鄰，難以執(zhí)行跨程序SWAP.但是，X-SWAP在具有更多量子位的芯片上卻能有較好的表現(xiàn).

6.3 映射成本評測

X-SWAP在更大的啟發(fā)式搜索空間中表現(xiàn)更好.當多個更大規(guī)模的量子程序在具有更多量子位的量子芯片上并發(fā)運行時，X-SWAP能體現(xiàn)出更優(yōu)的性能.本文將映射后量子門操作的數(shù)量和線路深度作為評價標準，評估IBM-Q50上4程序工作負載的映射開銷.工作負載隨機選擇，旨在覆蓋盡可能多的正交程序組合.對于每個工作負載和每個策略，本文采用5次實驗中的最佳結(jié)果(類似于文獻[16]).實驗結(jié)果如表5所示.

Table 5 Mapping Overheads Comparison of 4-program Workloads on IBM-Q50表5 IBM-Q50上的4程序工作集映射成本對比

SABRE[16]使用反向遍歷技術和啟發(fā)式搜索方案，最小化插入SWAP的數(shù)量.然而，因SABRE在初始映射時并未考慮局部性原理，在映射并發(fā)量子程序工作負載時，并發(fā)量子程序的SWAP 路徑存在交疊，引發(fā)了更多的SWAP操作，無法獲得最優(yōu)映射方案.并發(fā)基準在劃分量子位時會考慮局部性，但在并發(fā)量子程序之間會引入資源沖突，導致冗余的SWAP操作.實驗結(jié)果表明，并發(fā)基準的映射后CNOT門操作數(shù)平均比SABRE高4.0%，映射后線路深度平均比SABRE高6.8%.

平均而言，僅使用CDAQP在映射后CNOT門的數(shù)量上比SABRE高2.7%，在線路深度上比SABRE高6.8%.雖然CDAQP能夠幫助找到量子位緊密相連的初始映射.幫助減小映射開銷，但效果并不顯著.在個別情況下(如Mix_9)，僅使用CDAQP反而造成了比其他策略還高的映射開銷.其原因是：CDAQP的主要優(yōu)化目標是提升初始映射的保真度.降低映射開銷(即用最少的SWAP完成量子程序映射)并不是CDAQP的首要任務.僅采用X-SWAP的策略使用了與SABRE相同的初始映射方法，允許執(zhí)行跨程序SWAP操作，優(yōu)先處理關鍵門操作，有效地將映射后門操作的數(shù)量縮減了8.8%，并將映射后線路深度縮減了9.2%.原因包括2個方面：1)X-SWAP利用跨程序SWAP，采取捷徑，節(jié)省映射開銷.2)通過優(yōu)先處理關鍵門操作，X-SWAP可提供更高效的SWAP，縮減映射開銷和映射后線路深度.

在本文的設計中，CDAQP可以生成可靠且緊密相連的初始映射，而X-SWAP則用于減少映射開銷.同時應用CDAQP和X-SWAP可提升性能：與并發(fā)基準和SABRE相比，映射后門操作數(shù)分別減少了11.6%和8.6%；與并發(fā)基準和SABRE相比，線路深度分別降低了16.0%和10.3%.表5展示了更詳細的數(shù)據(jù).

此外，本工作具有可擴展性。本工作不僅能夠降低IBM-Q50上的4程序工作負載的映射開銷，還能在更大規(guī)模的量子芯片上運行.這是因為：1)CDAQP中所采用的社區(qū)檢測方法已被證明對于大型網(wǎng)絡是有效的.2)無論量子芯片規(guī)模大小，只要量子程序映射位置鄰接，X-SWAP就可以起到減少映射開銷的作用.

6.4 任務調(diào)度器評測

本文采用表3中的微型/小型量子程序構(gòu)造了一個映射任務隊列，并使用任務調(diào)度器進行調(diào)度.從0.05～0.20變更閾值ε，在每種情況下分別進行調(diào)度，工作負載的PST均值和TRF如圖14所示.圖14還展示了在每個程序單獨執(zhí)行和程序兩兩隨機組合情況下的性能.

Fig.14 Performance of the task compiler圖14 任務調(diào)度器性能

單獨執(zhí)行情況下，TRF為1(無并發(fā))，平均PST為35.9%，是該任務隊列能夠達到的最高平均PST.程序兩兩隨機組合情況下的平均PST最低，僅為25.1%，但TRF達到2(2個程序并發(fā)).當ε=0.15(即僅允許EPST損失小于15%的并發(fā)量子程序映射情況)時，調(diào)度器性能最好.在這種情況下，工作負載的平均保真度為30.1%，比兩兩隨機組合的工作負載高出5.0%；TRF為1.429，與單獨執(zhí)行的情況相比，吞吐量提高了42.9%.實驗結(jié)果表明，本文的映射任務調(diào)度器可以用于權衡量子計算機的吞吐量和保真度.

7 總 結(jié)

量子計算和量子計算云服務逐漸興起.當前云環(huán)境下的量子計算機面臨著資源利用率低、保真度低、錯誤率高等問題.本文對面向超導量子芯片的量子程序映射技術進行了綜述，深入剖析了不同類別映射技術的特點和區(qū)別.并針對云環(huán)境下的并發(fā)量子程序映射問題提出了一種新的映射策略，提升并發(fā)量子程序的執(zhí)行保真度和資源利用率.本文設計的系統(tǒng)是一個面向量子計算機的操作系統(tǒng)原型QuOS.希望我們的工作能幫助相關領域未來的研究人員.