原標(biāo)題：18歲天才華裔少年用一個(gè)經(jīng)典算法，推翻量子加速神話！
來源：quantamagazine
編輯：大明
【新智元導(dǎo)讀】一位年僅18歲的華裔少年提出了一種傳統(tǒng)計(jì)算機(jī)AI算法，其運(yùn)算速度可以與量子計(jì)算比肩，相對之前的傳統(tǒng)算法實(shí)現(xiàn)了運(yùn)算速度的指數(shù)級增長。這一發(fā)現(xiàn)不僅推翻了兩位量子計(jì)算重量級人物的量子加速神話，而且證明了量子算法和經(jīng)典算法研究之間存在富有成效的相互作用。
在本月早些時(shí)候在網(wǎng)上發(fā)表的一篇論文中，18歲的Ewin Tang證明用普通計(jì)算機(jī)可以解決一個(gè)重要的計(jì)算問題，其性能表現(xiàn)可能與量子計(jì)算機(jī)相當(dāng)。
以最實(shí)際的問題“推薦問題”為例，這個(gè)問題中就涉及亞馬遜和Netflix等服務(wù)是怎樣確定用戶想要嘗試體驗(yàn)?zāi)男┊a(chǎn)品的。計(jì)算機(jī)科學(xué)家認(rèn)為，這個(gè)問題是量子計(jì)算應(yīng)用的典型范例之一，和傳統(tǒng)計(jì)算相比，量子計(jì)算解決這個(gè)問題速度可能呈指數(shù)級增長，這讓該問題成為對未來量子計(jì)算性能的重要驗(yàn)證。現(xiàn)在Ewin Tang已經(jīng)證明，事實(shí)不盡如此。
14歲上大學(xué)，18歲讀博士，挑戰(zhàn)量子計(jì)算領(lǐng)域示范問題
Ewin Tang今年春季畢業(yè)于德克薩斯大學(xué)奧斯汀分校，并將于今年秋季開始在華盛頓大學(xué)攻讀博士學(xué)位。“這曾經(jīng)是量子加速計(jì)算的最明確的范例之一，不過現(xiàn)在已經(jīng)不是了。”Ewin Tang說。
Ewin Tang在小學(xué)曾從四年級跳級至六年級，2014年，年僅14歲的他進(jìn)入德克薩斯大學(xué)奧斯汀分校就讀，主修數(shù)學(xué)和計(jì)算機(jī)科學(xué)。2017年春，他選了量子計(jì)算方面的著名研究員Scott Aaronson講授的關(guān)于量子信息的課程。Aaronson認(rèn)為他是一位非常有才華的學(xué)生，并且自稱是一個(gè)獨(dú)立研究項(xiàng)目的顧問。Aaronson給了他一些可供選擇的問題，其中就包括推薦問題。Tang有點(diǎn)不情愿地選擇了這個(gè)問題。
“我當(dāng)時(shí)曾一度猶豫不決，因?yàn)檫@似乎是一個(gè)難題，但這是他給我的最簡單的問題了。”Ewin Tang說。
這類“推薦問題”旨在為用戶喜歡的產(chǎn)品提供建議。以Netflix為例，它知道你看過哪部電影，也了解其他數(shù)百萬用戶所觀看的內(nèi)容。那么根據(jù)這些信息，你接下來可能想要觀看什么電影？
你可以將這些數(shù)據(jù)視為在一張巨大網(wǎng)格或矩陣中排列，上方列出的是電影，側(cè)方列出的是用戶，而網(wǎng)絡(luò)中各點(diǎn)的值用于量化每個(gè)用戶對每部電影的喜愛程度。一個(gè)好的算法可以快速準(zhǔn)確地識別電影和用戶之間的相似度，并填充矩陣中的空白，為用戶推薦喜歡的電影。
2016年，計(jì)算機(jī)科學(xué)家Iordanis Kerenidis和Anupam Prakash發(fā)布了一種量子算法，能夠比任何已知經(jīng)典算法更加快速地解決推薦問題。他們通過對問題模型的簡化來實(shí)現(xiàn)這一量子加速過程：不用填滿整個(gè)矩陣并確定唯一最佳推薦結(jié)果，而是開發(fā)一種將用戶進(jìn)行分類的方式：比如用戶是喜歡商業(yè)大片還是獨(dú)立電影？并對現(xiàn)有數(shù)據(jù)進(jìn)行抽樣，以生成質(zhì)量足夠高的建議。
在Kerenidis和Prakash開展研究時(shí)，量子計(jì)算機(jī)似乎能夠以比經(jīng)典計(jì)算機(jī)更快的速度解決一些示例問題。大部分示例問題都是專門的、旨在發(fā)揮量子計(jì)算機(jī)優(yōu)勢的狹隘問題。Kerenidis和Prakash的研究結(jié)果令人興奮，因?yàn)樵撗芯刻岢隽艘幌盗腥藗冴P(guān)心的實(shí)際問題，量子計(jì)算機(jī)在解決這些問題上的表現(xiàn)優(yōu)于經(jīng)典計(jì)算機(jī)。
“我認(rèn)為，這是機(jī)器學(xué)習(xí)和大數(shù)據(jù)中的第一個(gè)范例，表明量子計(jì)算機(jī)可以解決一些我們用傳統(tǒng)計(jì)算機(jī)尚無法解決的問題。”現(xiàn)任巴黎計(jì)算機(jī)科學(xué)基礎(chǔ)研究所的計(jì)算機(jī)科學(xué)家Kerenidis說。
Kerenidis和Prakash證明了量子計(jì)算機(jī)能夠比任何已知算法更快地解決推薦問題，速度呈指數(shù)級增長。但他們沒能證明快速的經(jīng)典算法是不存在的。因此，當(dāng)Aaronson在2017年開始與Ewin Tang合作時(shí)，前者提出的問題就是，要證明在解決推薦問題上不存在快速的經(jīng)典算法，從而確認(rèn)Kerenidis和Prakash的量子加速是真實(shí)的。
“在我看來，這似乎是完成這個(gè)問題最重要的最后一步了。”Aaronson說。他當(dāng)時(shí)認(rèn)為并不存在快速的經(jīng)典算法。
Ewin Tang將于今年秋天開始攻讀博士
圖片來源：Vivian Abagiu,The University of Texasat Austin
傳統(tǒng)算法運(yùn)算速度比肩量子計(jì)算，推翻權(quán)威學(xué)者的結(jié)論
Tang于2017年秋天開始這項(xiàng)研究，他打算將推薦問題作為一篇高級論文的題目。在幾個(gè)月的時(shí)間里，他一直試圖證明快速的經(jīng)典算法是不存在的。但隨著時(shí)間的推移，他開始認(rèn)為，可能確實(shí)存在這樣的算法。
“我開始相信確實(shí)存在一種快速的經(jīng)典算法，但我無法向自己證明這一點(diǎn)，而且Scott似乎認(rèn)為這樣的算法不存在，而且他是權(quán)威。”Tang說。
最后，隨著論文的最后期限越來越近，Tang寫信給Aaronson，承認(rèn)自己對這個(gè)問題的懷疑越來越深了：“Tang寫信給我說，實(shí)際上，'我認(rèn)為存在一種快速的經(jīng)典算法'。”Aaronson說。
在2018年的整個(gè)春天，Tang寫出了算法的結(jié)果，并與Aaronson一起理清算法證明中的一些步驟。Tang發(fā)現(xiàn)的這一快速經(jīng)典算法受到了Kerenidis和Prakash兩年前發(fā)現(xiàn)的快速量子算法的直接啟發(fā)。Tang表明，Kerenidis和Prakash在其算法中使用的量子采樣技術(shù)可以在經(jīng)典環(huán)境中復(fù)制。與Kerenidis和Prakash的算法一樣，Tang的算法也是在多對數(shù)時(shí)間內(nèi)運(yùn)行的，也就是說計(jì)算時(shí)間是按照特征（如數(shù)據(jù)集中的用戶和產(chǎn)品的數(shù)量）的對數(shù)進(jìn)行縮放的，并且比任何之前已知的經(jīng)典算法的速度呈指數(shù)增長。
在算法完成后，Aaronson希望在公開發(fā)表之前確定算法是正確無誤的。“我仍然感到緊張，一旦在網(wǎng)上發(fā)表論文，如果算法出錯(cuò)了，那么他的職業(yè)生涯的第一篇重要論文的價(jià)值就會降低。”Aaronson說。
青出于藍(lán)，少年老成
Aaronson計(jì)劃于6月份參加于加州大學(xué)伯克利分校舉辦的量子計(jì)算研討會。量子計(jì)算領(lǐng)域的許多重量級人物都將出席會議，其中就包括Kerenidis和Prakash。在官方會議結(jié)束后的幾天后，Aaronson邀請Tang來伯克利非正式介紹他的算法。
在6月18日和19日的上午，Tang做了兩次演講，并接受了觀眾的提問。等到四小時(shí)的演講結(jié)束時(shí)，在場的人達(dá)成了共識：Tang提出的經(jīng)典算法似乎是正確的。然而，房間里的許多人都沒有意識到演講者的年齡。“我當(dāng)時(shí)并不知道他只有18歲，從交流中完全看不出來。在我看來，他的演講非常成熟。”Kerenidis說。目前，這一算法在正式發(fā)表之前尚待正式的同行評議。
對于量子計(jì)算而言，Tang的發(fā)現(xiàn)似乎是一個(gè)挫折。但也許并非如此。這一發(fā)現(xiàn)消滅了量子計(jì)算中優(yōu)勢最清晰范例之一。但與此同時(shí)，Tang的論文進(jìn)一步證明了量子算法和經(jīng)典算法研究之間存在富有成效的相互作用。
“Tang的發(fā)現(xiàn)推翻了Kerenidis和Prakash的量子加速神話，但在另一種意義上，這也是一次很大的改進(jìn)，而且這種改進(jìn)是在Kerenidis和Prakash研究的基礎(chǔ)上做出的。如果沒有他們的量子算法作為基礎(chǔ)，Tang不可能成功做出這個(gè)經(jīng)典算法。”Aaronson說。
參考鏈接：
https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/
http://www.aiworld2018.com/
返回搜狐，查看更多
責(zé)任編輯：
