阿波羅新聞網新聞 > 科教 > 正文

18歲華裔少年打破量子計算「神話」?他的經典算法更快!

最近,一名得州(Texas)的華裔少年將量子計算“拉下神壇”。現年18歲的埃文·唐(Ewin Tang)7月初公布在 arXiv上的一篇論文,使得經典計算機也能“媲美”量子計算機,解決重要計算問題。

日常生活中,在 Amazon及 Netflix等服務商給客戶推薦可能喜歡的產品時,算法工程師會面臨一個“推薦問題”(recommendation problem)。計算機科學家認為如果將這種問題交給量子計算機,計算時間能夠大大縮短,並且彰顯出這種還未出世的計算機運算速度之快。但唐推翻了這一假設。

今年春季剛從德克薩斯大學奧斯汀分校(the University of Texas, Austin)畢業,準備秋季攻讀華盛頓大學(the University of Washington)博士的唐說道:“以前推薦問題能很直接地證明量子計算能夠提高運算速度,但現在不再是這樣了。”

少年天才

2014年,14歲的唐跳級進入德克薩斯大學奧斯汀分校學習數學和計算機科學。2017年春季,他選了量子計算領域專家斯科特·阿倫森(Scott Aaronson)的量子信息課。阿倫森覺得唐很有天分,主動擔任了唐的獨立研究項目的指導教師:他給唐提供了一大堆研究備選題目,唐勉勉強強地選了其中的推薦問題。

唐表示:“我當時很猶豫,攻克推薦問題在我看來困難重重,可這已經是備選課題里最簡單的一個了。”

推薦問題的初衷,是為用戶推薦可能感興趣的產品。就拿 Netflix來說,它記載了你看過的電影的信息,記載了它數百萬用戶看過的電影的信息。根據這些信息,如何為你做出影視推薦?

你可以把這些數據想成是放在一個超大的網格(即矩陣)中,網格上方是電影信息,下方是看過這些電影的用戶,網格節點的值則表示用戶對每部電影的喜愛程度。優秀的算法可以快速、精準識別用戶與電影間的匹配度來填充空格,進而生成推薦

量子算法

2016年,計算機科學家約丹尼斯·克里尼迪斯(IordanisKerenidis)和阿努帕姆·普拉卡什(Anupam Prakash)提出了一種量子算法,該算法解決推薦問題的速度比任何已知經典算法都快。這種量子算法計算速度的提高,得益於他們對問題的簡化:最佳推薦不再需要用填滿整個矩陣的方式來獲得——可以先將用戶分成幾小類(比如用戶是喜歡大片還是小眾電影),再從現有數據中抽樣,生成合適的推薦。

在克里尼迪斯和普拉卡什提出上述算法之前,能體現出量子計算機優越性的例子並不多。而且大多是為體現量子計算機優越性而專門設計的,比如“相關(correlation)問題”(判斷兩個隨機數字序列生成器生成的兩組序列是完全獨立的,還是以某種隱藏的形式相關聯的)。但克里尼迪斯與普拉卡什提出的是一個現實生活中的問題,與之前的專業問題相比,量子計算機的優越性更能引起大眾的關心。

巴黎計算機科學基礎研究所(the Research Institute on the Foundations of Computer Science in Paris)的計算機科學家克里尼迪斯說:“我認為,這是在機器學習和大數據領域,量子計算機能解決,而經典計算機不能的第一批案例。”

克里尼迪斯和普拉卡什已證明,量子計算機解決推薦問題的速度,比任何已知算法都要快,但這並不能證明計算速度更快的經典算法一定不存在。所以2017年阿倫森給唐提出的研究課題是:證明任何經典推薦算法的計算速度都沒有量子推薦算法快,克里尼迪斯與普拉卡什的量子算法確實能提高計算速度

阿倫森當時堅信不存在速度更快的經典算法:“在我看來,這是完成整個故事很重要的一環。”

經典算法能更快?

2017年唐開始了這項研究,打算將推薦問題作為自己畢業論文的課題。開始的幾個月,唐都在努力證明更快的經典算法不存在。但隨着研究的深入,唐不禁猜測,這樣的算法沒準是存在的

唐表示:“我越來越覺得存在這樣一個速度更快的經典算法,但我對自己的想法很懷疑,畢竟斯科特堅信不存在這樣的算法,而他更權威。”

隨着畢業論文截稿日期的臨近,唐終於給阿倫森寫信承認了自己的疑問:“唐寫道,事實上‘我認為這樣的算法存在’。”

2017年春,唐寫出了這個經典算法,並在阿倫森的指導下完善了其中的某些步驟。受兩年前克里尼迪斯與普拉卡什算法的啟發,唐發現量子算法中的量子抽樣思想可以直接應用到經典算法中,進而完成了自己的算法。與量子算法相同,唐的算法也在多重對數時間內運行,即計算時間與特徵量(如數據集中用戶量、產品量等)的對數相關,運算速度與以往的經典算法相比有指數級提升。

唐寫完算法之後,阿倫森希望能在發表之前確認算法的正確性:“我很是緊張,一旦唐公布在網上的論文存在錯誤,他的學術生涯會受到很大影響。”

阿倫森6月參加了加州大學伯克利分校(the University of California, Berkeley)的量子計算研討會。包括克里尼迪斯、普拉卡什等在內的多名量子計算領域專家都將出席該會議。阿倫森打算在正式會議結束後,邀請唐到伯克利講講他的經典推薦算法。

唐分別在6月18日和19日上午舉辦了兩場講座,回答了聽眾的提問。在長達四小時的講座結束後,大家達成了共識:唐的經典算法應該是對的。然而許多在場聽眾都沒意識到,這位看似老成的演講者年紀非常小。克里尼迪斯描述道:“真不敢相信唐只有18歲,我整場講座都沒聽出來,他演講的時候顯得很成熟。”目前,只要等到同行評議做完,這項算法就可以正式發表了。

唐的算法給了量子計算一記重拳?可能是也可能不是。唐推翻了能表明量子計算優越性的一個最清晰、最直白的例子;但同時,唐的論文也能很好地證明,量子算法與經典算法之間是相互影響、相輔相成的。

阿倫森評價:“唐扼殺了(克里尼迪斯與普拉卡什的)量子計算優越性,但從另一個角度來看,正是他們的算法孕育出了唐的新算法。沒有他們的量子算法,就不會有今天的經典算法。”

阿波羅網責任編輯:時方 來源:科研圈 轉載請註明作者、出處並保持完整。

科教熱門

相關新聞

➕ 更多同類相關新聞