量子計(jì)算再一次「被打敗了」。今年 8 月，剛剛年滿 18 歲的 Ewin Tang 證明了經(jīng)典算法能以和量子計(jì)算機(jī)相近的速度解決推薦問題，這位天才少女（更正：不是少年）的驚人成就引來了媒體爭相報(bào)道，和人們的廣泛討論。
Ewin Tang 已經(jīng)完成了在 UT Austin 的本科學(xué)位，目前正在華盛頓大學(xué)（University of Washington）攻讀計(jì)算機(jī)科學(xué)博士，她近期與 András Gilyén，以及量子計(jì)算先驅(qū) Seth Lloyd 共同完成的論文引起了 Nature 的注意。在這一研究中，科學(xué)家們再次使用經(jīng)典方式重構(gòu)了此前被認(rèn)為量子計(jì)算占據(jù)優(yōu)勢的算法。
看來，量子計(jì)算方式可以帶來的優(yōu)勢并沒有人們想象的那么多。未來的超級計(jì)算機(jī)不一定是量子計(jì)算機(jī)，你覺得呢？
在某些任務(wù)中，量子計(jì)算機(jī)可能無法超越已有的系統(tǒng)。圖源：Greg Kendall-Ball/Nature
今年 5 月，兩位理論計(jì)算機(jī)科學(xué)家解決了一個長達(dá) 25 年的假設(shè)。他們證明了量子計(jì)算機(jī)在非常復(fù)雜的任務(wù)上比經(jīng)典計(jì)算機(jī)更加高效，例如測試數(shù)值是否隨機(jī)。換種說法即：他們定義了一類特定的計(jì)算問題。他們在一定程度上證明了量子計(jì)算機(jī)能夠有效解決這個問題，而傳統(tǒng)計(jì)算機(jī)卻永遠(yuǎn)無法解決。
從計(jì)算復(fù)雜度的角度，PH 涵蓋了任何可能的傳統(tǒng)計(jì)算機(jī)所能解決的問題，他們則找到了證明是 BQP（涵蓋了量子計(jì)算機(jī)可以解決的所有問題）卻不是 PH 的問題。
盡管如此，這樣的工作并不能證明現(xiàn)在圍繞量子計(jì)算的期望的合理性。美國國家科學(xué)院、工程學(xué)和醫(yī)學(xué)院的最新報(bào)告（由領(lǐng)先的谷歌和微軟研究人員撰寫）強(qiáng)調(diào)了構(gòu)建實(shí)用的量子計(jì)算機(jī)的技術(shù)障礙。報(bào)告稱，創(chuàng)建這樣的機(jī)器至少需要十年時(shí)間。
報(bào)告地址：https://www.nap.edu/read/25196/chapter/1
劍橋麻省理工學(xué)院的理論物理學(xué)家 Seth Lloyd 在談到這個領(lǐng)域正處于爆炸性進(jìn)展期，「但是炒作也在失去控制... 整個量子計(jì)算領(lǐng)域現(xiàn)在正在走向混亂，」他說。
量子計(jì)算機(jī)是必需的嗎？今年 8 月一位 18 歲的計(jì)算機(jī)科學(xué)家在一項(xiàng)引人注目的研究中對此提出了質(zhì)疑，至少在一類特定任務(wù)中。
Ewin Tang 開發(fā)了一種非常高效的經(jīng)典推薦系統(tǒng)算法，相比于之前的最快經(jīng)典算法有指數(shù)級提高，并和量子推薦系統(tǒng)算法的速度 xian 相當(dāng)。Tang 的算法不一定實(shí)用，因此它不會取代當(dāng)前的算法，除非它在目前的形式中得到實(shí)質(zhì)性的改進(jìn)，它只對真正巨大規(guī)模的數(shù)據(jù)集有用。但是，在它有機(jī)會在實(shí)際機(jī)器上運(yùn)行之前，針對同一任務(wù)的量子算法現(xiàn)在已經(jīng)沒有實(shí)際意義了。
上個月，現(xiàn)在已經(jīng)位于西雅圖華盛頓大學(xué)的 Tang 對量子機(jī)器學(xué)習(xí)算法實(shí)現(xiàn)了二次沖擊。她和兩位同事證明了在另一項(xiàng)機(jī)器學(xué)習(xí)任務(wù)上，量子優(yōu)勢也不復(fù)存在。德克薩斯大學(xué)的另一個團(tuán)隊(duì)也獨(dú)立地取得了相同的結(jié)論。計(jì)算機(jī)科學(xué)家用比喻回應(yīng)了這個消息。例如，將 Tang 比作屠殺量子社區(qū)的希望和夢想的角斗士。對于 Tang 的合著者 Seth Lloyd 來說，這是一個苦樂參半的時(shí)刻，他寫了一個被打敗的量子算法。
論文：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è)對輸入數(shù)據(jù)進(jìn)行長度平方的采樣，實(shí)現(xiàn)了低秩矩陣的偽逆，并使用快速采樣技術(shù)從解決方案到問題 Ax = b 進(jìn)行采樣。我們通過找到 Avia 子采樣的近似奇異值分解，然后利用奇異值的倒數(shù)來實(shí)現(xiàn)偽逆。原則上，該方法還可用于將任何所需的「平滑」函數(shù)應(yīng)用于奇異值。由于許多量子算法可以表示為奇異值變換問題，我們的結(jié)果表明，更多的低秩量子算法可以有效地「去量化」為經(jī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）。專家們還指出了長期以來人們所知的量子計(jì)算機(jī)優(yōu)勢「項(xiàng)目」，例如網(wǎng)絡(luò)搜索。在另外一些情況下——例如將大整數(shù)分解為素?cái)?shù)（質(zhì)因數(shù)分解）或模擬材料的電特性——科學(xué)家們目前認(rèn)為量子計(jì)算機(jī)可能仍然具有優(yōu)勢，盡管這尚未在數(shù)學(xué)上得到證明。
量子計(jì)算機(jī)是一種尚未存在的技術(shù)，它可以解決的問題還有待人們的發(fā)現(xiàn)。同時(shí)，研究者們也正在尋找使用經(jīng)典策略可以解決的問題。兩者都是有前途的研究方向。量子計(jì)算設(shè)備仍然是一個有價(jià)值的目標(biāo)，但它并不是通往未來的唯一途徑。