原標(biāo)題:學(xué)界|中科大潘建偉團(tuán)隊(duì)在光量子處理器上成功實(shí)現(xiàn)拓?fù)鋽?shù)據(jù)分析

選自arXiv

作者：黃合良等

機(jī)器之心編譯

參與：劉曉坤

近日，來(lái)自中國(guó)科學(xué)技術(shù)大學(xué)、中國(guó)科學(xué)院-阿里巴巴量子計(jì)算實(shí)驗(yàn)室等機(jī)構(gòu)，由潘建偉院士、陸朝陽(yáng)教授帶領(lǐng)的團(tuán)隊(duì)完成了在光量子處理器上執(zhí)行拓?fù)鋽?shù)據(jù)分析（TDA）的原理性實(shí)驗(yàn)演示驗(yàn)證。TDA可以抵抗一定噪聲的干擾，從數(shù)據(jù)中提取有用信息，而量子版本的TDA能實(shí)現(xiàn)對(duì)經(jīng)典最優(yōu)TDA算法的指數(shù)級(jí)加速。量子TDA算法也是繼Shor算法（用于大數(shù)因子分解進(jìn)行密碼破譯）、Grover算法（用于搜索問(wèn)題）、HHL算法（用于解線性方程組）之后，人類(lèi)在量子計(jì)算機(jī)上可使用的一種新算法。該研究為在量子計(jì)算機(jī)上進(jìn)行高維數(shù)據(jù)處理、甚至人工智能算法領(lǐng)域的探索打開(kāi)了方向。

論文：DemonstrationofTopologicalDataAnalysisonaQuantumProcessor

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

通過(guò)識(shí)別帶噪聲、非結(jié)構(gòu)化數(shù)據(jù)的底層結(jié)構(gòu)，拓?fù)鋽?shù)據(jù)分析（TDA）可以魯棒地從數(shù)據(jù)中提取有用信息。最近，人們提出了一種有效的量子算法[Lloyd,Garnerone,Zanardi,Nat.Commun.7,10138(2016)]，用于計(jì)算數(shù)據(jù)點(diǎn)的貝蒂數(shù)（一種拓?fù)涮卣?，描述散點(diǎn)圖中各個(gè)維度的拓?fù)涠吹目倲?shù)）。我們利用一個(gè)六光子量子處理器實(shí)現(xiàn)了這個(gè)量子算法的原理性實(shí)驗(yàn)演示驗(yàn)證，成功地分析了一個(gè)包含三個(gè)數(shù)據(jù)點(diǎn)的網(wǎng)絡(luò)的貝蒂數(shù)拓?fù)涮卣?，為量子?jì)算領(lǐng)域的數(shù)據(jù)分析提供了新的探索思路和研究方法。

在探索性數(shù)據(jù)分析和數(shù)據(jù)挖掘中，我們的收集到的大數(shù)據(jù)通常編碼了非常有價(jià)值的信息，然而，這些數(shù)據(jù)往往規(guī)模很大，并且是非結(jié)構(gòu)化的、帶噪聲的、不完整的，從而使得從數(shù)據(jù)中提取有用信息變得很有挑戰(zhàn)性。TDA[1]將拓?fù)鋵W(xué)與數(shù)據(jù)分析進(jìn)行結(jié)合，可以從無(wú)結(jié)構(gòu)的數(shù)據(jù)中分析數(shù)據(jù)隱含的拓?fù)涮卣?，?duì)噪聲具有較強(qiáng)的魯棒性，提供了研究此類(lèi)數(shù)據(jù)的一種分析方法。特別地，持續(xù)同調(diào)（persistenthomology）[2][3]通過(guò)計(jì)算和分析數(shù)據(jù)的貝蒂數(shù)，用于提取數(shù)據(jù)的有用信息。其中，貝蒂數(shù)是一種拓?fù)涮卣?，第k個(gè)貝蒂數(shù)β_k表示為數(shù)據(jù)集中的k維洞的數(shù)量。例如，β_0、β_1、β_2分別代表了連通分支、一維洞和二維洞的數(shù)量。通過(guò)貝蒂數(shù)可以對(duì)數(shù)據(jù)進(jìn)行了抽象化表示，將其轉(zhuǎn)化為拓?fù)湫缘拿枋?，這對(duì)于理解數(shù)據(jù)集的底層結(jié)構(gòu)很有價(jià)值。使用TDA分析數(shù)據(jù)的貝蒂數(shù)這一分析方法近年來(lái)得到了快速發(fā)展，有望應(yīng)用于圖像識(shí)別[4]、信號(hào)處理[5]、網(wǎng)絡(luò)科學(xué)[6,7]、傳感器分析[8-11]、大腦連接[12,13]和fMRI數(shù)據(jù)分析[14,15]等。

然而實(shí)際上，當(dāng)處理復(fù)雜數(shù)據(jù)的時(shí)候，經(jīng)典的拓?fù)鋽?shù)據(jù)分析方法將面臨計(jì)算量巨大的問(wèn)題：n個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集擁有2^n個(gè)潛在拓?fù)浣Y(jié)構(gòu)，即使使用最強(qiáng)大的經(jīng)典計(jì)算機(jī)也難以求解規(guī)模不太大的數(shù)據(jù)集。目前，估計(jì)數(shù)據(jù)集合所有階貝蒂數(shù)的最優(yōu)經(jīng)典算法需要的時(shí)間復(fù)雜度為O(2^nlog(1/δ))[16–21]，其中δ為精度。此外，對(duì)某些類(lèi)型的拓?fù)浣Y(jié)構(gòu)[22]，計(jì)算所有階貝蒂數(shù)是PSPACE-hard的。

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

我們首次利用一個(gè)小規(guī)模的光子量子處理器，進(jìn)行了量子TDA算法的原理性演示驗(yàn)證。在實(shí)驗(yàn)中，我們?cè)趦煞N不同的距離參數(shù)下，監(jiān)控和識(shí)別三個(gè)數(shù)據(jù)點(diǎn)的貝蒂數(shù)的拓?fù)涮卣?，成功地展示了量子TDA算法的可行性，表明數(shù)據(jù)分析可能是未來(lái)量子計(jì)算的重要應(yīng)用。

為了計(jì)算貝蒂數(shù)，我們首先以數(shù)據(jù)點(diǎn)之間的關(guān)系拓?fù)涞乇碚鲾?shù)據(jù)。我們使用截?cái)嗑嚯x將數(shù)據(jù)點(diǎn)分類(lèi)為單純形（參見(jiàn)圖1（a）），即數(shù)據(jù)點(diǎn)的全連接子集。單純形的集合構(gòu)成一個(gè)單純復(fù)形，然后可以從該拓?fù)浣Y(jié)構(gòu)中提取貝蒂數(shù)等特征。這些拓?fù)浣Y(jié)構(gòu)如圖1（b-d）所示。

通過(guò)確定?所有范圍的貝蒂數(shù)的完整集合，我們可以構(gòu)建條形碼（參見(jiàn)圖1（e））[39]，即貝蒂數(shù)的距離依賴(lài)形式的參數(shù)化版本。H_k區(qū)域內(nèi)的每個(gè)條形代表一個(gè)k維洞，條形的長(zhǎng)度表示其在參數(shù)中的存在持續(xù)性。利用條形碼，我們可以定量地將短條形當(dāng)做拓?fù)湓肼曔^(guò)濾掉，并將長(zhǎng)條形作為重要的特征（條形的長(zhǎng)度表示其對(duì)抗間距變化的存在持續(xù)性）。在圖1（e）中，在H_1區(qū)域有一個(gè)條形延展了很長(zhǎng)的范圍，從而我們確定該非結(jié)構(gòu)化數(shù)據(jù)（圖1（b））的底層拓?fù)涮卣魇且粋€(gè)圓。

圖1：（a）k-單純形（圖中展示了k=0、1、2、3的例子）是k+1個(gè)數(shù)據(jù)點(diǎn)的全連接集合。（b）數(shù)據(jù)點(diǎn)的散點(diǎn)圖。（c）使用某些任意的指標(biāo)以量化數(shù)據(jù)點(diǎn)之間的距離，（以數(shù)據(jù)點(diǎn)為，圓心直徑為?）圓彼此接觸的數(shù)據(jù)點(diǎn)之間以邊連接。（d）單純復(fù)形是單純形的集合。著色區(qū)域表示復(fù)形中的不同單純形。（e）條形碼的結(jié)構(gòu)。水平軸代表距離?。在H_k的任意區(qū)域中，條形和垂直線的交點(diǎn)數(shù)等于（距離?對(duì)應(yīng)的）貝蒂數(shù)β_k。

一般地，量子TDA算法有兩個(gè)主要步驟（參見(jiàn)圖2（a））。首先訪問(wèn)數(shù)據(jù)，構(gòu)造的拓?fù)浣Y(jié)構(gòu)k-單純形的均勻混態(tài)。該步驟的時(shí)間復(fù)雜度依賴(lài)于k-單純形的比例，在最差的情況下是指數(shù)量級(jí)的。但是在實(shí)際應(yīng)用中，復(fù)雜拓?fù)浣Y(jié)構(gòu)中k-單純形的比例一般不會(huì)太小。所以，在實(shí)際應(yīng)用中，無(wú)論用經(jīng)典算法還是Grover算法（進(jìn)一步的二次型算法加速）都可以高效地實(shí)現(xiàn)這個(gè)步驟。在量子算法中，這個(gè)步驟可以分成兩小步：（1a）單純復(fù)形量子態(tài)的制備；（1b）均勻混態(tài)的構(gòu)造。（2）揭示結(jié)構(gòu)中的拓?fù)洳蛔兞?，這個(gè)步驟使用相位估計(jì)算法[40]實(shí)現(xiàn)，在量子計(jì)算機(jī)上，該算法相對(duì)經(jīng)典算法能實(shí)現(xiàn)指數(shù)級(jí)加速，實(shí)際證明[23,24]它的時(shí)間復(fù)雜度為O（n^5/δ），其中δ為計(jì)算精度。

圖2：量子TDA的量子線路。（a）原始量子算法線路的簡(jiǎn)單示意圖。（b）包含三個(gè)數(shù)據(jù)點(diǎn)的散點(diǎn)圖。

（c）1-單純形量子態(tài)（3

的圖表征。第一個(gè)和第二個(gè)數(shù)據(jù)點(diǎn)由一條邊連接。

（d）1-單純形量子態(tài)（4

第一個(gè)數(shù)據(jù)點(diǎn)分別和第二個(gè)和第三個(gè)數(shù)據(jù)點(diǎn)連接。（e）5量子比特的優(yōu)化量子線路。不同顏色的模塊代表4個(gè)基本階段（單純復(fù)形制備、構(gòu)造混態(tài)、相位估計(jì)、測(cè)量）。

圖3：實(shí)驗(yàn)裝置。中心波長(zhǎng)為394nm的紫外激光脈沖（脈沖持續(xù)時(shí)間為150飛秒，脈沖重復(fù)頻率為80MHz）通過(guò)三個(gè)偏硼酸鋇（BBO）晶體[42]以生成三對(duì)糾纏光子對(duì)(|H>|V>+|V>|H>)/√2（空間模式分別為1-2、3-4、5-6，細(xì)節(jié)參見(jiàn)附錄1）。光子2（3）和4（5）在PBS上進(jìn)行干涉。所有的光子使用3-nm帶寬的過(guò)濾器進(jìn)行光譜過(guò)濾。C-BBO：三明治形態(tài)的BBO+HWP+BBO組合；QWP：四分之一玻片；POL：起偏器；SC-YVO4：用于空間補(bǔ)償?shù)腨VO4晶體；TC-YVO4：用于時(shí)間補(bǔ)償?shù)腨VO4晶體。

圖4：最終的實(shí)驗(yàn)結(jié)果。最終的輸出通過(guò)在泡利-Z基上測(cè)量本征值寄存器確定。兩個(gè)不同1-單純形的態(tài)輸入的測(cè)量期望值（藍(lán)色條形）和理論預(yù)測(cè)值（灰色條形）如（a）和（b）所示。誤差線表示1個(gè)標(biāo)準(zhǔn)偏差，它是根據(jù)原始數(shù)據(jù)，通過(guò)泊松分布推導(dǎo)得出的（c）0

（a）的量子態(tài)：

（b）的量子態(tài)：

本文為機(jī)器之心編譯，轉(zhuǎn)載請(qǐng)聯(lián)系本公眾號(hào)獲得授權(quán)。

?------------------------------------------------

加入機(jī)器之心（全職記者/實(shí)習(xí)生）：hr@jiqizhixin.com

投稿或?qū)で髨?bào)道：editor@jiqizhixin.com

廣告&商務(wù)合作：bd@jiqizhixin.com