原標題：18歲天才華裔少年用一個經典算法，推翻量子加速神話！
來源：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/
http://www.aiworld2018.com/
返回搜狐，查看更多
責任編輯：
