上個月初，發表在arXiv上的一篇論文引起了人們的興趣，作者是一位18歲的青少年——Ewin Tang。這位來自美國德克薩斯州的少年在論文中證明，用普通計算機就能解決重要的計算問題，並有可能達到和量子計算機相當的性能。
首先讓我們看看這篇論文的摘要：
這項應用放在實際中，可以用作我們熟知的推薦系統。各大電商公司和視頻網站經常向用戶推薦他們可能感興趣的產品。計算機科學家們將這一任務看作是這類問題的典型案例，如果在量子計算機上運行的會更快。所以很多人認為量子計算機是未來計算力的重要象徵。但現在，Tang的發現讓這一說法受到了質疑。
Tang說：「這是量子加速的最佳案例。」Tang今年春季畢業於德克薩斯州大學奧斯汀分校，並在秋季將成為華盛頓大學的博士生。
據2012年的一份報導，Ewin在12歲的時候就已經在德克薩斯州大學阿靈頓分校就就讀，他在10歲時就開始接收大學課程教育，並完成了20個小時的課程，包括微積分和微分方程，GPA達到4.0，是當時年紀最小的學生。
在私立學校學習完全部K-12數學課程後，Ewin就開始了大學知識學習，他在10歲時SAT成績就達到了1920分。除了學習大學課程，Ewin在課餘時間還會泡在他父親的實驗室裡，他的父親Liping Tang是一名生物工程教授。
2014年，Tang連跳兩級進入了UT Austin的數學和計算機科學專業就讀。2017年春季，他接收了著名量子計算研究者Scot Aaronson教授的量子信息課程，Aaronson認為Tang天賦異稟，在研究上給予了他很多幫助，同時還讓他選擇想要研究的問題，包括推薦問題。
「我有點猶豫，因為推薦問題看起來很難，但已經是他給我的問題中最簡單的了，」Tang說。
推薦問題的核心是為用戶推薦他們可能喜歡的產品。關於這一研究領域，論智此前也做過相應報導：
你可以想像數據在一個巨大的網格或者矩陣中，橫排代表所有電影，豎排代表觀眾，交叉點的值用數字表示觀眾喜歡電影的成都。一個好的算法能快速而準確地識別電影和用戶之間的相似性，從而生成推薦，並填補矩陣中的空白。
2016年，計算機科學家Iordanis Kerenidis和Anupam Prakash發表了一種量子算法，可以比任何經典算法都快速地解決推薦問題。他們將問題簡化：與此前只為了填滿矩陣並推薦最佳產品不同，他們開發了一種對用戶進行分類的方法——他們喜歡大片還是獨立小眾的電影？然後通過對現有數據採樣生成最佳推薦結果。
當時，量子計算機對推薦問題的貢獻非常少，大部分都是解決的很具體的問題。而二人的成果之所以令人激動是因為他們在現實人們關心的問題上證明量子計算機能做得比傳統方法更好。
Kerenidis表示：「在我看來，這是機器學習和大數據領域第一件只有量子計算機能完成的任務。」Kerenidis和Prakash證明了，量子計算機可以比任何經典算法都能更快地完成推薦算法，但是他們並沒有證明這種快速的經典算法不存在。所以2017年，當Aaronson和Tang共同研究時，他提出了這一想法，證明了確實沒有這樣一種經典推薦算法，所以確認了Kerenidis和Prakash提出的量子加速器是真實的。
2017年秋季，Tang開始他的研究，並將推薦問題作為它的論文主題。在幾個月的時間裡，Tang一直在努力證明上述那樣的快速經典算法是不可能存在的，但與此同時，他開始思考也許確實存在這樣一種算法呢？
「我有些猶豫了，但是Scott是權威。」Tang說道。但是隨著論文deadline臨近，Tang還是給Aaronson寫了封郵件：「我認為存在這樣一種快速的經典算法。」
接著，Tang和Aaronson開始努力證明這一存在，Tang發現的這種經典算法是直接收到了Kerenidis和Prakash二人提出的快速量子算法，Tang證明他們在算法中所用到的量子採樣技術可以複製到經典設置中。和Kerenidis和Prakash二人的算法類似，Tang的算法也是多對數規模，也就是說計算時間與特徵的對數成比例關係（例如數據集中的產品和用戶數量），同時這一算法比此前所知的經典算法都快。
Tang的論文發表前，Aaronson十分謹慎，因為一旦出現差錯，Tang的第一篇大paper會很影響他的事業。
六月，Aaronson在UC Berkeley舉辦了一場量子計算研討會，並邀請了Kerenidis和Prakash。會上，Tang對自己的發現做了展示，很多人對這一結果表示認同，同時，與會者都沒有意識到這位研究者如此年輕。
Aaronson表示：「Tang推翻了量子加速的成果，但是從另一個角度來說，Tang也為這一領域做出了巨大的貢獻。如果沒有前人對經典算法和量子算法的研究，就不會有今天的成果。」
論文地址：arxiv.org/abs/1807.04271
原文地址：www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/