18歲華裔少年打破量子計算神話 他的演算法更快？(圖)

量子計算機（圖片來源：Adobe stock）

【看中國2018年8月13日訊】現年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歲，我整場講座都沒聽出來，他演講的時候顯得很成熟。」目前，只要等到同行評議做完，這項演算法就可以正式發表了。

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

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