18歲天才華裔少年用一個經典算法，推翻量子加速神話！

【新智元導讀】一位年僅18歲的華裔少年提出了一種傳統計算機AI算法，其運算速度可以與量子計算比肩，相對之前的傳統算法實作了運算速度的指數級增長。這一發現不僅推翻了兩位量子計算重量級人物的量子加速神話，而且證明了量子算法和經典算法研究之間存在富有成效的互相作用。

在本月早些時候在網上發表的一篇論文中，18歲的Ewin Tang證明用普通計算機可以解決一個重要的計算問題，其性能表現可能與量子計算機相當。

以最實際的問題“推薦問題”為例，這個問題中就涉及亞馬遜和Netflix等服務是怎樣确定使用者想要嘗試體驗哪些産品的。計算機科學家認為，這個問題是量子計算應用的典型範例之一，和傳統計算相比，量子計算解決這個問題速度可能呈指數級增長，這讓該問題成為對未來量子計算性能的重要驗證。現在Ewin Tang已經證明，事實不盡如此。

14歲上大學，18歲讀博士，挑戰量子計算領域示範問題

Ewin Tang今年春季畢業于德克薩斯大學奧斯汀分校，并将于今年秋季開始在華盛頓大學攻讀博士學位。“這曾經是量子加速計算的最明确的範例之一，不過現在已經不是了。”Ewin Tang說。

Ewin Tang在國小曾從四年級跳級至六年級，2014年，年僅14歲的他進入德克薩斯大學奧斯汀分校就讀，主修數學和計算機科學。2017年春，他選了量子計算方面的著名研究員Scott Aaronson講授的關于量子資訊的課程。Aaronson認為他是一位非常有才華的學生，并且自稱是一個獨立研究項目的顧問。Aaronson給了他一些可供選擇的問題，其中就包括推薦問題。Tang有點不情願地選擇了這個問題。

“我當時曾一度猶豫不決，因為這似乎是一個難題，但這是他給我的最簡單的問題了。”Ewin Tang說。

這類“推薦問題”旨在為使用者喜歡的産品提供建議。以Netflix為例，它知道你看過哪部電影，也了解其他數百萬使用者所觀看的内容。那麼根據這些資訊，你接下來可能想要觀看什麼電影？

你可以将這些資料視為在一張巨大網格或矩陣中排列，上方列出的是電影，側方列出的是使用者，而網絡中各點的值用于量化每個使用者對每部電影的喜愛程度。一個好的算法可以快速準确地識别電影和使用者之間的相似度，并填充矩陣中的空白，為使用者推薦喜歡的電影。

2016年，計算機科學家Iordanis Kerenidis和Anupam Prakash釋出了一種量子算法，能夠比任何已知經典算法更加快速地解決推薦問題。他們通過對問題模型的簡化來實作這一量子加速過程：不用填滿整個矩陣并确定唯一最佳推薦結果，而是開發一種将使用者進行分類的方式：比如使用者是喜歡商業大片還是獨立電影？并對現有資料進行抽樣，以生成品質足夠高的建議。

在Kerenidis和Prakash開展研究時，量子計算機似乎能夠以比經典計算機更快的速度解決一些示例問題。大部分示例問題都是專門的、旨在發揮量子計算機優勢的狹隘問題。Kerenidis和Prakash的研究結果令人興奮，因為該研究提出了一系列人們關心的實際問題，量子計算機在解決這些問題上的表現優于經典計算機。

“我認為，這是機器學習和大資料中的第一個範例，表明量子計算機可以解決一些我們用傳統計算機尚無法解決的問題。”現任巴黎計算機科學基礎研究所的計算機科學家Kerenidis說。

Kerenidis和Prakash證明了量子計算機能夠比任何已知算法更快地解決推薦問題，速度呈指數級增長。但他們沒能證明快速的經典算法是不存在的。是以，當Aaronson在2017年開始與Ewin Tang合作時，前者提出的問題就是，要證明在解決推薦問題上不存在快速的經典算法，進而确認Kerenidis和Prakash的量子加速是真實的。

“在我看來，這似乎是完成這個問題最重要的最後一步了。”Aaronson說。他當時認為并不存在快速的經典算法。

Ewin Tang将于今年秋天開始攻讀博士

圖檔來源：Vivian Abagiu, The University of Texasat Austin

傳統算法運算速度比肩量子計算，推翻權威學者的結論

Tang于2017年秋天開始這項研究，他打算将推薦問題作為一篇進階論文的題目。在幾個月的時間裡，他一直試圖證明快速的經典算法是不存在的。但随着時間的推移，他開始認為，可能确實存在這樣的算法。

“我開始相信确實存在一種快速的經典算法，但我無法向自己證明這一點，而且Scott似乎認為這樣的算法不存在，而且他是權威。”Tang說。

最後，随着論文的最後期限越來越近，Tang寫信給Aaronson，承認自己對這個問題的懷疑越來越深了：“Tang寫信給我說，實際上，'我認為存在一種快速的經典算法'。”Aaronson說。

在2018年的整個春天，Tang寫出了算法的結果，并與Aaronson一起理清算法證明中的一些步驟。 Tang發現的這一快速經典算法受到了Kerenidis和Prakash兩年前發現的快速量子算法的直接啟發。Tang表明，Kerenidis和Prakash在其算法中使用的量子采樣技術可以在經典環境中複制。與Kerenidis和Prakash的算法一樣，Tang的算法也是在多對數時間内運作的，也就是說計算時間是按照特征（如資料集中的使用者和産品的數量）的對數進行縮放的，并且比任何之前已知的經典算法的速度呈指數增長。

在算法完成後，Aaronson希望在公開發表之前确定算法是正确無誤的。“我仍然感到緊張，一旦在網上發表論文，如果算法出錯了，那麼他的職業生涯的第一篇重要論文的價值就會降低。”Aaronson說。

青出于藍，少年老成

Aaronson計劃于6月份參加于加州大學伯克利分校舉辦的量子計算研讨會。量子計算領域的許多重量級人物都将出席會議，其中就包括Kerenidis和Prakash。在官方會議結束後的幾天後，Aaronson邀請Tang來伯克利非正式介紹他的算法。

在6月18日和19日的上午，Tang做了兩次演講，并接受了觀衆的提問。等到四小時的演講結束時，在場的人達成了共識：Tang提出的經典算法似乎是正确的。然而，房間裡的許多人都沒有意識到演講者的年齡。“我當時并不知道他隻有18歲，從交流中完全看不出來。在我看來，他的演講非常成熟。”Kerenidis說。目前，這一算法在正式發表之前尚待正式的同行評議。

對于量子計算而言，Tang的發現似乎是一個挫折。但也許并非如此。這一發現消滅了量子計算中優勢最清晰範例之一。但與此同時，Tang的論文進一步證明了量子算法和經典算法研究之間存在富有成效的互相作用。

“Tang的發現推翻了Kerenidis和Prakash的量子加速神話，但在另一種意義上，這也是一次很大的改進，而且這種改進是在Kerenidis和Prakash研究的基礎上做出的。如果沒有他們的量子算法作為基礎，Tang不可能成功做出這個經典算法。”Aaronson說。

參考連結：

https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/

原文釋出時間為：2018-08-02

本文來自雲栖社群合作夥伴新智元，了解相關資訊可以關注“AI_era”。

原文連結：

18歲天才華裔少年用一個經典算法，推翻量子加速神話！