量子譜回歸算法

潘世杰 高 飛 萬林春 秦素娟 溫巧燕

1(網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室(北京郵電大學(xué)) 北京 100876) 2(密碼科學(xué)技術(shù)國家重點實驗室 北京 100878)

量子計算展示了其相對經(jīng)典計算的強(qiáng)大優(yōu)勢[1-2].在處理特定的問題時，如大數(shù)質(zhì)因數(shù)分解[3]、無結(jié)構(gòu)數(shù)據(jù)搜索[4]、稀疏線性方程組求解[5]和低秩矩陣主成分分析[6]，采用量子計算的方式具有比經(jīng)典計算方式低得多的復(fù)雜度.近年來，一些研究人員將量子強(qiáng)大的計算能力用在處理經(jīng)典計算機(jī)上具有較高復(fù)雜度的機(jī)器學(xué)習(xí)問題，取得了一系列成果，包括量子回歸算法[7]、量子支持向量機(jī)[8]、量子生成對抗網(wǎng)絡(luò)[9-10]、量子神經(jīng)網(wǎng)絡(luò)和量子數(shù)據(jù)挖掘[11]等.

子空間學(xué)習(xí)是機(jī)器學(xué)習(xí)的重要部分.現(xiàn)實世界的數(shù)據(jù)大多數(shù)是以高維的形式出現(xiàn)，而決定計算任務(wù)——例如分類和回歸——結(jié)果的有效維度往往很低.由于直接處理高維數(shù)據(jù)不僅需要消耗大量計算資源，還會導(dǎo)致維數(shù)災(zāi)難(the curse of dimensionality)問題，因此子空間學(xué)習(xí)被提出，用來把數(shù)據(jù)集從高維降到低維，同時保持?jǐn)?shù)據(jù)潛在的結(jié)構(gòu).人臉識別的結(jié)果表明，通過子空間學(xué)習(xí)進(jìn)行降維，可以顯著地提高算法的性能[12].盡管子空間學(xué)習(xí)可以部分解決高維數(shù)據(jù)的學(xué)習(xí)問題，但子空間學(xué)習(xí)本身通常也需要很高的復(fù)雜度，因此如何降低子空間學(xué)習(xí)的復(fù)雜度是一個很有實際意義的問題.一個自然而然的想法是將量子計算應(yīng)用于子空間學(xué)習(xí)，以達(dá)到更低的算法復(fù)雜度.

常用的子空間學(xué)習(xí)算法包括主成分分析(principal components analysis,PCA)[13]、線性判別分析(linear discriminant analysis,LDA)[14]、局部保持投影(locality preserving projections,LPP)[12]和鄰域保持嵌入(neighborhood preserving embedding,NPE)[15]等.子空間學(xué)習(xí)算法如LDA,LPP和NPE，通常需要進(jìn)行稠密矩陣的特征分解，這往往需要消耗較高的計算資源.為了降低計算資源，2007年Cai等人[16]提出了譜回歸降維框架，該框架包含了很多現(xiàn)有的子空間學(xué)習(xí)算法，如LDA，LPP和NPE.在同一篇文章中，針對結(jié)合標(biāo)簽信息來構(gòu)造對應(yīng)圖的子空間學(xué)習(xí)，Cai等人提出了高效譜回歸.Cai等人提出可利用權(quán)重矩陣的特殊結(jié)構(gòu)，結(jié)合格拉姆-施密特正交化來得到稠密矩陣的特征向量，而不需要對稠密矩陣進(jìn)行特征分解，從而把復(fù)雜度從維數(shù)的立方降低為維數(shù)的一次方.另外，因為引入了線性回歸，所以譜回歸中也可以很自然地加入正則化參數(shù)，使得算法可用于數(shù)據(jù)矩陣是病態(tài)矩陣的情況.

在量子領(lǐng)域，Lloyd等人[6]率先提出了量子主成分分析算法(quantum principal component analysis algorithm,QPCA)，算法相對經(jīng)典算法具有指數(shù)加速效果.需要指出的是，盡管該算法被稱為QPCA算法，但實際上如果要維持量子算法的加速效果，該算法只能用來得到低秩(或者近似低秩)矩陣的較大的特征值，以及以量子態(tài)形式得到對應(yīng)的特征向量；另外，如果矩陣有重特征值，那么我們無法通過量子主成分分析得到重特征值對應(yīng)的一組特征向量，而只能得到特征向量的疊加態(tài).隨后，Yu等人基于量子PCA算法，提出了量子PCA降維算法，當(dāng)降維后數(shù)據(jù)的維數(shù)為訓(xùn)練數(shù)據(jù)維數(shù)的對數(shù)時，他們的量子算法相對經(jīng)典算法實現(xiàn)了指數(shù)級的加速[17].Cong等人實現(xiàn)了量子LDA算法，與經(jīng)典算法相比有指數(shù)級的加速效果[18].Meng等人基于譜回歸降維框架[16]，首次提出了正則化子空間學(xué)習(xí)的量子譜回歸算法(MYXZ算法，以作者姓名首字母命名)，并在降維數(shù)據(jù)的項數(shù)m和數(shù)據(jù)的特征數(shù)n滿足m=O(lbn)時，算法具有多項式加速效果[19].盡管如此，MYXZ算法仍然存在有待改進(jìn)的地方.首先，MYXZ算法在算法的第一步，即求一般特征值問題時用了稀疏哈密頓量模擬，當(dāng)處理的矩陣是稀疏矩陣時，算法具有良好的加速效果，但實際應(yīng)用中存在很多矩陣不稀疏的例子，例如LDA，此時用稀疏哈密頓量模擬沒有加速效果.其次，如果算法第一步的解中有相同的特征值，也會導(dǎo)致MYXZ算法無法得到相應(yīng)的特征向量(只能得到特征向量的疊加態(tài))而導(dǎo)致后續(xù)步驟出錯.最后，MYXZ算法的加速基于假設(shè)m=O(lbn)，其中m為數(shù)據(jù)的項數(shù)，n為數(shù)據(jù)的特征數(shù).因為譜回歸的原始文獻(xiàn)[16]的重點在于把算法復(fù)雜度中的因子m3降至m，而對于m=O(lbn)的情況，譜回歸本身只有很小的加速效果，因此我們認(rèn)為m=O(n)是更符合實際情況的假設(shè).

本文首先對MYXZ算法進(jìn)行了細(xì)致分析，并指出了算法的局限性.然后，我們提出了一個改進(jìn)算法，該算法采用了量子奇異值估計技術(shù)(quantum singular value estimation,QSVE)[20]，而不是稀疏量子主成分分析來求解一般特征值問題，在處理稠密矩陣特征值問題時，QSVE具有更低的復(fù)雜度.當(dāng)m=O(n)時，我們的改進(jìn)算法相對經(jīng)典算法有多項式加速效果；當(dāng)算法的第1步涉及的矩陣是稠密矩陣時，我們的改進(jìn)算法相對MYXZ算法有多項式加速效果.其次，針對結(jié)合標(biāo)簽信息來構(gòu)造對應(yīng)圖的子空間學(xué)習(xí)算法，例如LDA和帶標(biāo)簽的LPP,NPE，我們提出了相應(yīng)的量子算法.我們把文獻(xiàn)[16]中提出的高效算法中復(fù)雜度較高的嶺回歸部分設(shè)計成量子算法，并行得到多個嶺回歸結(jié)果；而復(fù)雜度較低的部分(即格拉姆施密特正交化)仍然采用原算法實現(xiàn).這樣做的好處在于既規(guī)避了稠密矩陣特征分解的問題，也利用了量子的加速效果.另外，為了算法的完整性，我們給出了對新輸入數(shù)據(jù)進(jìn)行降維的實現(xiàn)方式.當(dāng)m=O(n)時，我們的算法相對經(jīng)典的高效譜回歸算法具有多項式加速效果.

1 正則化子空間學(xué)習(xí)的譜回歸

在本節(jié)中，我們將對正則化子空間學(xué)習(xí)的譜回歸進(jìn)行回顧，并介紹其復(fù)雜度.

1.1 譜回歸

令G表示由m個頂點構(gòu)成的圖，每個頂點對應(yīng)一張人臉圖像即xi，W為一個m×m的權(quán)重矩陣，其元素表示圖G中頂點i和頂點j之間的權(quán)重.譜回歸是一個降維算法的框架，通過W矩陣的不同選取方式，能得到不同的降維算法，如線性判別分析、局部保持投影和鄰域保持嵌入.譜回歸的提出是為了避免降維算法中復(fù)雜度較高的稠密矩陣特征分解.

譜回歸主要包含3個步驟：

1)求解最大特征向量問題

Wy=λDy，

(1)

2)求解c-1個最小二乘問題

(2)

3)對新數(shù)據(jù)x進(jìn)行降維，令A(yù)=(a1,a2,…,ac)，則降維后的坐標(biāo)為

yx=ATx.

當(dāng)樣本數(shù)m小于特征數(shù)n時，優(yōu)化問題(2)是病態(tài)的，一種常見的做法是采用嶺回歸的方式，引入正則化參數(shù)α，即求解優(yōu)化問題：

此時ai的解析解為

ai=(XXT+αI)-1Xy(i).

引入正則化參數(shù)的譜回歸被稱為正則化子空間學(xué)習(xí)的譜回歸.

在文獻(xiàn)[16]中，作者提出一種高效的譜回歸求解方法.對于結(jié)合標(biāo)簽信息來構(gòu)造對應(yīng)圖的降維算法，如LDA以及有監(jiān)督的LPP和NPE，其最大特征向量問題(即式(1))的求解是平凡的.不妨假設(shè)數(shù)據(jù)是按標(biāo)簽信息排列的，則

其中W(t)是mt×mt的矩陣，mt為第t個類別的樣本數(shù)，此時可以直接給出式(1)的最大特征值1對應(yīng)的c個特征向量，即

另外，顯然全1向量1=(1,1,…,1)T也是式(1)中最大特征值1對應(yīng)的特征向量.因為對所有的W，1都是式(1)中特征值1對應(yīng)的特征向量，因此1并不包含關(guān)于問題的任何信息.為了去除和1相關(guān)的冗余信息，文獻(xiàn)[16]中提出的方法是取1為第1個正交向量，其余c-1個特征向量由y(i)通過格拉姆-施密特正交化得到.最后去掉1，就得到了我們想要的c-1個相互正交的特征向量，也即式(1)的解.

1.2 譜回歸的復(fù)雜度

2 正則化子空間學(xué)習(xí)的量子譜回歸

本節(jié)將對正則化子空間學(xué)習(xí)的量子譜回歸進(jìn)行回顧，并對算法進(jìn)行分析，給出算法復(fù)雜度.

2.1 量子譜回歸

2019年，Meng等人提出了正則化子空間學(xué)習(xí)的量子譜回歸算法[19](MYXZ算法).該算法沒有利用文獻(xiàn)[16]中的核心思想，即對于結(jié)合標(biāo)簽信息來構(gòu)造對應(yīng)圖的降維算法，其最大特征向量問題的求解(式(1))是平凡的，而是直接用量子主成分分析[6]的方式來對矩陣進(jìn)行特征分解.

MYXZ算法主要包含2個步驟：

1)用稀疏矩陣量子主成分分析和量子矩陣向量乘法來求式(1)的解y(1),y(2),…,y(c-1).

2)用量子算法求

ai=(XXT+αI)-1Xy(i).

MYXZ算法假設(shè)矩陣X事先存儲在一個樹狀的QRAM中，基于量子稠密線性方程組求解技術(shù)[16]，設(shè)計出量子稠密矩陣嶺回歸技術(shù)，可直接用于求ai.

MYXZ算法沒有考慮算法的第3步，也即針對一個新輸入的數(shù)據(jù)x，輸出其降維后坐標(biāo)yx=Ax.

2.2 算法分析

本節(jié)將結(jié)合文獻(xiàn)[19]中的假設(shè)，對算法及其復(fù)雜度進(jìn)行分析.

3 改進(jìn)的量子譜回歸

在實際應(yīng)用中，往往樣本數(shù)量m和提取的特征個數(shù)n的規(guī)模是相差不大的，另外，在譜回歸的原始論文中[16]，譜回歸算法的優(yōu)勢在于降低了復(fù)雜度中參數(shù)m的次數(shù).如果m?n，譜回歸的加速效果并不明顯.因此在改進(jìn)的算法中，在其他參數(shù)假設(shè)不變的前提下，我們希望在m=O(n)時，量子算法相對經(jīng)典算法有顯著加速效果.

4 高效譜回歸的量子算法

在文獻(xiàn)[16]中，Cai等人針對結(jié)合標(biāo)簽信息來構(gòu)造對應(yīng)圖的降維算法，如有監(jiān)督的局部保持投影和鄰域保持嵌入，提出了一個高效的實現(xiàn)方式.對于這類降維算法，式(1)的最大特征值1是c重特征值，因而MYXZ算法無法進(jìn)行處理.我們提出了這類子空間學(xué)習(xí)問題的量子譜回歸算法.我們的算法中也用到了MYXZ中的部分過程.

4.1 算法過程

考慮到量子主成分分析的局限性，我們直接采用經(jīng)典的方式來求式(1)的解.我們的算法步驟為：

1)令第1個特征向量為全1向量(1,1,…,1)T，通過對

進(jìn)行格拉姆-施密特正交化，得到c-1正交的特征向量，作為式(1)的解，記為y(1),y(2),…,y(c-1).

2)把y(1),y(2),…,y(c-1)存儲到QRAM中，制備量子態(tài)

3)對第2量子寄存器，執(zhí)行稠密矩陣嶺回歸量子算法，得

4)針對新輸入的量子態(tài)|x〉，用量子低秩矩陣向量乘法，來求其降維后量子態(tài)|y〉.

我們算法的第4步即對新輸入的數(shù)據(jù)進(jìn)行降維，這正是子空間學(xué)習(xí)的目的.MYXZ算法沒有給出算法的降維過程，為了算法的完整性，我們將給出降維過程以及其復(fù)雜度分析.

4.2 算法分析

為了方便對4.1節(jié)所述的步驟4的分析，我們定義對數(shù)據(jù)的量子訪問[21]：

定義1[21].如果存在以下變換可以在復(fù)雜度T內(nèi)實現(xiàn)，那么稱我們可以通過量子訪問矩陣A∈n×m：

其中,i∈{1,2,…,n}，Ai表示矩陣A的第i列構(gòu)成的向量.

綜上，算法的總復(fù)雜度為

相關(guān)算法的復(fù)雜度對比和適用條件如表1所示.需要注意的是，我們沒有把降維過程(即4.1節(jié)中的算法步驟4)的復(fù)雜度列在表中，因此表中量子高效譜回歸的總復(fù)雜度比上面算出來的復(fù)雜度稍低，但并不影響對比結(jié)果.

Table 1 Comparison of Complexity and Applicable Conditions of Classical and Quantum Spectral Regression Algorithms表1 經(jīng)典和量子譜回歸算法的復(fù)雜度和適用條件對比

5 結(jié) 論