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

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

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

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

天才少年Ewin Tang

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

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

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

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

“我有點(diǎn)猶豫，因?yàn)橥扑]問題看起來很難，但已經(jīng)是他給我的問題中最簡單的了，”Tang說。

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

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

Netflix用機(jī)器學(xué)習(xí)為你推送專屬電視劇封面

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

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

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

當(dāng)時(shí)，量子計(jì)算機(jī)對(duì)推薦問題的貢獻(xiàn)非常少，大部分都是解決的很具體的問題。而二人的成果之所以令人激動(dòng)是因?yàn)樗麄冊(cè)诂F(xiàn)實(shí)人們關(guān)心的問題上證明量子計(jì)算機(jī)能做得比傳統(tǒng)方法更好。

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

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

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

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

Tang的論文發(fā)表前，Aaronson十分謹(jǐn)慎，因?yàn)橐坏┏霈F(xiàn)差錯(cuò)，Tang的第一篇大paper會(huì)很影響他的事業(yè)。

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

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