上個月初，發(fā)表在arXiv上的一篇論文引起了人們的興趣，作者是一位18歲的青少年——Ewin Tang。這位來自美國得克薩斯州的少年在論文中證明，用普通計算機就能解決重要的計算問題，并有可能達到和量子計算機相當?shù)男阅堋?/span>

首先讓我們看看這篇論文的摘要：

這項應用放在實際中，可以用作我們熟知的推薦系統(tǒng)。各大電商公司和視頻網(wǎng)站經(jīng)常向用戶推薦他們可能感興趣的產(chǎn)品。計算機科學家們將這一任務看作是這類問題的典型案例，如果在量子計算機上運行的會更快。所以很多人認為量子計算機是未來計算力的重要象征。但現(xiàn)在，Tang的發(fā)現(xiàn)讓這一說法受到了質(zhì)疑。

Tang說：“這是量子加速的最佳案例?！盩ang今年春季畢業(yè)于德克薩斯州大學奧斯汀分校，并在秋季將成為華盛頓大學的博士生。

天才少年Ewin Tang

據(jù)2012年的一份報道，Ewin在12歲的時候就已經(jīng)在德克薩斯州大學阿靈頓分校就就讀，他在10歲時就開始接收大學課程教育，并完成了20個小時的課程，包括微積分和微分方程，GPA達到4.0，是當時年紀最小的學生。

在私立學校學習完全部K-12數(shù)學課程后，Ewin就開始了大學知識學習，他在10歲時SAT成績就達到了1920分。除了學習大學課程，Ewin在課余時間還會泡在他父親的實驗室里，他的父親Liping Tang是一名生物工程教授。

新算法的發(fā)現(xiàn)

2014年，Tang連跳兩級進入了UT Austin的數(shù)學和計算機科學專業(yè)就讀。2017年春季，他接收了著名量子計算研究者Scot Aaronson教授的量子信息課程，Aaronson認為Tang天賦異稟，在研究上給予了他很多幫助，同時還讓他選擇想要研究的問題，包括推薦問題。

“我有點猶豫，因為推薦問題看起來很難，但已經(jīng)是他給我的問題中最簡單的了，”Tang說。

推薦問題的核心是為用戶推薦他們可能喜歡的產(chǎn)品。關(guān)于這一研究領(lǐng)域，論智此前也做過相應報道：

2018年推薦系統(tǒng)入門指南

Netflix用機器學習為你推送專屬電視劇封面

Spotify揭秘：如何用算法實現(xiàn)歌曲精準推送

你可以想象數(shù)據(jù)在一個巨大的網(wǎng)格或者矩陣中，橫排代表所有電影，豎排代表觀眾，交叉點的值用數(shù)字表示觀眾喜歡電影的成都。一個好的算法能快速而準確地識別電影和用戶之間的相似性，從而生成推薦，并填補矩陣中的空白。

2016年，計算機科學家Iordanis Kerenidis和Anupam Prakash發(fā)表了一種量子算法，可以比任何經(jīng)典算法都快速地解決推薦問題。他們將問題簡化：與此前只為了填滿矩陣并推薦最佳產(chǎn)品不同，他們開發(fā)了一種對用戶進行分類的方法——他們喜歡大片還是獨立小眾的電影？然后通過對現(xiàn)有數(shù)據(jù)采樣生成最佳推薦結(jié)果。

當時，量子計算機對推薦問題的貢獻非常少，大部分都是解決的很具體的問題。而二人的成果之所以令人激動是因為他們在現(xiàn)實人們關(guān)心的問題上證明量子計算機能做得比傳統(tǒng)方法更好。

Kerenidis表示：“在我看來，這是機器學習和大數(shù)據(jù)領(lǐng)域第一件只有量子計算機能完成的任務?！盞erenidis和Prakash證明了，量子計算機可以比任何經(jīng)典算法都能更快地完成推薦算法，但是他們并沒有證明這種快速的經(jīng)典算法不存在。所以2017年，當Aaronson和Tang共同研究時，他提出了這一想法，證明了確實沒有這樣一種經(jīng)典推薦算法，所以確認了Kerenidis和Prakash提出的量子加速器是真實的。

2017年秋季，Tang開始他的研究，并將推薦問題作為它的論文主題。在幾個月的時間里，Tang一直在努力證明上述那樣的快速經(jīng)典算法是不可能存在的，但與此同時，他開始思考也許確實存在這樣一種算法呢？

“我有些猶豫了，但是Scott是權(quán)威?！盩ang說道。但是隨著論文deadline臨近，Tang還是給Aaronson寫了封郵件：“我認為存在這樣一種快速的經(jīng)典算法。”

接著，Tang和Aaronson開始努力證明這一存在，Tang發(fā)現(xiàn)的這種經(jīng)典算法是直接收到了Kerenidis和Prakash二人提出的快速量子算法，Tang證明他們在算法中所用到的量子采樣技術(shù)可以復制到經(jīng)典設(shè)置中。和Kerenidis和Prakash二人的算法類似，Tang的算法也是多對數(shù)規(guī)模，也就是說計算時間與特征的對數(shù)成比例關(guān)系（例如數(shù)據(jù)集中的產(chǎn)品和用戶數(shù)量），同時這一算法比此前所知的經(jīng)典算法都快。

Tang的論文發(fā)表前，Aaronson十分謹慎，因為一旦出現(xiàn)差錯，Tang的第一篇大paper會很影響他的事業(yè)。

六月，Aaronson在UC Berkeley舉辦了一場量子計算研討會，并邀請了Kerenidis和Prakash。會上，Tang對自己的發(fā)現(xiàn)做了展示，很多人對這一結(jié)果表示認同，同時，與會者都沒有意識到這位研究者如此年輕。

Aaronson表示：“Tang推翻了量子加速的成果，但是從另一個角度來說，Tang也為這一領(lǐng)域做出了巨大的貢獻。如果沒有前人對經(jīng)典算法和量子算法的研究，就不會有今天的成果?！?/p>