量子典型相關分析算法

王慶樂, 薛雪, 李元誠?

(1 華北電力大學控制與計算機工程學院, 北京 102206;2 北京郵電大學網絡與交換技術國家重點實驗室, 北京 100876;3 中國科學技術大學量子信息重點實驗室, 安徽 合肥 230026)

0 引 言

量子計算在處理某些特定問題時有比經典計算更強的計算能力,如質因數分解[1]、非結構化數據搜索[2]和矩陣計算問題[3?5]。近年來,隨著量子計算機的發展,量子機器學習(QML)受到了廣泛關注。QML 研究的一個重要方向是設計量子算法來加速機器學習,包括數據分類[6,7]和線性回歸等[8?10]。

嚴格來說,大部分機器學習算法實際上也是統計分析算法,統計分析中的一種重要方法為典型相關分析。實際上,當需要分析和研究兩組變量之間的關系時,通常會用到典型相關分析。例如,為了研究財政政策實施以后對經濟發展的影響,需要考察有關財政政策的一系列指標(如財政支出總額、財政赤字、國債發行額、稅率等)與經濟發展的一系列指標(如國內生產總值、就業率等兩組變量)之間的相關程度。典型相關分析方法最初由Hotelling[11]在1936 年提出。2004 年,Hardoon 等[12]對該方法進行了綜述,并提出了其在學習方法上的應用。2005 年,Sun 等[13]提出把典型相關分析用于特征融合。近年來,典型相關分析研究不斷發展,其變體也相繼被提出,包括基于核理論的典型相關分析[14]、基于流形結構的典型相關分析[15]、基于監督學習的典型相關分析[16]、稀疏典型相關分析等[17,18]。當數據量很大時,典型相關分析算法運算速度很慢,耗時嚴重,因此其不適用于大數據時代。

本文利用量子計算的優勢降低典型相關分析算法的復雜度,并提出了量子典型相關分析算法。所提出量子算法在特定參數條件下,相對經典典型相關分析在維度上有指數加速效果。

1 典型相關分析

1.1 典型相關分析的提出

典型相關分析的目的是尋求兩組變量中每一組變量的線性組合,使得兩組變量的線性組合之間的相關性最大化。一般的相關性分析依賴于變量的坐標系,即使兩組多維變量之間本質上存在非常強的線性關系,坐標系選取不恰當也會導致線性關系不可見[12]。典型相關分析通過研究兩組綜合指標之間的關系來研究變量之間的線性關系,可用于挖掘一般相關性分析中的不可見關系。

具體地,考慮兩組多變量隨機向量:X= [x0,x1,··· ,xn?1]和Y= [y0,y1,··· ,ym?1],其中xi和yj均為l維向量。定義一個線性組合wx,使得矩陣X列向量之間的一個線性組合為zx=Xwx。同理,可定義zy=Ywy。

典型相關分析通過選擇合適的wx和wy,使投影后的向量具有最大的相關性,即最大化函數

1.2 典型相關分析的求解及其復雜度

記[x,y]的協方差矩陣為C(x,y),則

經典算法求解(4)式轉化為求一般特征值問題,計算復雜度為O(poly(nml)),其中n、m分別是隨機向量X、Y中的隨機變量個數,l是隨機變量xi和yj的維度。

2 量子典型相關分析

2.1 問題轉化

2.2 量子典型相關分析算法設計

量子算法的輸入是矩陣X= [x0,x1,··· ,xn?1]和Y= [y1,y2,··· ,ym]。簡單起見,令n=m。實際上,如果n>m,可令Y= [y1,y2,··· ,ym,y1,y2,··· ,yn?m]。由于要找的是一個向量之間的線性組合,因此對Y進行這樣的處理不會影響最終結果。

不妨假設向量xi和yj(i,j∈{0,1,··· ,n?1})均為歸一化向量,即

假設輸入存儲在一個經典的數據結構中,那么量子訪問數據結構可以高效創建矩陣X和Y的每一列對應的量子態

以及每一列的二范數組成的向量對應的量子態|?X〉和|?Y〉,創建這些量子態的復雜度均為O[polylog(mnl)]。

步驟2:對ρ 做主成分分析

根據定理1,可實現和ρ 相關的量子操作,根據量子主成分分析算法[19],可以在量子態ρ 上做相位估計。假設ρ 的特征分解為

那么,由文獻[20]可以得到

步驟3:計算

3 結 論

典型相關分析是一種在實際生活中有很多應用的重要相關分析算法。利用量子算法的并行運算特性,提出了一種量子典型相關分析。將經典問題轉化為求解一個矩陣的主成分問題以及矩陣的冪與向量相乘問題。在求矩陣的主成分問題中,結合量子主成分分析和量子判別分析中的子算法設計了所提出算法;在求矩陣的冪和向量相乘的問題中,應用HHL 算法的思想并結合矩陣求冪算法,得到了很好的加速效果。在特定參數條件下,所提出算法相比經典典型分析具有指數加速效果。