【我們為什麼挑選這篇文章】生活中各樣 app 都在使用推薦演算法,餵給我們想要的內容,但傳統上我們認為,一般傳統電腦能做到的推薦演算法,沒辦法超過量子電腦的速度。

然而這樣的印象被一位 18 歲的少年打破,父親來自台灣,培養他從小接觸科學,雖然是典型的神童人物設定,不過近期他發表的研究,影響重大,可能未來在他的研究基礎上,將掀起一波演算法的革新。(責任編輯:鄧天心)

量子電腦能為機器學習大幅加速?

不好意思,這件事的最佳證據:量子推薦系統,已被華盛頓大學準博士生Ewin Tang「殺死」。

他在量子電腦的啟發下,開發了一種在傳統電腦上運行的推薦演算法,與以前的推薦演算法相比能實現指數級加速,媲美量子推薦演算法。

「這曾是量子加速的最強例證之一,現在它已經不復存在。」

打破量子電腦優越性的Ewin,秋天即將去華盛頓大學讀博的Ewin,不是你的同齡人。

他今年,只有18歲。

17 歲的艱鉅作業

2017年春天,17 歲的少年Ewin正在德克薩斯大學奧斯汀讀大三。

他選了一門深奧的課程:量子信息。

這門課的老師,是德克薩斯大學奧斯汀分校量子信息中心主任斯科特·阿倫森(Scott Aaronson)教授。

阿倫森老師曾在MIT任教9年,2016年秋天加入UT奧斯汀。這位37歲的教授,在學術界稱得上青年才俊。

阿倫森老師

他看著少年,不知道是不是看見了自己17歲的影子,覺得這位少年天賦異禀,決定帶著他做點研究。

於是,一堆課題擺在了少年面前。最後,他不大情願地選了推薦系統算法。

而「不情願」的理由,與14歲上大學、「天賦異禀」的學霸人物設定很不搭。

少年接受Quanta Magazine採訪時說:猶豫,是因為我看起來感覺它好像很難,但這已經是他給我的課題裡最簡單的了。

推薦演算法,可能是機器學習技術應用中群眾基礎最好的一個。它早已經被各種App大規模應用,每天為幾億人推薦著新聞、商品、歌曲。

如此司空見慣,為什麼學霸少年會覺得難?

量子推薦演算法,權威不再?

課是量子訊息,導師是量子訊息中心主任,這個推薦算法課題,研究的自然是它和量子計算的交叉。

推薦演算法之於量子訊息,約等於燈泡之於電力。

一直以來,量子電腦最深入人心的特徵是計算能力強悍,而它究竟能用來幹什麼,就超出了群眾的認知範疇。

大家都說,它擅長分解龐大的數字,對加密解密有著巨大的作用。

但如果僅僅是密碼學,與傳統電腦能完成的任務相比就未免太狹窄了。更何況,要真正用量子計算攻克密碼,還要等個10年左右。

當下真能證明量子電腦優越性的問題,寥寥無幾而且局限在非常狹窄的細分任務上。

直到2016年,一篇論文:Quantum Recommendation Systems,也就是量子推薦系統,終於在一個大眾關心的問題上,證明了量子電腦的優越性。
論文地址:https://arxiv.org/abs/1603.08675

論文作者,是法國科學研究中心(CNRS)高級研究員Iordanis Kerenidis和南洋理工大學的Anupam Prakash。

阿倫森教授把他們的算法稱為KP算法,還說它堪稱量子電腦能為真實世界中的機器學習提供指數級加速的最強證據之一。

推薦系​​統就像一個用戶×產品構成的偏好矩陣。對於傳統的演算法來說,矩陣中所有的偏好信息要用到,而KP算法,用一種叫做「量子相位估算」的方法從中抽樣。與眾多傳統演算法相比,速度呈「指數級提升」。

Kerenidis說,據他所知這是第一次有機器學習和大數據領域的例子,證明了量子電腦可以完成傳統電腦上不可能的任務。

少年要研究的東西,就和這個KP算法有關。

從不可能到可能

2017年秋天,Ewin的研究作為本科畢業論文開工了。

一開始,少年和阿倫森老師一樣,一心相信傳統推薦演算法不可能達到量子推薦系統的速度。

可是,他的想法逐漸在改變。

論文截稿時間已近,他對老師說:我認為快速的傳統算法,是存在的,KP算法中的量子相位估計,能找到替代品。

有想法還不夠。少年證明了可以用傳統算法來替代量子相位估計,從一個用戶偏好矩陣中隨機採樣,形成一個小矩陣。

在傳統的電腦上,同樣可以做出像KP算法一樣快的推薦系統。

和兩位前輩一樣,少年的算法的運行時間也是用戶和產品的多重對數。也就是說,計算時間隨著特徵的對數而縮放。在推薦系統中,「特徵」就是用戶和等著推薦的產品。

經過自己反復計算,阿倫森老師反複檢查,兩人反復討論,他的最終成果出爐了。這篇35頁的論文題為A quantum-inspired classical algorithm for recommendation systems,一個量子計算啟發的推薦系統傳統算法,前不久在arXiv上公開了。

論文地址:https://arxiv.org/abs/1807.04271

少年宣告,與傳統電腦上的算法,也就是他自己剛剛開發的這個相比,KP演算法實際上並不能帶來指數級加速。

量子加速的最強證據之一,被推翻了。

一人單挑一屋子量子電腦大師

阿倫森老師參加加州大學伯克利分校的量子電腦workshop時,還帶上了Ewin,讓他根據這篇論文做了非正式的演講。眾多量子電腦大牛都在場,包括打造了量子推薦系統的Kerenidis和Prakash。

這就像是一場高規格的論文答辯會。少年做了兩場演講,和諸位觀眾唇槍舌劍問答4小時。最終,大家終於達成共識:算法正確,「答辯」通過。

QuantaMagazine還說,這篇論文後來還正式投遞到了某期刊或者會議,正在進行同行評審,等待發表。

阿倫森老師在自己的博客上,把這篇論文稱為「a striking new result」,驚人的新成果。

他說,唐同學殺死了(KP算法的)量子加速。

但是,無論是阿倫森,還是少年,都不想給量子電腦潑冷水。少年的論文標題恰恰強調了是透過「量子電腦啟發的」,阿倫森老師也說,如果沒有KP的量子演算法,也不會有唐同學的這項成果。

18歲的準博士生

驕人的研究背後的作者Ewin Tang,是今年秋天即將入學華盛頓大學的博士生。

沒錯,18歲的博士生。

在我們剛剛高中畢業暑期狂歡的時候,大神已經準備下個月的讀博項目了?

是的,而且是一路開掛——

根據德克薩斯大學阿靈頓分校(UT阿靈頓)的校報報導,小學階段,少年一路連跳。 12歲時,Ewin實現了「質的跳躍」,成為校園裡最年輕的學生,主修數學和電腦科學了。

這還不是他第一次接觸大學課程,自10歲時開始第一次上大學課程以來,他已經接觸了微積分和微分方程在內的高數知識,且這些課程的GPA均為4.0。還是10歲,當少年的SAT考試拿到1920的高分時,學校決定給他提前入學的機會。
當大部分同齡孩子還在小學數學習題中無法自拔時,少年已經師從著名量子電腦專家阿倫森教授,鑽研起高數和量子信息學,還受到了「unusually talented」的讚譽。

14歲的Ewin,在大學期間,還發表了三篇……論文。

神童的父母通常都很厲害?

是誰啟發了幼年的Ewin學大學課程的?秉持著「神童的父母多半也很厲害」的傳統信仰,量子位找尋到了少年的家庭訊息。果然——

據2012年UT阿靈頓的古老報導中記載,Ewin的父親為UT阿靈頓的生物工程系教授唐力平(Liping Tang),成長於台灣,目前主要的研究方向為乾細胞、組織工程、奈米技術、生物相容性等。
少年學習大學課程時,週一三五的部分時間在私立學校上課,參加足球、籃球、越野和科學奧林匹克競賽等活動;另外一部分時間,他回去UTA上課。週二和周四,Ewin則到他父親的納米技術實驗室兼職工作。此外,少年還在學習中文、鋼琴和二胡。
神童的培養過程也有困擾,只不過唐力平最擔心的不是兒子的學習,而是他的社交生活。 「在學術上他表現很好,但我們希望他留在學校和他這個年齡的孩子一起生活,讓身邊的朋友與他同齡。」唐力平說。

真是甜蜜的苦惱呢~

圍觀群眾驚呼

無論是在動漫還是電影裡,「天才少年」總是人群中最受關注的那一個。現實中當然也不例外,Ewin已經引起了各大科技學術論壇中網友的關注,一天之中HackerNews上就堆積了200多條評論。

有唇槍舌劍的學術探討,更多人對著少年在感慨。

一些「寶爸」「寶媽」的關注點自然在「天才少年養成記」上。

ID為nsxwolf的網友評論Ewin跳過了四到六年級讓他印象深刻,疑惑這是Ewin的天賦還是父母的教育方法特別:

我應該對自己的孩子做些什麼嗎?孩子多大時才知道具有這種潛力。
好尖銳!也好讓人want to know!

問題的跟評者各抒己見,有認為孩子擁有無憂無慮的童年和在同齡人中表現最佳往往不可兼得,順氣自然開心快樂就好。

也有網友覺得父母無需為孩子找方向,興趣必須來自孩子,父母只需要提供適當幫助就好,強求不來。

有的網友認為,大家的評論和討論太基於Ewin的年齡,甚至有些放錯了重點:

為什麼大家探討的重點是Ewin的年齡還不是他的技能。當然他很年輕,但這也與所提出的實際工作無關。
當然,也有一些評論穩中帶皮。 ID為greg7mdp的hacker news網友感慨Ewin「生不逢時」:如果他幾年前發現了這個算法,可能已經贏得了100萬美元的Netflix大獎。還給出了當年Netflix基於推薦算法舉辦影片評級大賽的地址~

__

(本文經合作夥伴 量子位 授權轉載,並同意 TechOrange 編寫導讀與修訂標題,原文標題為 〈杀死量子推荐算法:18岁华裔少年推翻量子加速最强证据〉,圖片來源:YouTube

延伸閱讀

《經濟學人》專文探討:「為什麼 Python 是世上最屌的程式語言?」

給工程師的投資入門手冊:Python、R 哪個才是你最適合用來理財的程式語言?

從太空科技到人工智慧,量子電腦的應用會全面顛覆現有科技!