[發(fā)明專利]一種量子拉普拉斯特征映射方法

有效

• 申請?zhí)枺?/td>: 201710122846.6
• 申請日: 2017-03-03
• 公開（公告）號: CN106919797B
• 公開（公告）日: 2020-04-07
• 發(fā)明（設計）人: 李曉瑜;黃一鳴;雷航;鄭德生
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F17/10
• 分類號: G06F17/10
• 代理公司: 成都華風專利事務所(普通合伙) 51223
• 代理人: 徐豐

本發(fā)明公開了一種量子拉普拉斯特征映射方法，在現(xiàn)有的拉普拉斯特征映射算法之上，將拉普拉斯矩陣視為數(shù)據(jù)集的協(xié)方差矩陣，可以簡便地得到一個密度矩陣，同時將現(xiàn)有的特征向量問題進行相應的轉換，采用量子的方式進行計算。本發(fā)明提出了一種量子版本的拉普拉斯特征映射方法?QLE（Quantum Laplacian Eigenmaps），應用了共軛鏈以及矩陣運算以解決非線性的降維問題。比起經典的拉普拉斯特征映射需要的多項式時間，本發(fā)明可以提供指數(shù)級的加速。

技術領域

本發(fā)明涉及一種量子拉普拉斯特征映射方法。

背景技術

機器學習與數(shù)據(jù)分析在降維，預測和分類中扮演著越來越重要的角色。在許多例子中原有的數(shù)據(jù)在高維的特征空間，如一張有n平方像素的圖片(每個像素作為一個特征)。所以為了分析這些高維度的特征數(shù)據(jù)，我們需要將自然結構視為低維流形嵌入高維空間的數(shù)據(jù)降維。

為了將高維的數(shù)據(jù)降維，無論我們選擇哪種方式，我們都需要考慮所需要的時間。正如我們所知的，一個設計良好的量子算法可以極大的改善我們的經典算法。勞埃德等人提出量子版本的PCA，可以指數(shù)級的提高算法速度。cong等人泛化了HHL算法，使之可以應用于量子判別式分析。盡管如此，這里依舊沒有非線性的量子版本的降維方法。

發(fā)明內容

本發(fā)明的目的在于克服現(xiàn)有技術的不足，提供一種量子拉普拉斯特征映射方法，應用了共軛鏈以及矩陣運算，解決非線性的降維問題，指數(shù)級地加快原有的拉普拉斯特征算法。

本發(fā)明的目的是通過以下技術方案來實現(xiàn)的：一種量子拉普拉斯特征映射方法，包括以下步驟：

S1：利用數(shù)據(jù)的位置信息建立一個圖G，頂點V是數(shù)據(jù)，邊E是不同領域數(shù)據(jù)的相似性；為了使數(shù)據(jù)降維，需要最小化目標函數(shù)J(u)：

式中，y_i是數(shù)據(jù)點x_i的低維表現(xiàn)，w_ij對應x_i與x_j的權重，L代表圖G的拉普拉斯矩陣；

S2：將目標函數(shù)min(2Y^TLY)求解轉化為廣義特征值求解：

Lv＝λDv

式中，D是一個對角矩陣，D_ii＝∑_jW(i,j)，特征向量v的最小非零特征值構造出數(shù)據(jù)的低維表示Y，λ表示特征值；

S3：將拉普拉斯矩陣L視為數(shù)據(jù)集的協(xié)方差矩陣，得到一個密度矩陣，即L＝I·I^T；其中I是圖G＝(V,E)的關聯(lián)矩陣；所述的關聯(lián)矩陣I存儲每個節(jié)點及其連接邊之間的關系，如果一個有向邊j從點i出發(fā)，則I_ij＝1，如果在點i結束，則I_ij＝-1，否則I_ij＝0；

S4：將步驟S2中的廣義特征值求解轉換為：

D^-1I·I^Tv＝λv；

S5：將關聯(lián)矩陣I和對角矩陣D轉化為可以在量子隨機存儲器QRAM中輸入的形式，a_i為關聯(lián)矩陣I的列，d_i為對角矩陣D的列；

S6：訪問QRAM以得到關聯(lián)矩陣I和對角矩陣D的量子態(tài)：

O(|i＞|0＞|0＞)→|i＞|d_i＞||d_i|＞

O(|i＞|0＞|0＞)→|i＞|a_i＞||a_i|＞

S7：通過QRAM構造|ψ₁＞和|ψ₂＞的狀態(tài)：