安妮 夏乙 發自 凹非寺

量子位 出品

量子計算能為機器學習大幅加速？

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

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

“這曾是量子加速的最強例證之一，現在它已經不複存在。”

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

他今年，只有18歲。

△18歲的華裔少年Ewin Tang

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的高分時，學校決定給他提前入學的機會。

△高數掛住了我們，唯獨給Ewin開掛

當大部分同齡孩子還在小學數學習題中無法自拔時，少年已經師從著名量子計算專家阿倫森教授，鑽研起高數和量子資訊學，還受到了“unusually talented”的讚譽。

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

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

據2012年UT阿靈頓的古老報導中記載，Ewin的父親為UT阿靈頓的生物工程系教授唐力平（Liping Tang），成長於台灣，目前主要的研究方向為幹細胞、組織工程、納米技術、生物相容性等。

△Ewin父親、華裔教授唐力平

少年學習大學課程時，周一三五的部分時間在私立學校上課，參加足球、籃球、越野和科學奧林匹克競賽等活動；另外一部分時間，他回去UTA上課。周二和周四，Ewin則到他父親的納米技術實驗室兼職工作。此外，少年還在學習中文、鋼琴和二胡。

△12歲的Ewin Tang

神童的培養過程也有困擾，隻不過唐力平最擔心的不是兒子的學習，而是他的社交生活。“在學術上他表現很好，但我們希望他留在學校和他這個年齡的孩子一起生活，讓身邊的朋友與他同齡。”唐力平說。

真是甜蜜的苦惱呢~

圍觀群眾驚呼

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

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

一些“寶爸”“寶媽”的關注點自然在“天才少年養成記”上。ID為nsxwolf的網友評論Ewin跳過了四到六年級讓他印象深刻，疑惑這是Ewin的天賦還是父母的教育方法特別：

我應該對自己的孩子做些什麽嗎？孩子多大時才知道具有這種潛力。

好尖銳！也好讓人want to know！

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

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

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

為什麽大家探討的重點是Ewin的年齡還不是他的技能。當然他很年輕，但這也與所提出的實際工作無關。

當然，也有一些評論穩中帶皮。ID為greg7mdp的hacker news網友感慨Ewin“生不逢時”：“如果他幾年前發現了這個算法，可能已經贏得了100萬美元的Netflix大獎。”還給出了當年Netflix基於推薦算法舉辦影片評級大賽的地址~

One More Thing

好像是冥冥中注定的某種巧合。

在歷史上，也有一位18歲的準博士生，他是Ewin的知名華人校友。18歲那年，一封華盛頓大學的博士offer發到了他的手中；23歲，他博士畢業。

那個人是張亞勤。

—完—