徐令予:18歲華裔少年挑落量子霸權

【文/ 觀察者網專欄作者 徐令予】

量子計算的一個重要成果被一個18歲少年推翻。

自古英雄出少年！18歲的美國德克薩斯州華裔少年Ewin Tang的論文證明，經典計算機幾乎可以像量子計算機一樣快速地解決「推薦問題」。量子加速（又稱量子霸權）的一個最佳案例如今卻被拉下了神壇[1]。

推薦算法是計算機領域中的一種重要算法，它可以用來為客戶可能喜歡的產品和服務提供建議。例如影視網站從海量數據中獲取到用戶數據，根據用戶過去喜歡或搜索過的影視內容，為用戶推薦與之相似的影視作品，而內容相似性的度量，是算法運用的關鍵。

我們可以將這些數據視為一個矩陣，橫向代表電影，豎向代表用戶，而網格中各點是某用戶對某電影的喜好程度的量化值。一個好的算法可以通過快速準確地識別電影和用戶之間的相似性，並填充矩陣中的空白以生成推薦。

2016年，計算機科學家Iordanis Kerenidis和Anupam Prakash發布了一種量子算法，該算法解決推薦問題的速度比任何已知經典算法要快得多。他們通過簡化問題來實現量子加速：不是填寫整個矩陣並確定推薦單一最佳產品，而是先將用戶根據他們的喜好分類為人數不多的小組，並對現有數據進行抽樣，從而生成足夠好的建議。

在這之前，量子計算機解決某些問題比經典計算機有指數式加速優勢的例子已經存在，但這些問題都比較專門和單一，量子計算機的優勢有很大局限性。 Kerenidis和Prakash的研究結果令人興奮，因為這是一種具有普遍意義的算法，而且又有著人們非常關心的實際應用價值。

「據我所知，它是機器學習和大數據中的一個好例子，我們展示了量子計算機可以做一些我們仍然不知道如何用經典辦法解決的事情。」巴黎計算機基礎科學研究所的科學家Kerenidis說。

一個18歲的少年有何能耐改變量子計算的歷程？希望的種子埋下於四年之前。2014年，14歲的Ewin連跳幾級後入讀於德州大學奧斯汀分校，主修數學和計算機科學。2017年春天，Ewin選修了斯科特·亞倫森（Scott Aaronson）教授的量子信息課程，亞倫森教授是量子計算專家。亞倫森教授慧眼識英雄，很快發覺Ewin是匹千裡馬，於是主動提出願意為Ewin同學擔任獨立研究項目的顧問。

亞倫森教授給了Ewin一些可供選擇的課題，這其中就包括了「推薦問題」，Ewin選擇了它，但有點不情不願。「我有些猶豫不決，因為當我初看時，這似乎是一個難題，但這又是他給我的問題中間最簡單的一個。」Ewin說。

2017年秋季開始，Ewin全身投入工作，打算將「推薦問題」作為自己的大學畢業論文。亞倫森教授和Ewin的原始想法是：通過證明不存在快速的經典推薦算法，從而確認Kerenidis和Prakash的量子加速算法的真實價值。幾個月來，Ewin一直拚著命想證明關於「推薦問題」不存在任何快速經典算法。「山窮水盡疑無路，柳暗花明又一村。」隨著時間的推移，Ewin開始看到了構建快速經典算法的一線希望。

「我開始相信有一種快速的經典算法，但我無法向自己證明這一點，因為亞倫森教授似乎認為這不可能，而他是權威，」Ewin說。隨著畢業論文的最後期限接近，Ewin寫信把自己的懷疑告訴了教授。

在今年整個春天裡，Ewin把自己的想法變成嚴格的算法，並與亞倫森教授合作把算法中的一些步驟作出澄清和證明。Ewin發現的快速經典算法直接受到Kerenidis和Prakash兩年前發現的快速量子算法的啟發。Ewin發覺他倆的算法中使用的那種採樣技術也可以在經典環境中複製。與Kerenidis和Prakash的算法一樣，Ewin的經典算法在多重對數時間內運行，這意味著計算時間與數據量（例如數據集中的用戶和產品的數量）的關係是對數函數，它比任何先前已知的經典算法要快指數倍，與量子算法速度對等。

算法完成後，亞倫森教授希望在公開發布之前確定它是正確的，他真心希望自己的愛徒的學術生涯有一個好的開端。

亞倫森教授對Ewin同學的培養和提攜真可謂不遺餘力，為此他作出了一個重要的決定。6月份，亞倫森教授出席在加州大學伯克利分校舉行的量子計算研討會。該領域的許多大腕都將出現在那裡，其中包括了Kerenidis和Prakash。在正式會議結束後的幾天裡，由亞倫森教授出面邀請Ewin同學來伯克利大學非正式地介紹他的新算法。

在6月18日和19日的早晨，Ewin做了兩次講座，同時接受觀眾提問。四小時的講座結束時，人們已經有了共識：Ewin的創新經典算法似乎是正確的。然而，會議室的許多聽眾都沒有意識到這位演講者的真實年齡。 「我不知道Tang先生是18歲，從他的演講中完全感覺不到這一點。對我來說，他就是一個非常成熟的演講者。」這位量子計算專家Kerenidis如是說。目前，Ewin的論文正式發布之前正在面臨同行的評審。