量子回歸算法綜述?

高 飛 潘世杰 劉海玲 秦素娟 溫巧燕

北京郵電大學(xué)，北京市 100876

引言

隨著信息技術(shù)的高速發(fā)展，全球數(shù)據(jù)總量每年指數(shù)增長，這使得經(jīng)典機(jī)器學(xué)習(xí)算法在處理大數(shù)據(jù)時(shí)將面臨計(jì)算性能的巨大挑戰(zhàn)。 量子力學(xué)獨(dú)特的性質(zhì)使得量子計(jì)算在處理某些特定問題上相比于經(jīng)典計(jì)算具有顯著的速度優(yōu)勢。 近年來各研究機(jī)構(gòu)和IT 公司聚焦于研究用量子算法解決經(jīng)典機(jī)器學(xué)習(xí)問題，進(jìn)而出現(xiàn)了一個(gè)新型交叉領(lǐng)域—量子機(jī)器學(xué)習(xí)[1]。 該領(lǐng)域的一些成功實(shí)例包括量子主成分分析[2]，量子分類算法[3，4]，量子數(shù)據(jù)聚類[5，6]，量子神經(jīng)網(wǎng)絡(luò)等[7]。

2012 年，Wiebe 等首次提出一個(gè)基于HHL算法[8]的量子線性回歸算法[9]。 當(dāng)數(shù)據(jù)矩陣是稀疏矩陣且具有很低的條件數(shù)時(shí)，該算法相對經(jīng)典算法具有指數(shù)加速效果。 后來，Liu 和Zhang對該算法進(jìn)行了簡化，提出復(fù)雜度更低的量子線性回歸算法[10]。 2016 年，Schuld 設(shè)計(jì)了用線性回歸預(yù)測新數(shù)據(jù)的量子算法[11]。 當(dāng)數(shù)據(jù)矩陣低秩時(shí)，該算法相對經(jīng)典算法具有指數(shù)加速效果。2017 年，Wang 提出一個(gè)輸出經(jīng)典形式擬合參數(shù)的量子線性回歸算法[12]，相比經(jīng)典算法，該算法的復(fù)雜度在樣本數(shù)目因子上具有指數(shù)加速效果。同年，Yu 等提出一個(gè)量子嶺回歸算法[13]，該算法在數(shù)據(jù)矩陣為低秩時(shí)具有指數(shù)加速效果。 此外，他們也提出一個(gè)評(píng)估嶺回歸預(yù)測性能的量子交叉驗(yàn)證算法。 2019 年，Li 等基于稠密矩陣線性系統(tǒng)求解算法[14]提出非稀疏矩陣的量子嶺回歸算法[15]，該算法相對經(jīng)典算法在數(shù)據(jù)矩陣的維度上有多項(xiàng)式加速效果。

本文將綜述量子回歸算法近年來的重要進(jìn)展，并借鑒文獻(xiàn)[16]的思想給出一個(gè)基于梯度下降法的量子邏輯回歸算法。 文章安排如下:第一節(jié)介紹一些基礎(chǔ)量子算法，它們已被廣泛應(yīng)用于量子機(jī)器學(xué)習(xí)；第二節(jié)對經(jīng)典回歸算法進(jìn)行簡單的回顧；第三節(jié)介紹典型的量子回歸算法；第四節(jié)對文章做了總結(jié)。

1 量子基礎(chǔ)算法

1.1 哈密頓量模擬

1982 年Feynman 指出用經(jīng)典計(jì)算機(jī)模擬量子系統(tǒng)的復(fù)雜度會(huì)隨著qubits 數(shù)目呈指數(shù)級(jí)增長，并提出量子計(jì)算機(jī)模擬量子系統(tǒng)的構(gòu)想[17]。封閉量子系統(tǒng)的演化遵循薛定諤方程:

其中?被稱為普朗克常數(shù)，H為系統(tǒng)的哈密頓量。 當(dāng)H與時(shí)間無關(guān)時(shí)，有｜ψ (t)〉＝e-iHt ｜ψ(0)〉。 即給定初態(tài)｜ ψ(0)〉， 在一個(gè)不隨時(shí)間變化的量子系統(tǒng)中演化t時(shí)間，那最終會(huì)得到量子態(tài)｜ψ(t)〉。 哈密頓量模擬是指給定訪問Hermitian 矩陣H的量子黑盒(quantum oracle)、任意時(shí)間t以及誤差∈， 設(shè)計(jì)一個(gè)量子電路U使其以精度∈近似酉操作e-iHt，即

針對不同的矩陣輸入模型，有不同的哈密頓量模擬的方式，復(fù)雜度也各不相同。

表1 典型哈密頓模擬方法

1.2 量子相位估計(jì)

相位估計(jì)算法[14，21]是一個(gè)重要的量子算法，已經(jīng)作為子算法被成功嵌入到多個(gè)量子算法中[8，9，22]。 它的目標(biāo)是把酉算子的相位信息(或量子模擬中哈密頓量的特征值信息)存儲(chǔ)到計(jì)數(shù)量子寄存器中。

量子相位估計(jì)[14]:令酉算子U:U ｜ vj〉＝exp(iθj)｜vj〉，其中θj∈[-π，π]，j∈[n]。 那么存在一個(gè)量子算法可將量子態(tài)∑j∈[n]αj ｜vj〉變換為∑j∈[n]αj ｜vj〉｜〉，使得對所有的j∈[n]，滿足算法的成功概率為1-1/poly(n) ，復(fù)雜度為O(TUlog(n)/δ) ，其中TU為實(shí)現(xiàn)U的復(fù)雜度。

1.3 Grover 搜索

在經(jīng)典搜索算法的搜索過程中，需要一個(gè)可以判斷隨機(jī)采樣的第x個(gè)元素是否為目標(biāo)元素的函數(shù)f(x)，不失一般性，假設(shè)

在量子情形下，類似于經(jīng)典算法，需要利用f(x)來構(gòu)造一個(gè)量子黑盒O來“判斷” 第x個(gè)元素是否為目標(biāo)元素:O ｜ x〉｜ q〉＝｜ x〉｜ q⊕f(x)〉。 利用黑盒O來構(gòu)造G算子:

在該算法中，｜ψ〉 為n個(gè)量子比特的均勻疊加態(tài)，即

1.4 幅度估計(jì)

1.5 受控旋轉(zhuǎn)

受控旋轉(zhuǎn)解決的問題是如何有效地把信息從計(jì)數(shù)量子寄存器中提取到量子態(tài)的振幅上。

受控旋轉(zhuǎn)[25]:令θ∈R，θ?是θ的d比特有限精度表示，則存在酉矩陣Uθ，滿足:

1.6 量子交換測試(Swap Test)

圖1 交換測試的量子線路。 測量頂部的輔助量子比特獲得測量結(jié)果為0 的概率為 ＝ +Tr ( ρ1ρ2) 。 重復(fù)運(yùn)行該電路足夠多次可得到Tr ( ρ1ρ2) 的估計(jì)值。

2 經(jīng)典回歸算法

2.1 一般線性回歸

2.2 嶺回歸

當(dāng)數(shù)據(jù)點(diǎn)自變量存在多重共線性使得XTX不可逆或者遭遇過擬合時(shí)，一般線性回歸的擬合效果往往不能令人滿意[27，28，29]。 為了克服這兩個(gè)問題，Hoerl 等提出嶺回歸模型[28]。 嶺回歸是一般線性回歸的擴(kuò)展，和一般線性回歸不同的是，嶺回歸是在一般線性回歸引入w的正則化項(xiàng)，使其最終的最優(yōu)擬合參數(shù)為

其中α記為嶺回歸參數(shù)，I為單位矩陣，且‖w‖為任意向量w的2-范數(shù)。 很顯然，一般線性回歸是嶺回歸在α＝0 下的特例。

找出一個(gè)好的正則化參數(shù)α 使得嶺回歸在該參數(shù)下具有較好的預(yù)測性能，并算出相應(yīng)的最優(yōu)擬合參數(shù)w在實(shí)際應(yīng)用中具有重要意義。

2.3 邏輯回歸

邏輯回歸是機(jī)器學(xué)習(xí)與模式識(shí)別中最重要的分類算法之一，被廣泛應(yīng)用于醫(yī)療、人臉識(shí)別、金融等領(lǐng)域[30]。 二元邏輯回歸是最簡單的邏輯回歸模型，其回歸函數(shù)為非線性函數(shù)

其中xi和yi分別是第i個(gè)訓(xùn)練樣本以及其對應(yīng)的類別。

因?yàn)樯鲜街泻瘮?shù)的最小值沒有閉式解，所以需要結(jié)合一些優(yōu)化手段(如梯度下降、牛頓法等)以迭代方式進(jìn)行求解。 一般采用梯度下降法來求解參數(shù)w， 該優(yōu)化算法的核心任務(wù)是計(jì)算出每次迭代中的梯度:

3 量子回歸算法

本節(jié)將介紹具有代表性的量子回歸算法。具體來說， 3.1 節(jié)分別介紹了模型參數(shù)w的輸出為量子態(tài)以及輸出為經(jīng)典形式的量子線性回歸算法，3.2 節(jié)介紹量子嶺回歸算法，3.3 節(jié)借鑒文獻(xiàn)[16]的思想給出一個(gè)基于梯度下降法的量子邏輯回歸算法。

3.1 量子線性回歸算法

3.1.1 輸出量子態(tài)｜w〉 的量子線性回歸算法

圖2 Liu 等的一般線性回歸的量子算法

圖3 Schuld 等算法的大致流程

3.1.2 獲得參數(shù)w經(jīng)典信息的量子線性回歸算法

另外，Wang還設(shè)計(jì)了一個(gè)量子算法來估計(jì)擬合的質(zhì)量，可用于提前檢查給定的數(shù)據(jù)集是否符合線性回歸模型。 擬合質(zhì)量的定義與WBL[9]方法相同，但該算法采用相位估計(jì)算法的一個(gè)變體[35]來標(biāo)記想要的特征相位，接著運(yùn)用類似HHL算法的方法得到擬合質(zhì)量。 這里不做詳細(xì)介紹，具體內(nèi)容見文獻(xiàn)[12]的定理3。

圖4 獲得最優(yōu)參數(shù)w 的經(jīng)典信息的量子算法

3.2 量子嶺回歸算法

2017 年，Yu等提出一個(gè)數(shù)據(jù)矩陣為低秩矩陣的量子嶺回歸算法[13]。 另外，為了高效評(píng)估嶺回歸預(yù)測能力，他們還設(shè)計(jì)了量子K重交叉驗(yàn)證算法來選取一個(gè)好的正則化參數(shù)α。

首先介紹量子嶺回歸算法(子算法1)，該算法輸出為一個(gè)量子態(tài)，其幅度以誤差∈近似w的歸一化形式。 該算法類似于量子線性回歸算法，需將X擴(kuò)展到一個(gè)厄米矩陣

另外，Yu等把上述量子嶺回歸算法作為子算法，設(shè)計(jì)了量子算法做嶺回歸的K重交叉驗(yàn)證，以便選取一個(gè)好的嶺回歸參數(shù)α使得量子嶺回歸具有很好的預(yù)測性能。

經(jīng)典情形下，可采用下面的K重交叉驗(yàn)證法來確定一個(gè)好的α:

(1)將N個(gè)初始數(shù)據(jù)點(diǎn)的集合分為K(2 ≤K≤N)個(gè)子集，且第l(l＝1，…，K)個(gè)子集包含數(shù)據(jù)點(diǎn){(xj，yj)｜ j∈Sl}， 其中Sl:＝{(l-1)N/K+ 1，…，lN/K} 用于標(biāo)記分配到第l子集中數(shù)據(jù)點(diǎn)的編號(hào)；

(2)執(zhí)行K輪訓(xùn)練-測試過程。 對于第l輪，第l子集被選為測試集合，而其他子集作為訓(xùn)練集；

(3)計(jì)算所有數(shù)據(jù)的殘差平方和E(α) 作為評(píng)估具有該特定候選α參數(shù)下嶺回歸的預(yù)測，性能的指標(biāo)；

(4)最后，選擇一個(gè)具有最佳預(yù)測性能的候選α 作為最終的嶺回歸參數(shù)α。

計(jì)算E(α) 的量子算法過程簡述如下:令Xl∈R N/K×M為X中包含Sl指定的行，即對應(yīng)了第l個(gè)子集，X-l∈R N×M為X但Sl所指定的行的元素均用0 代替。 在初態(tài)上引入一個(gè)附加寄存器存儲(chǔ)Sl的信息，作為控制位控制做量子模擬的時(shí)候選取的矩陣X-l。 用類似于子算法1 的過程制備量子態(tài)

圖5 量子K 重交叉驗(yàn)證算法

3.3 量子邏輯回歸算法

圖6 獲得梯度?wj 的量子算法

4 結(jié)論和展望

量子計(jì)算在解決某些機(jī)器學(xué)習(xí)問題時(shí)展現(xiàn)出強(qiáng)大的計(jì)算能力。 本文綜述了量子回歸算法近年來的重要進(jìn)展，包括量子線性回歸、量子嶺回歸算法，并提出一個(gè)基于梯度下降法的量子邏輯回歸算法。 這些量子算法在合理的假設(shè)條件下相比經(jīng)典算法有指數(shù)加速效果，展現(xiàn)出了量子計(jì)算的獨(dú)特優(yōu)勢。 目前，針對Lasso 回歸、Elastic Net 回歸等問題還沒有相關(guān)的量子快速算法，它們可能是未來的研究方向。 此外，如何在量子回歸算法中增加隱私保護(hù)的功能，也有待解決。 隨著大數(shù)據(jù)和量子計(jì)算的快速發(fā)展，我們期待在未來量子計(jì)算能解決更多的經(jīng)典機(jī)器學(xué)習(xí)問題。