十八歲天才攜手Seth Lloyd顛覆量子計(jì)算

Ewin Tang 已經(jīng)完成了在 UT Austin 的本科學(xué)位，目前正在華盛頓大學(xué)（University of Washington）攻讀計(jì)算機(jī)科學(xué)博士，她近期與 András Gilyén，以及量子計(jì)算先驅(qū) Seth Lloyd 共同完成的論文引起了 Nature 的注意。在這一研究中，科學(xué)家們?cè)俅问褂媒?jīng)典方式重構(gòu)了此前被認(rèn)為量子計(jì)算占據(jù)優(yōu)勢(shì)的算法。

看來(lái)，量子計(jì)算方式可以帶來(lái)的優(yōu)勢(shì)并沒(méi)有人們想象的那么多。未來(lái)的超級(jí)計(jì)算機(jī)不一定是量子計(jì)算機(jī)，你覺(jué)得呢？

在某些任務(wù)中，量子計(jì)算機(jī)可能無(wú)法超越已有的系統(tǒng)。圖源：Greg Kendall-Ball/Nature

今年 5 月，兩位理論計(jì)算機(jī)科學(xué)家解決了一個(gè)長(zhǎng)達(dá) 25 年的假設(shè)。他們證明了量子計(jì)算機(jī)在非常復(fù)雜的任務(wù)上比經(jīng)典計(jì)算機(jī)更加高效，例如測(cè)試數(shù)值是否隨機(jī)。換種說(shuō)法即：他們定義了一類(lèi)特定的計(jì)算問(wèn)題。他們?cè)谝欢ǔ潭壬献C明了量子計(jì)算機(jī)能夠有效解決這個(gè)問(wèn)題，而傳統(tǒng)計(jì)算機(jī)卻永遠(yuǎn)無(wú)法解決。

從計(jì)算復(fù)雜度的角度，PH 涵蓋了任何可能的傳統(tǒng)計(jì)算機(jī)所能解決的問(wèn)題，他們則找到了證明是 BQP（涵蓋了量子計(jì)算機(jī)可以解決的所有問(wèn)題）卻不是 PH 的問(wèn)題。

盡管如此，這樣的工作并不能證明現(xiàn)在圍繞量子計(jì)算的期望的合理性。美國(guó)國(guó)家科學(xué)院、工程學(xué)和醫(yī)學(xué)院的最新報(bào)告（由領(lǐng)先的谷歌和微軟研究人員撰寫(xiě)）強(qiáng)調(diào)了構(gòu)建實(shí)用的量子計(jì)算機(jī)的技術(shù)障礙。報(bào)告稱(chēng)，創(chuàng)建這樣的機(jī)器至少需要十年時(shí)間。

報(bào)告地址：https://www.nap.edu/read/25196/chapter/1

劍橋麻省理工學(xué)院的理論物理學(xué)家 Seth Lloyd 在談到這個(gè)領(lǐng)域正處于爆炸性進(jìn)展期，「但是炒作也在失去控制... 整個(gè)量子計(jì)算領(lǐng)域現(xiàn)在正在走向混亂，」他說(shuō)。

量子計(jì)算機(jī)是必需的嗎？今年 8 月一位 18 歲的計(jì)算機(jī)科學(xué)家在一項(xiàng)引人注目的研究中對(duì)此提出了質(zhì)疑，至少在一類(lèi)特定任務(wù)中。

Ewin Tang 開(kāi)發(fā)了一種非常高效的經(jīng)典推薦系統(tǒng)算法，相比于之前的最快經(jīng)典算法有指數(shù)級(jí)提高，并和量子推薦系統(tǒng)算法的速度 xian 相當(dāng)。Tang 的算法不一定實(shí)用，因此它不會(huì)取代當(dāng)前的算法，除非它在目前的形式中得到實(shí)質(zhì)性的改進(jìn)，它只對(duì)真正巨大規(guī)模的數(shù)據(jù)集有用。但是，在它有機(jī)會(huì)在實(shí)際機(jī)器上運(yùn)行之前，針對(duì)同一任務(wù)的量子算法現(xiàn)在已經(jīng)沒(méi)有實(shí)際意義了。

上個(gè)月，現(xiàn)在已經(jīng)位于西雅圖華盛頓大學(xué)的 Tang 對(duì)量子機(jī)器學(xué)習(xí)算法實(shí)現(xiàn)了二次沖擊。她和兩位同事證明了在另一項(xiàng)機(jī)器學(xué)習(xí)任務(wù)上，量子優(yōu)勢(shì)也不復(fù)存在。德克薩斯大學(xué)的另一個(gè)團(tuán)隊(duì)也獨(dú)立地取得了相同的結(jié)論。計(jì)算機(jī)科學(xué)家用比喻回應(yīng)了這個(gè)消息。例如，將 Tang 比作屠殺量子社區(qū)的希望和夢(mèng)想的角斗士。對(duì)于 Tang 的合著者 Seth Lloyd 來(lái)說(shuō)，這是一個(gè)苦樂(lè)參半的時(shí)刻，他寫(xiě)了一個(gè)被打敗的量子算法。

論文：Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension

論文地址：https://arxiv.org/abs/1811.04909

摘要：我們?yōu)榈椭染仃嚇?gòu)造了量子矩陣求逆算法（HHL）的有效經(jīng)典變體。受 Tang 最近工作的啟發(fā)，我們假設(shè)對(duì)輸入數(shù)據(jù)進(jìn)行長(zhǎng)度平方的采樣，實(shí)現(xiàn)了低秩矩陣的偽逆，并使用快速采樣技術(shù)從解決方案到問(wèn)題 Ax = b 進(jìn)行采樣。我們通過(guò)找到 Avia 子采樣的近似奇異值分解，然后利用奇異值的倒數(shù)來(lái)實(shí)現(xiàn)偽逆。原則上，該方法還可用于將任何所需的「平滑」函數(shù)應(yīng)用于奇異值。由于許多量子算法可以表示為奇異值變換問(wèn)題，我們的結(jié)果表明，更多的低秩量子算法可以有效地「去量化」為經(jīng)典的長(zhǎng)度平方采樣算法。

另一篇：Quantum-inspired sublinear classical algorithms for solving low-rank linear systems

論文地址：https://arxiv.org/abs/1811.04852

該領(lǐng)域的一些研究者認(rèn)為，經(jīng)典計(jì)算機(jī)在這方面的使用實(shí)際上是量子計(jì)算的成功，因?yàn)樗鼈儽砻髁肆孔铀季S方式如何產(chǎn)生影響——即使是在量子計(jì)算機(jī)出現(xiàn)之前的今天（畢竟這些算法也是 Quantum-inspired）。專(zhuān)家們還指出了長(zhǎng)期以來(lái)人們所知的量子計(jì)算機(jī)優(yōu)勢(shì)「項(xiàng)目」，例如網(wǎng)絡(luò)搜索。在另外一些情況下——例如將大整數(shù)分解為素?cái)?shù)（質(zhì)因數(shù)分解）或模擬材料的電特性——科學(xué)家們目前認(rèn)為量子計(jì)算機(jī)可能仍然具有優(yōu)勢(shì)，盡管這尚未在數(shù)學(xué)上得到證明。

量子計(jì)算機(jī)是一種尚未存在的技術(shù)，它可以解決的問(wèn)題還有待人們的發(fā)現(xiàn)。同時(shí)，研究者們也正在尋找使用經(jīng)典策略可以解決的問(wèn)題。兩者都是有前途的研究方向。量子計(jì)算設(shè)備仍然是一個(gè)有價(jià)值的目標(biāo)，但它并不是通往未來(lái)的唯一途徑。