經(jīng)過(guò)量子破壞后，一種方法毫發(fā)無(wú)損地幸存下來(lái)

量子計(jì)算機(jī)被大肆宣傳，但事實(shí)是我們?nèi)匀徊淮_定它們有什么用。這些設(shè)備利用了亞原子世界的特殊物理特性，并有可能執(zhí)行普通經(jīng)典計(jì)算機(jī)根本無(wú)法執(zhí)行的計(jì)算。但事實(shí)證明，很難找到具有明顯「量子優(yōu)勢(shì)」的任何算法的例子，這些算法的性能超出了經(jīng)典機(jī)器的范圍。

在 21 世紀(jì) 10 年代的大部分時(shí)間里，許多計(jì)算機(jī)科學(xué)家認(rèn)為一組特定的應(yīng)用程序很有可能會(huì)發(fā)現(xiàn)這一優(yōu)勢(shì)。當(dāng)某些數(shù)據(jù)分析計(jì)算由量子計(jì)算機(jī)處理時(shí)，它們的速度會(huì)呈指數(shù)級(jí)增長(zhǎng)。

后來(lái)，Ewin Tang 出現(xiàn)了。2018年，18歲 的她剛從大學(xué)畢業(yè)，她找到了經(jīng)典計(jì)算機(jī)解決這些問(wèn)題的新方法，削弱了量子算法所承諾的優(yōu)勢(shì)。對(duì)于許多研究量子計(jì)算機(jī)的人來(lái)說(shuō)，Tang 的工作是一種清算。荷蘭量子計(jì)算研究中心 QuSoft 的理論計(jì)算機(jī)科學(xué)家克里 Chris Cade 說(shuō)：「這些超級(jí)令人興奮的用例一個(gè)接一個(gè)地被扼殺了?！?/span>

但有一種算法毫發(fā)無(wú)損地幸存下來(lái)：對(duì)一種用于研究數(shù)據(jù)「形狀」的小眾數(shù)學(xué)方法的量子扭曲，稱為拓?fù)鋽?shù)據(jù)分析 (TDA)。在 9 月份的一系列論文之后，研究人員現(xiàn)在認(rèn)為，這些 TDA 計(jì)算超出了經(jīng)典計(jì)算機(jī)的掌握范圍，這可能是由于與量子物理學(xué)的隱藏聯(lián)系。但這種量子優(yōu)勢(shì)可能只出現(xiàn)在高度特定的條件下，使其實(shí)用性受到質(zhì)疑。

共同創(chuàng)建量子 TDA 算法的麻省理工學(xué)院量子力學(xué)工程師 Seth Lloyd 對(duì)其起源記憶猶新。2015 年，他和物理學(xué)家 Paolo Zanardi 正在比利牛斯山脈一個(gè)田園詩(shī)般的小鎮(zhèn)參加量子物理研討會(huì)。會(huì)議開始幾天后，他們跳過(guò)會(huì)談，在酒店露臺(tái)上閑逛，試圖讓自己的頭腦沉浸在一種他們聽說(shuō)過(guò)的用于分析數(shù)據(jù)的「瘋狂抽象」數(shù)學(xué)技術(shù)中。

Zanardi 愛(ài)上了 TDA 背后的數(shù)學(xué)，它植根于拓?fù)鋵W(xué)，這是數(shù)學(xué)的一個(gè)分支，關(guān)注形狀被壓扁、拉伸或扭曲時(shí)仍然存在的特征。「這是滲透一切的數(shù)學(xué)分支之一，」萊頓大學(xué)的量子計(jì)算研究員 Vedran Dunjko 說(shuō)?！杆鼰o(wú)處不在。」 該領(lǐng)域的核心問(wèn)題之一是物體上的孔數(shù)，稱為 Betti 數(shù)。

拓?fù)淇梢詳U(kuò)展到我們熟悉的三個(gè)維度之外，使研究人員能夠計(jì)算 4 維、10 維甚至 100 維物體中的 Betti 數(shù)。這使得拓?fù)涑蔀榉治龃髷?shù)據(jù)集形狀的有吸引力的工具，大數(shù)據(jù)集還可以包括數(shù)百個(gè)相關(guān)性和連接維度。

目前，經(jīng)典計(jì)算機(jī)最多只能計(jì)算四個(gè)維度的 Betti 數(shù)。在那個(gè)比利牛斯山酒店的露臺(tái)上，Lloyd 和Zanardi試圖打破這個(gè)障礙。經(jīng)過(guò)大約一周的討論和潦草的方程式，他們有了量子算法的基本框架，可以估計(jì)非常高維度的數(shù)據(jù)集中的 Betti 數(shù)。他們于 2016 年發(fā)表了它，研究人員歡迎它進(jìn)入他們認(rèn)為具有有意義的量子優(yōu)勢(shì)的數(shù)據(jù)分析量子應(yīng)用組。

論文鏈接：
https://www.nature.com/articles/ncomms10138

兩年之內(nèi)，TDA 是唯一一個(gè)沒(méi)有受到 Tang 的工作影響的。雖然 Tang 承認(rèn) TDA「確實(shí)與其他的不同」，但她和其他研究人員不禁要問(wèn)，它的逃脫在多大程度上可能是僥幸。

Dunjko 和他的同事們決定再試一次，為 TDA 尋找一種可以消除其量子優(yōu)勢(shì)的經(jīng)典算法。為此，他們?cè)噲D將 Tang 的方法應(yīng)用于這一特定應(yīng)用，但不知道會(huì)發(fā)生什么?！肝覀冋娴牟淮_定。有理由相信這一個(gè)可能在‘Tang 化’中幸存下來(lái)，」他回憶道。

活下來(lái)了。在 2020 年首次作為預(yù)印本發(fā)布并于今年 10 月在 Quantum 上發(fā)表的結(jié)果中，Dunjko 的團(tuán)隊(duì)表明 TDA 的存活并非僥幸。要找到一種能夠與量子算法保持同步的經(jīng)典算法，「你必須做一些不同的事情，而不僅僅是盲目地將 Ewin Tang 的 [過(guò)程] 應(yīng)用于 Seth Lloyd 的算法，」該論文的合著者之一 Cade 說(shuō)。

論文鏈接：https://quantum-journal.org/papers/q-2022-11-10-855/

我們不確定經(jīng)典算法能否趕上 TDA，但我們可能很快就會(huì)趕上。「為了證明這一點(diǎn)，我們需要采取四個(gè)步驟……也許我們已經(jīng)采取了三個(gè)步驟，」初創(chuàng)公司 QC Ware 的理論物理學(xué)家 Marcos Crichigno 說(shuō)。迄今為止最好的證據(jù)來(lái)自他去年與 Cade 一起發(fā)表的一篇論文，該論文表明經(jīng)典計(jì)算機(jī)無(wú)法有效地解決類似的拓?fù)溆?jì)算。Crichigno 目前正在努力為 TDA 專門證明相同的結(jié)果。

Marcos Crichigno。

Crichigno 懷疑 TDA 的彈性指向與量子力學(xué)的內(nèi)在聯(lián)系——而且是完全出乎意料的系。這種聯(lián)系來(lái)自超對(duì)稱性，這是粒子物理學(xué)中的一種理論，它提出構(gòu)成物質(zhì)的粒子和攜帶力的粒子之間存在深度對(duì)稱性。事實(shí)證明，正如物理學(xué)家 Ed Witten 在 20 世紀(jì) 80 年代所解釋的那樣，拓?fù)鋵W(xué)的數(shù)學(xué)工具可以輕松地描述這些超對(duì)稱系統(tǒng)。受 Witten 工作的啟發(fā)，Crichigno 一直在通過(guò)使用超對(duì)稱來(lái)研究拓?fù)鋪?lái)反轉(zhuǎn)這種聯(lián)系。

「太瘋狂了。這是一種非常、非常、非常奇怪的聯(lián)系，」Dunjko 說(shuō)，他沒(méi)有參與 Crichigno 的工作。

這種隱藏的量子聯(lián)系可能是 TDA 與眾不同的原因，Cade 說(shuō)，他曾與 Crichigno 就此進(jìn)行過(guò)合作。「從本質(zhì)上講，這確實(shí)是一個(gè)量子力學(xué)問(wèn)題，盡管它看起來(lái)不像，」他說(shuō)。

但是，雖然 TDA 目前仍然是量子優(yōu)勢(shì)的一個(gè)例子，但亞馬遜網(wǎng)絡(luò)服務(wù)、谷歌和麻省理工學(xué)院 Lloyd 實(shí)驗(yàn)室最近的研究已經(jīng)大大縮小了優(yōu)勢(shì)最明顯的可能場(chǎng)景。為了使算法的運(yùn)行速度比經(jīng)典技術(shù)快得多（通常是量子優(yōu)勢(shì)的標(biāo)準(zhǔn)），高維空洞的數(shù)量需要大到難以想象，達(dá)到數(shù)萬(wàn)億級(jí)。否則，該算法的近似技術(shù)根本就沒(méi)有效率，抹殺了對(duì)經(jīng)典計(jì)算機(jī)的任何有意義的改進(jìn)。

在現(xiàn)實(shí)世界的數(shù)據(jù)中，這是「一組很難找到的條件」，Cade 說(shuō)，他沒(méi)有參與這三篇論文中的任何一篇。谷歌研究的資深作者之一 Ryan Babbush 表示，很難確定這些情況是否存在，所以目前，我們只有直覺(jué)，他和 Cade 都不認(rèn)為這些情況會(huì)普遍存在。

Tang 現(xiàn)在是華盛頓大學(xué)的一名博士生，他認(rèn)為 TDA 不是該領(lǐng)域正在尋找的實(shí)際量子應(yīng)用，因?yàn)榇嬖谶@些局限性。她說(shuō)，「我認(rèn)為這個(gè)領(lǐng)域作為一個(gè)整體已經(jīng)重塑」以擺脫算法狩獵。她預(yù)計(jì)量子計(jì)算機(jī)對(duì)于了解量子系統(tǒng)本身最有用，而不是用于分析經(jīng)典數(shù)據(jù)。

但近期工作背后的研究人員并不認(rèn)為 TDA 是死胡同。在最近的預(yù)印本發(fā)布后，所有研究團(tuán)隊(duì)召開了一次 Zoom 會(huì)議，「我們每個(gè)人都知道下一步該怎么做，」與谷歌團(tuán)隊(duì)合作的 Dunjko 說(shuō)。例如，Crichigno 希望探究拓?fù)鋵W(xué)和量子力學(xué)之間的這種聯(lián)系會(huì)產(chǎn)生更多意想不到的量子問(wèn)題，這些問(wèn)題可能特別適合量子計(jì)算。

總是存在一種創(chuàng)造性的新古典方法的威脅，它可以做 Tang 和 Dunjko 做不到的事情，并最終推翻 TDA。Dunjko 說(shuō)：「我不會(huì)拿我的房子、我的車或我的貓打****，」這不會(huì)發(fā)生?！傅@個(gè)故事并沒(méi)有消亡。我認(rèn)為這是我一點(diǎn)都不擔(dān)心的主要原因?！?/span>

參考內(nèi)容：https://www.quantamagazine.org/after-a-classical-clobbering-a-quantum-advantage-remains-20221207/