新智元報導
來源：quantamagazine
編輯：大明
【新智元導讀】一位年僅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/
新智元AI WORLD 2018大會【早鳥票】開售！
新智元將於9月20日在北京國家會議中心舉辦AI WORLD 2018 大會，邀請機器學習教父、CMU教授 Tom Mitchell，邁克思·泰格馬克，周志華，陶大程，陳怡然等AI領袖一起關注機器智能與人類命運。
大會官網：
即日起到8月19日，新智元限量發售若干早鳥票，與全球AI領袖近距離交流，見證全球人工智慧產業跨越發展。
活動行購票連結：
http://www.huodongxing.com/event/6449053775000
活動行購票二維碼：