中科大潘建偉團隊在光量子處理器上成功實現拓撲數據分析

自arXiv，作者：黃合良等，機器之心編譯，參與：劉曉坤。

論文：Demonstration of Topological Data Analysis on a Quantum Processor

論文鏈接：https://arxiv.org/abs/1801.06316

通過識別帶雜訊、非結構化數據的底層結構，拓撲數據分析（TDA）可以魯棒地從數據中提取有用信息。最近，人們提出了一種有效的量子演算法 [Lloyd, Garnerone, Zanardi, Nat. Commun. 7, 10138 (2016)]，用於計算數據點的貝蒂數（一種拓撲特徵，描述散點圖中各個維度的拓撲洞的總數）。我們利用一個六光子量子處理器實現了這個量子演算法的原理性實驗演示驗證，成功地分析了一個包含三個數據點的網路的貝蒂數拓撲特徵，為量子計算領域的數據分析提供了新的探索思路和研究方法。

在探索性數據分析和數據挖掘中，我們的收集到的大數據通常編碼了非常有價值的信息，然而，這些數據往往規模很大，並且是非結構化的、帶雜訊的、不完整的，從而使得從數據中提取有用信息變得很有挑戰性。TDA[1] 將拓撲學與數據分析進行結合，可以從無結構的數據中分析數據隱含的拓撲特徵，對雜訊具有較強的魯棒性，提供了研究此類數據的一種分析方法。特別地，持續同調（persistent homology）[2][3] 通過計算和分析數據的貝蒂數，用於提取數據的有用信息。其中，貝蒂數是一種拓撲特徵，第 k 個貝蒂數β_k 表示為數據集中的 k 維洞的數量。例如，β_0、β_1、β_2 分別代表了連通分支、一維洞和二維洞的數量。通過貝蒂數可以對數據進行了抽象化表示，將其轉化為拓撲性的描述，這對於理解數據集的底層結構很有價值。使用 TDA 分析數據的貝蒂數這一分析方法近年來得到了快速發展，有望應用於圖像識別 [4]、信號處理 [5]、網路科學 [6,7]、感測器分析 [8-11]、大腦連接 [12,13] 和 fMRI 數據分析 [14,15] 等。

然而實際上，當處理複雜數據的時候，經典的拓撲數據分析方法將面臨計算量巨大的問題：n 個數據點的數據集擁有 2^n 個潛在拓撲結構，即使使用最強大的經典計算機也難以求解規模不太大的數據集。目前，估計數據集合所有階貝蒂數的最優經典演算法需要的時間複雜度為 O(2^nlog(1/δ)) [16–21]，其中δ為精度。此外，對某些類型的拓撲結構 [22]，計算所有階貝蒂數是 PSPACE-hard 的。

最近，Lloyd 等人 [23,24] 將量子機器學習方法擴展到 TDA 中，以高效地計算所有階的貝蒂數。如果從一個數據集中生成的 k-單純形的比例足夠大，則以精度δ計算所有階貝蒂數的量子演算法耗費的時間複雜度為 O(n^5/δ)，相比已知最好的經典演算法，具有指數加速。此外，該演算法不需要大規模的量子隨機存取存儲器（qRAM）[25]，只需要 O(n^2 ) 的比特數即可——用於存儲 n 個數據點之間所有兩兩間距的信息。該演算法的潛在計算加速能力和可行性有望令量子 TDA 作為未來量子計算機的新演算法（量子演算法包括 Shor 演算法、[26,29]、量子模擬 [30-33]、求解線性系統 [34,35] 和線性向量的分類 [36-38] 等）。

我們首次利用一個小規模的光子量子處理器，進行了量子 TDA 演算法的原理性演示驗證。在實驗中，我們在兩種不同的距離參數下，監控和識別三個數據點的貝蒂數的拓撲特徵，成功地展示了量子 TDA 演算法的可行性，表明數據分析可能是未來量子計算的重要應用。

為了計算貝蒂數，我們首先以數據點之間的關係拓撲地表徵數據。我們使用截斷距離將數據點分類為單純形（參見圖 1（a）），即數據點的全連接子集。單純形的集合構成一個單純復形，然後可以從該拓撲結構中提取貝蒂數等特徵。這些拓撲結構如圖 1（b-d）所示。

通過確定?所有範圍的貝蒂數的完整集合，我們可以構建條形碼（參見圖 1（e））[39]，即貝蒂數的距離依賴形式的參數化版本。H_k 區域內的每個條形代表一個 k 維洞，條形的長度表示其在參數中的存在持續性。利用條形碼，我們可以定量地將短條形當做拓撲雜訊過濾掉，並將長條形作為重要的特徵（條形的長度表示其對抗間距變化的存在持續性）。在圖 1（e）中，在 H_1 區域有一個條形延展了很長的範圍，從而我們確定該非結構化數據（圖 1（b））的底層拓撲特徵是一個圓。

圖 1：（a）k-單純形（圖中展示了 k=0、1、2、3 的例子）是 k+1 個數據點的全連接集合。（b）數據點的散點圖。（c）使用某些任意的指標以量化數據點之間的距離，（以數據點為，圓心直徑為?）圓彼此接觸的數據點之間以邊連接。（d）單純復形是單純形的集合。著色區域表示復形中的不同單純形。（e）條形碼的結構。水平軸代表距離?。在 H_k 的任意區域中，條形和垂直線的交點數等於（距離?對應的）貝蒂數β_k。

一般地，量子 TDA 演算法有兩個主要步驟（參見圖 2（a））。首先訪問數據，構造的拓撲結構 k-單純形的均勻混態。該步驟的時間複雜度依賴於 k-單純形的比例，在最差的情況下是指數量級的。但是在實際應用中，複雜拓撲結構中 k-單純形的比例一般不會太小。所以，在實際應用中，無論用經典演算法還是 Grover 演算法（進一步的二次型演算法加速）都可以高效地實現這個步驟。在量子演算法中，這個步驟可以分成兩小步：（1a）單純復形量子態的製備；（1b）均勻混態的構造。（2）揭示結構中的拓撲不變數，這個步驟使用相位估計演算法 [40] 實現，在量子計算機上，該演算法相對經典演算法能實現指數級加速，實際證明 [23,24] 它的時間複雜度為 O（n^5/δ），其中δ為計算精度。

圖 2：量子 TDA 的量子線路。（a）原始量子演算法線路的簡單示意圖。（b）包含三個數據點的散點圖。

（c）1-單純形量子態（3<?_1<4）

的圖表徵。第一個和第二個數據點由一條邊連接。

（d）1-單純形量子態（4<?_2<5）

第一個數據點分別和第二個和第三個數據點連接。（e）5 量子比特的優化量子線路。不同顏色的模塊代表 4 個基本階段（單純復形製備、構造混態、相位估計、測量）。

圖 3：實驗裝置。中心波長為 394nm 的紫外激光脈衝（脈衝持續時間為 150 飛秒，脈衝重複頻率為 80MHz）通過三個偏硼酸鋇（BBO）晶體 [42] 以生成三對糾纏光子對 (|H>|V>+|V>|H>)/√2（空間模式分別為 1-2、3-4、5-6，細節參見附錄 1）。光子 2（3）和 4（5）在 PBS 上進行干涉。所有的光子使用 3-nm 帶寬的過濾器進行光譜過濾。C-BBO：三明治形態的 BBO+HWP+BBO 組合；QWP：四分之一玻片；POL：起偏器；SC-YVO4：用於空間補償的 YVO4 晶體；TC-YVO4：用於時間補償的 YVO4 晶體。

圖 4：最終的實驗結果。最終的輸出通過在泡利-Z 基上測量本徵值寄存器確定。兩個不同 1-單純形的態輸入的測量期望值（藍色條形）和理論預測值（灰色條形）如（a）和（b）所示。誤差線表示 1 個標準偏差，它是根據原始數據，通過泊松分布推導得出的（c）0<?<5 的條形碼。由於不存在 k≥1 的 k 維洞，這裡只給出了第 0 個貝蒂數。當 0<?<3 時，所有點之間都沒有連接，因此第 0 個貝蒂數等於數據點個數，即 0<?<3 時有三個條形。當 3<?1<4 和 4<?2<5 時，第 0 個貝蒂數分別等於 2 和 1。

（a）的量子態：

（b）的量子態：

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！