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