量子計算再一次「被打敗了」。今年 8 月，剛剛年滿 18 歲的 Ewin Tang 證明了經(jīng)典算法能以和量子計算機相近的速度解決推薦問題，這位天才少女（更正：不是少年）的驚人成就引來了媒體爭相報道，和人們的廣泛討論。

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

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

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

今年 5 月，兩位理論計算機科學家解決了一個長達 25 年的假設(shè)。他們證明了量子計算機在非常復雜的任務(wù)上比經(jīng)典計算機更加高效，例如測試數(shù)值是否隨機。換種說法即：他們定義了一類特定的計算問題。他們在一定程度上證明了量子計算機能夠有效解決這個問題，而傳統(tǒng)計算機卻永遠無法解決。

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

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

報告地址：https://www.nap.edu/read/25196/chapter/1

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

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

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

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

論文：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ù)進行長度平方的采樣，實現(xiàn)了低秩矩陣的偽逆，并使用快速采樣技術(shù)從解決方案到問題 Ax = b 進行采樣。我們通過找到 Avia 子采樣的近似奇異值分解，然后利用奇異值的倒數(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)域的一些研究者認為，經(jīng)典計算機在這方面的使用實際上是量子計算的成功，因為它們表明了量子思維方式如何產(chǎn)生影響——即使是在量子計算機出現(xiàn)之前的今天（畢竟這些算法也是 Quantum-inspired）。專家們還指出了長期以來人們所知的量子計算機優(yōu)勢「項目」，例如網(wǎng)絡(luò)搜索。在另外一些情況下——例如將大整數(shù)分解為素數(shù)（質(zhì)因數(shù)分解）或模擬材料的電特性——科學家們目前認為量子計算機可能仍然具有優(yōu)勢，盡管這尚未在數(shù)學上得到證明。

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