十八歲華裔天才再次顛覆量子計算，引來Nature報道

選自Nature，機器之心編譯，參與：劉曉坤、李澤南。

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

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

看來，量子計算方式可以帶來的優勢並沒有人們想像的那麼多。未來的超級計算機不一定是量子計算機，你覺得呢？

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

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

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

儘管如此，這樣的工作並不能證明現在圍繞量子計算的期望的合理性。美國國家科學院、工程學和醫學院的最新報告（由領先的谷歌和微軟研究人員撰寫）強調了構建實用的量子計算機的技術障礙。報告稱，創建這樣的機器至少需要十年時間。

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

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

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

Ewin Tang 開發了一種非常高效的經典推薦系統演算法，相比於之前的最快經典演算法有指數級提高，並和量子推薦系統演算法的速度 xian 相當。Tang 的演算法不一定實用，因此它不會取代當前的演算法，除非它在目前的形式中得到實質性的改進，它只對真正巨大規模的數據集有用。但是，在它有機會在實際機器上運行之前，針對同一任務的量子演算法現在已經沒有實際意義了。

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

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

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

摘要：我們為低秩矩陣構造了量子矩陣求逆演算法（HHL）的有效經典變體。受 Tang 最近工作的啟發，我們假設對輸入數據進行長度平方的採樣，實現了低秩矩陣的偽逆，並使用快速採樣技術從解決方案到問題 Ax = b 進行採樣。我們通過找到 Avia 子採樣的近似奇異值分解，然後利用奇異值的倒數來實現偽逆。原則上，該方法還可用於將任何所需的「平滑」函數應用於奇異值。由於許多量子演算法可以表示為奇異值變換問題，我們的結果表明，更多的低秩量子演算法可以有效地「去量化」為經典的長度平方採樣演算法。

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

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

該領域的一些研究者認為，經典計算機在這方面的使用實際上是量子計算的成功，因為它們表明了量子思維方式如何產生影響——即使是在量子計算機出現之前的今天（畢竟這些演算法也是 Quantum-inspired）。專家們還指出了長期以來人們所知的量子計算機優勢「項目」，例如網路搜索。在另外一些情況下——例如將大整數分解為素數（質因數分解）或模擬材料的電特性——科學家們目前認為量子計算機可能仍然具有優勢，儘管這尚未在數學上得到證明。

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

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！