首頁 > AI資訊 > 最新資訊 > 少量樣本即可運行，中國科大團隊提出經(jīng)典量子混合算法QDMD，加速高維時間序列分析

少量樣本即可運行，中國科大團隊提出經(jīng)典量子混合算法QDMD，加速高維時間序列分析

新火種    2023-11-20
圖片

編輯 | 紫羅

時間序列廣泛應用于數(shù)理統(tǒng)計、數(shù)學金融、醫(yī)學醫(yī)療、天氣預報、語音識別和生物等領域。

時間序列是作為一系列時間上均勻分布的樣本收集的一組數(shù)據(jù)，例如一個月每個市場日結束時股票指數(shù)的價值，或者一個城市一年中每天的平均溫度。

高維時間序列在每個采樣時刻由多條信息組成，而不是只有一條信息，因此高維時間序列的處理和分析計算量更大。

動態(tài)模式分解（DMD）算法是時間序列分析中廣泛使用的因式分解和降維技術。在分析高維時間序列時，DMD 算法需要極大的計算能力。

為了加速 DMD 算法，來自中國科學技術大學和合肥綜合性國家科學中心人工智能研究院的研究團隊，提出了一種量子經(jīng)典混合算法，稱為量子動態(tài)模態(tài)分解（QDMD）算法。

研究人員在三個應用場景中測試了他們的算法：數(shù)據(jù)去噪、場景背景提取和流體動力學分析。研究確定 QDMD 只需少量樣本即可運行，并且在高維時間序列分析中具有量子優(yōu)勢。

該研究以「Quantum Dynamic Mode Decomposition Algorithm for High-Dimensional Time Series Analysis」 為題，于 2023 年 7 月 28 日發(fā)表在《Intelligent Computing》雜志上。

圖片

為了加速高維時間序列分析，研究人員開發(fā)并測試了 QDMD 算法。它通過降低對時間序列數(shù)據(jù)執(zhí)行的操作的復雜性來實現(xiàn)指數(shù)加速。

QDMD 算法的框架如下圖所示。輸入是時間序列 oracle圖片。首先在初始狀態(tài)準備步驟中準備由 X0的主奇異向量組成的初始狀態(tài)，然后對 X0生成的矩陣進行量子奇異值分解，得到包含分解矩陣的主奇異值和奇異向量的輸出狀態(tài)。然后對獲得的輸出狀態(tài)進行低采樣頻率處理，并使用采樣結果計算投影 DMD 算子 A。最后，使用一元線性組合 (LCU) 技術計算 DMD 特征值并準備 DMD 模態(tài)的幅度編碼狀態(tài)。

在目前的形式下，它也可以用來加速對某些其他類型數(shù)據(jù)集的分析。此外，研究人員計劃創(chuàng)建其算法的新變體，專門用于其他動態(tài)模態(tài)分解應用，如庫普曼分析。

量子算法的主要限制是樣本數(shù)量必須保持小，否則不會降低算法的復雜度，失去量子優(yōu)勢。研究人員在設計算法時充分意識到這一點，因此對樣本數(shù)量設定了上限，以確保強大的性能。

圖片

圖 1：QDMD 算法框架。（來源：論文）

不過，合肥綜合性國家科學中心人工智能研究院研究員Cheng Xue解釋道：「通過數(shù)值測試，我們發(fā)現(xiàn)分析特定時間序列所需的樣本數(shù)量低于我們推導的界限，這進一步說明了我們算法的加速性能?！?/p>三個應用場景中測試

為了測試改變樣本數(shù)量的效果，研究人員探索了他們的量子算法在不同領域的應用。第一個是數(shù)據(jù)去噪，是類似于從圖像中去除噪聲的過程。第二，場景背景提取，是計算機視覺中的常見任務。它是一種通過比較同一場景的一系列圖像來去除前景項目的圖像處理方法。第三種是流體動力學分析，用于預測氣體或液體的運動。該算法成功地執(zhí)行了這些任務。

第一個應用是數(shù)據(jù)去噪，這是去除噪聲并重建原始數(shù)據(jù)的過程。研究人員使用 QDMD 算法解決特定的時間序列去噪問題。

圖片

圖 2：n0 = 1, 000 時通過 QDMD 算法重建的去噪時間序列。（來源：論文）

圖 2 為 k = 0，4，8，12 時的 4 個快照（snapshot）。圖 2A ~ C 分別為噪聲快照、重構快照和原始快照。重構后的圖像更接近原始圖像，表明去噪成功。

QDMD 算法的第二個應用是場景背景提取，其中從背景被多個前景對象遮擋的圖像序列中獲得背景模型。場景背景提取具有廣泛的應用，從視頻監(jiān)控到計算攝影。

圖片

圖 3：使用 QDMD 算法提取的背景，樣本數(shù)量 M = 10, 000。（來源：論文）

隨著樣本數(shù)量的增加，QDMD 算法變得更加穩(wěn)定。當樣本數(shù)達到 10, 000 個時，QDMD 算法的性能相對較好。使用 QDMD 算法提取的背景。3 個數(shù)據(jù)集的空間維度分別為 230,400、921,600 和 1,440,000，均顯著大于10,000。此外，樣本數(shù) M 對 MSSSIM 的影響與 n 無關；因此，隨著 n 的增加，QDMD 算法提供了更大的量子優(yōu)勢。

在許多可能的應用中，流體動力學尤其重要?！竸討B(tài)模態(tài)分解最初用于流場數(shù)據(jù)分析，」 Cheng Xue解釋道。「流體動力學的研究往往會產(chǎn)生高維流場數(shù)據(jù)，數(shù)據(jù)維度達到數(shù)十億級。從這些數(shù)據(jù)中提取有意義的流場特征是一個具有挑戰(zhàn)性的問題?！?/p>

接下來，利用 QDMD 算法加速流場數(shù)據(jù)分析是 QDMD 一個有前景的應用場景。研究人員應用 QDMD 算法，測試樣本數(shù) M 對獲得的 DMD 特征值和 DMD 模態(tài)的影響；結果如下圖所示，當樣本數(shù)量相對較少時，QDMD 算法的保真度接近 1。因此，QDMD 算法對于流體動力學分析也很有效。

圖片

圖 4：QDMD算法求解流體動力學分析問題時的數(shù)值結果。（來源：論文）

由于量子計算機仍處于開發(fā)階段且相對難以獲得，該研究在量子算法方面的工作由「理論推導加數(shù)值模擬」 組成，但她表示，量子芯片技術正在與量子算法的「協(xié)同」 關系中快速發(fā)展，在不遠的將來，這有望帶來「革命性的突破」。

量子計算機的力量來自兩個不直觀的特性：疊加和糾纏，這使得它們能夠并行執(zhí)行許多計算。然而，量子計算「只能加速特定問題的速度，并不能取代經(jīng)典計算機」 。

未來，研究人員將利用 QDMD 算法加速庫普曼（Koopman）分析，并開發(fā)量子庫普曼分析算法來提取時間序列的非線性特征。

相關推薦
免責聲明
本文所包含的觀點僅代表作者個人看法，不代表新火種的觀點。在新火種上獲取的所有信息均不應被視為投資建議。新火種對本文可能提及或鏈接的任何項目不表示認可。 交易和投資涉及高風險，讀者在采取與本文內(nèi)容相關的任何行動之前，請務必進行充分的盡職調查。最終的決策應該基于您自己的獨立判斷。新火種不對因依賴本文觀點而產(chǎn)生的任何金錢損失負任何責任。

熱門文章