圖片來源：ADragan/Quantamagazine

撰文 Kevin Hartnett

翻譯 賈曉璇

審校 魏瀟

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

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

今年春季剛從德克薩斯大學(xué)奧斯汀分校（the University of Texas, Austin）畢業(yè)，準(zhǔn)備秋季攻讀華盛頓大學(xué)（the University of Washington）博士的唐說道：“以前推薦問題能很直接地證明量子計算能夠提高運(yùn)算速度，但現(xiàn)在不再是這樣了?！?/span>

2014 年，14 歲的唐跳級進(jìn)入德克薩斯大學(xué)奧斯汀分校學(xué)習(xí)數(shù)學(xué)和計算機(jī)科學(xué)。2017 年春季，他選了量子計算領(lǐng)域?qū)＜?/span>斯科特·阿倫森（Scott Aaronson）的量子信息課。阿倫森覺得唐很有天分，主動擔(dān)任了唐的獨立研究項目的指導(dǎo)教師：他給唐提供了一大堆研究備選題目，唐勉勉強(qiáng)強(qiáng)地選了其中的推薦問題。

華裔少年埃文·唐。圖片來源：Flickr

唐表示：“我當(dāng)時很猶豫，攻克推薦問題在我看來困難重重，可這已經(jīng)是備選課題里最簡單的一個了?！?/span>

推薦問題的初衷，是為用戶推薦可能感興趣的產(chǎn)品。就拿 Netflix 來說，它記載了你看過的電影的信息，記載了它數(shù)百萬用戶看過的電影的信息。根據(jù)這些信息，如何為你做出影視推薦？

你可以把這些數(shù)據(jù)想成是放在一個超大的網(wǎng)格（即矩陣）中，網(wǎng)格上方是電影信息，下方是看過這些電影的用戶，網(wǎng)格節(jié)點的值則表示用戶對每部電影的喜愛程度。優(yōu)秀的算法可以快速、精準(zhǔn)識別用戶與電影間的匹配度來填充空格，進(jìn)而生成推薦。

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

在克里尼迪斯和普拉卡什提出上述算法之前，能體現(xiàn)出量子計算機(jī)優(yōu)越性的例子并不多。而且大多是為體現(xiàn)量子計算機(jī)優(yōu)越性而專門設(shè)計的，比如“關(guān)系（forrelation）問題”（判斷兩個隨機(jī)數(shù)字序列生成器生成的兩組序列是完全獨立的，還是以某種隱藏的形式相關(guān)聯(lián)的）。但克里尼迪斯與普拉卡什提出的是一個現(xiàn)實生活中的問題，與之前的專業(yè)問題相比，量子計算機(jī)的優(yōu)越性更能引起大眾的關(guān)心。

巴黎計算機(jī)科學(xué)基礎(chǔ)研究所（the Research Institute on the Foundations of Computer Science in Paris）的計算機(jī)科學(xué)家克里尼迪斯說：“我認(rèn)為，這是在機(jī)器學(xué)習(xí)和大數(shù)據(jù)領(lǐng)域，量子計算機(jī)能解決，而經(jīng)典計算機(jī)不能的第一批案例?！?/span>

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

阿倫森當(dāng)時堅信不存在速度更快的經(jīng)典算法：“在我看來，這是完成整個故事很重要的一環(huán)。”

2017 年唐開始了這項研究，打算將推薦問題作為自己畢業(yè)論文的課題。開始的幾個月，唐都在努力證明更快的經(jīng)典算法不存在。但隨著研究的深入，唐不禁猜測，這樣的算法沒準(zhǔn)是存在的。

唐表示：“我越來越覺得存在這樣一個速度更快的經(jīng)典算法，但我對自己的想法很懷疑，畢竟斯科特堅信不存在這樣的算法，而他更權(quán)威。”

隨著畢業(yè)論文截稿日期的臨近，唐終于給阿倫森寫信承認(rèn)了自己的疑問：“唐寫道，事實上‘我認(rèn)為這樣的算法存在’?！?/span>

2017 年春，唐寫出了這個經(jīng)典算法，并在阿倫森的指導(dǎo)下完善了其中的某些步驟。受兩年前克里尼迪斯與普拉卡什算法的啟發(fā)，唐發(fā)現(xiàn)量子算法中的量子抽樣思想可以直接應(yīng)用到經(jīng)典算法中，進(jìn)而完成了自己的算法。與量子算法相同，唐的算法也在多重對數(shù)時間內(nèi)運(yùn)行，即計算時間與特征量（如數(shù)據(jù)集中用戶量、產(chǎn)品量等）的對數(shù)相關(guān)，運(yùn)算速度與以往的經(jīng)典算法相比有指數(shù)級提升。

唐寫完算法之后，阿倫森希望能在發(fā)表之前確認(rèn)算法的正確性：“我很是緊張，一旦唐公布在網(wǎng)上的論文存在錯誤，他的學(xué)術(shù)生涯會受到很大影響?！?/span>

阿倫森 6 月參加了加州大學(xué)伯克利分校（the University of California, Berkeley）的量子計算研討會。包括克里尼迪斯、普拉卡什等在內(nèi)的多名量子計算領(lǐng)域?qū)＜叶紝⒊鱿摃h。阿倫森打算在正式會議結(jié)束后，邀請?zhí)频讲死v講他的經(jīng)典推薦算法。

唐分別在 6 月 18 日和 19 日上午舉辦了兩場講座，回答了聽眾的提問。在長達(dá)四小時的講座結(jié)束后，大家達(dá)成了共識：唐的經(jīng)典算法應(yīng)該是對的。然而許多在場聽眾都沒意識到，這位看似老成的演講者年紀(jì)非常小?？死锬岬纤姑枋龅溃骸罢娌桓蚁嘈盘浦挥?18 歲，我整場講座都沒聽出來，他演講的時候顯得很成熟?！蹦壳?，只要等到同行評議做完，這項算法就可以正式發(fā)表了。

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

阿倫森評價：“唐扼殺了（克里尼迪斯與普拉卡什的）量子計算優(yōu)越性，但從另一個角度來看，正是他們的算法孕育出了唐的新算法。沒有他們的量子算法，就不會有今天的經(jīng)典算法?！?/span>