竇星磊 劉 磊 陳岳濤

(計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院計(jì)算技術(shù)研究所) 北京 100190) (中國科學(xué)院計(jì)算技術(shù)研究所 北京 100190)

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

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

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

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

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

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

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

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

1 量子計(jì)算概述

1.1 量子計(jì)算

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

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

1.2 量子計(jì)算機(jī)

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

Fig.2 Qubit topology of IBMQ Melbourne圖2 IBMQ Melbourne的量子位拓?fù)浣Y(jié)構(gòu)

1.3 量子計(jì)算機(jī)中的錯(cuò)誤

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

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

1.4 量子程序映射

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

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

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

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

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

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

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

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

2 量子程序映射技術(shù)概覽

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

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

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

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

2.1 最優(yōu)化方法

本文對(duì)具有代表性的最優(yōu)化方法進(jìn)行了整理匯總，如表1所示.現(xiàn)有工作中，量子程序映射問題可等價(jià)轉(zhuǎn)化為如下類型數(shù)學(xué)問題：可滿足性(Boolean satisfiability,SAT)問題、可滿足性模理論(satis-fiability modulo theories,SMT)問題、偽布爾優(yōu)化(pseudo Boolean optimization,PBO)問題、動(dòng)態(tài)規(guī)劃(dynamic programming,DP)問題、時(shí)序規(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)化為等價(jià)數(shù)學(xué)優(yōu)化問題，需轉(zhuǎn)化的內(nèi)容一般包括：1)待優(yōu)化變量.量子程序映射過程中，邏輯量子位的映射位置、門操作的執(zhí)行時(shí)刻、SWAP路徑均需轉(zhuǎn)換為等價(jià)數(shù)學(xué)優(yōu)化問題中的待優(yōu)化變量，以便于求解.2)約束條件.須將量子程序映射問題中的限制條件(如門操作需順序執(zhí)行、每個(gè)物理量子位僅允許映射一個(gè)邏輯量子位等)轉(zhuǎn)換為等價(jià)數(shù)學(xué)優(yōu)化問題中的限制條件.3)優(yōu)化目標(biāo).優(yōu)化目標(biāo)通常包括程序執(zhí)行保真度、映射過程中插入的SWAP操作數(shù)目、映射后線路深度(或程序執(zhí)行時(shí)間)3種.

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

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

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

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

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

2.2 啟發(fā)式方法

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

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

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

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

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

3.1 先前策略的問題

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

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

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

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

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

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

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

3.2 算法設(shè)計(jì)

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

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

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

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

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

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

輸入：量子計(jì)算機(jī)拓?fù)浣Y(jié)構(gòu)圖、錯(cuò)誤率標(biāo)定數(shù)據(jù)；

輸出：層次樹HT.

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

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

③ whileHT.length>1 do

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

2項(xiàng)A和B；

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

B分別設(shè)置為New_Node的左右子樹；

⑥HT.append(New_Node)；

⑦HT.remove(A)；

⑧HT.remove(B)；

⑨ end while

⑩ returnHT.

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

f=Qmerged-Qorigin+ωEV,

(1)

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

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

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

2)量子位劃分和分配

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

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

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

輸出：量子位劃分partition.

① 將programs按CNOTdensity降序排序；

② forprograminprograms

③C←set()；

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

④ forlinHT.leaves

/*對(duì)于HT中的每個(gè)葉節(jié)點(diǎn)l*/

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

⑥C.add(candidate)；

⑦ end for

⑧ ifC為空

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

⑩ end if

他節(jié)點(diǎn)的路徑

3.3 權(quán)重參數(shù)選擇

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 啟發(fā)式搜索空間設(shè)計(jì)

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

Fig.10 Critical gates圖10 關(guān)鍵門

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

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

Fig.11 SWAPs associated with critical gates圖11 與關(guān)鍵門操作相關(guān)的SWAP操作

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

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

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

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

(2)

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

score(SWAP)=H(SWAP)+

(3)

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

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

輸入：量子芯片拓?fù)浣Y(jié)構(gòu)G、量子程序programs、初始映射mapping；

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

① 為每個(gè)程序生成一個(gè)DAG；

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

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

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

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

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

⑦ else

⑧ for eachF

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

⑩ end for

SWAP操作到候選SWAP集合；

score(SWAP)最小的SWAP；

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

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

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

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

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

(4)

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

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

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

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

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

② 初始化cur_job_set為僅包含J中第1項(xiàng)任務(wù)的列表；

③idx←1；

④ whileidx

cur_job_set.length

⑤cur_job_set.append(J[idx]);

⑥ forjobincur_job_set

⑦ 計(jì)算job的Sep_EPST，Co_EPST;

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

⑨ ifEPST_violation>ε

⑩cur_job_set.remove(J[idx]);

6 實(shí)驗(yàn)評(píng)測

6.1 評(píng)測方法

1)評(píng)測指標(biāo)

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

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

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

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

2)量子芯片

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

Fig.13 Qubit topology of IBM-Q50圖13 IBM-Q50的量子位拓?fù)浣Y(jié)構(gòu)

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

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

Table 3 Benchmarks Used in the Evaluation表3 實(shí)驗(yàn)評(píng)測中所用的工作集

4)對(duì)比實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

6.3 映射成本評(píng)測

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

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

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

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

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

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

6.4 任務(wù)調(diào)度器評(píng)測

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

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

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

7 總 結(jié)

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