[[238644]]

尤因·唐的近照

　　尤因·唐將在今年秋季進(jìn)入研究生院。圖片來源：Vivian Abagiu 攝于得克薩斯大學(xué)奧斯汀分校

　　來自美國得克薩斯州的一名天才少年給量子計算界潑了一盆冷水。在本月早些時候發(fā)表于網(wǎng)上的一篇論文（https://arxiv.org/pdf/1807.04271.pdf）中，年僅 18 歲的尤因·唐（Ewin Tang）證明了普通計算機(jī)能解決一個重要的計算問題，而性能可能與量子計算機(jī)相當(dāng)。

　　舉個最實(shí)際的例子，“推薦問題”涉及亞馬遜和 Netflix 等服務(wù)如何確定你可能想要嘗試哪些產(chǎn)品。計算機(jī)科學(xué)家們之前認(rèn)為，這是***例子之一，證明了用量子計算機(jī)來解決要快得多，因而推薦問題成為證明這些未來機(jī)器強(qiáng)大功能的重要例子。現(xiàn)在唐否定了這個證明。

　　唐說：“這曾是證明量子計算機(jī)可大幅提速的最經(jīng)典例子之一，現(xiàn)在再也立不住腳。”他在今天春季畢業(yè)于得克薩斯大學(xué)奧斯汀分校，秋季將攻讀華盛頓大學(xué)的博士學(xué)位。

　　唐在 2014 年 14 歲那年，直接跳過四到六年級后，入讀得克薩斯大學(xué)奧斯汀分校，主修數(shù)學(xué)和計算機(jī)科學(xué)。2017 年春季，唐報名就讀量子計算領(lǐng)域的著名研究人員斯科特·阿倫森（Scott Aaronson）所教的量子信息課程。阿倫森認(rèn)為唐是特別有才華的學(xué)生，主動表示愿意在一個獨(dú)立研究項(xiàng)目當(dāng)他的顧問。阿倫森扔給了唐幾個問題來選擇，包括推薦問題。唐有點(diǎn)不情愿地選擇了推薦問題。

　　唐說：“我之所以猶豫不決，是因?yàn)槲铱吹酵扑]問題的***眼覺得這似乎是個難題，但這其實(shí)是他給我的最簡單的問題。”

　　推薦問題旨在為商家推薦用戶可能喜歡的產(chǎn)品。不妨以 Netflix 為例。它知道你看過哪些電影。它知道其他數(shù)百萬用戶觀看哪些電影。結(jié)合這些信息，你接下來可能想要觀看什么電影？

　　你可以想象這些數(shù)據(jù)排列在巨大的網(wǎng)格或矩陣中，頂部列出了電影，一側(cè)列出了用戶，網(wǎng)格中各點(diǎn)的值量化了每個用戶是否喜歡每部電影或喜歡的程度。一種好的算法會快速準(zhǔn)確地識別電影和用戶之間的相似之處，填充矩陣中的空白，以此推薦電影。

　　2016 年，約爾達(dá)尼斯·克倫尼迪斯（Iordanis Kerenidis）和阿努帕姆·普拉卡什（Anupam Prakash）這兩位計算機(jī)科學(xué)家發(fā)布了一種量子算法，該算法解決推薦問題的速度比任何已知的經(jīng)典算法都要快得多。他們實(shí)現(xiàn)這種速度的提升一方面得益于簡化問題：不是填寫整個矩陣、確定需要推薦的單一***產(chǎn)品，而是開發(fā)了一種將用戶分成少數(shù)類別的方法：他們喜歡大片還是獨(dú)立電影？然后對現(xiàn)有數(shù)據(jù)采樣，以便推薦的內(nèi)容足夠合適。

　　在克倫尼迪斯和普拉卡什發(fā)表研究成果時，只有少數(shù)幾個例子表明量子計算機(jī)似乎能夠以比經(jīng)典計算機(jī)快得多的速度解決問題。那些例子大多數(shù)是專門的，它們旨在充分發(fā)揮量子計算機(jī)優(yōu)勢的狹窄問題，這包括今年早些時候《Quanta》報道的“傅換關(guān)聯(lián)”（forrelation）問題?？藗惸岬纤购推绽ㄊ驳慕Y(jié)果之所以令人興奮，是因?yàn)樗峁┝巳藗冴P(guān)注的、量子計算機(jī)比經(jīng)典計算機(jī)更勝一籌的一個實(shí)際問題。

　　巴黎計算機(jī)科學(xué)基礎(chǔ)研究所的計算機(jī)科學(xué)家克倫尼迪斯說：“在我看來，這是機(jī)器學(xué)習(xí)和大數(shù)據(jù)領(lǐng)域的首批例子之一，表明了量子計算機(jī)可以做一些我們?nèi)匀徊恢廊绾斡媒?jīng)典計算機(jī)來做的事情。”

　　克倫尼迪斯和普拉卡什證明了量子計算機(jī)能夠以遠(yuǎn)超任何已知算法的速度解決推薦問題，但他們并沒有證明不存在一種快速的經(jīng)典算法。因此，當(dāng)阿倫森在 2017 年開始與唐合作時，這就是他提出的那個問題：證明沒有一種快速的經(jīng)典推薦算法，從而證實(shí)克倫尼迪斯和普拉卡什認(rèn)為量子計算機(jī)可大幅提速的觀點(diǎn)屬實(shí)。

　　阿倫森產(chǎn)：“在我看來，這是故事的一個重要細(xì)節(jié)。”他當(dāng)時認(rèn)為，不存在快速的經(jīng)典算法。

　　唐于 2017 年秋季開始研究這項(xiàng)工作，打算將推薦問題作為高級論文課題。唐花了幾個月努力證明不可能存在快速的經(jīng)典算法。隨著時間的推移，唐開始認(rèn)為可能存在這種一樣算法。

　　唐說：“我開始相信有一種快速的經(jīng)典算法，但沒法向自己證明這一點(diǎn)，因?yàn)樗箍铺厮坪跽J(rèn)為沒有這樣的經(jīng)典算法，他可是權(quán)威人士。”

　　***，隨著高級論文的***期限漸漸臨近，唐寫信給阿倫森，承認(rèn)自己越來越感到懷疑：“唐寫信跟我說‘我認(rèn)為有一種快速的經(jīng)典算法’，”阿倫森如是說。

　　在整個春季，唐都在撰寫研究結(jié)果，并與阿倫森一起闡清證明中的幾個步驟。唐發(fā)現(xiàn)的快速經(jīng)典算法直接受到克倫尼迪斯和普拉卡什兩年前發(fā)現(xiàn)的快速量子算法的啟發(fā)。唐表明，他們在算法中使用的那種量子采樣技術(shù)在經(jīng)典環(huán)境中可以復(fù)制。與克倫尼迪斯和普拉卡什的算法一樣，唐的算法以多重對數(shù)時間運(yùn)行，這意味著計算時間隨著特征（如數(shù)據(jù)集中的用戶和產(chǎn)品數(shù)量）的對數(shù)而變化，而且比任何之前已知的經(jīng)典算法快得多。

　　一旦唐完成了算法，阿倫森想要在公開發(fā)布之前確信結(jié)果是正確的。阿倫森說：“我仍然惴惴不安，一旦唐將論文放到網(wǎng)上，萬一結(jié)果是錯的，唐在其職業(yè)生涯上的***篇重大論文就糗大了。”

　　阿倫森早就計劃 6 月份參加加州大學(xué)伯克利分校的量子計算研討會。這個領(lǐng)域的許多大腕都悉數(shù)到場，包括克倫尼迪斯和普拉卡什。阿倫森邀請?zhí)魄巴死?，在正式會議結(jié)束后的幾天里非正式地介紹他的算法。

　　在 6 月 18 日和 19 日這兩天早上，唐做了兩次講座，從容地回答了聽眾拋出來的問題。四小時過后，大家達(dá)成了一個共識：唐的經(jīng)典算法似乎是正確的。然而，在座的許多人沒有意識到這位演講者到底有多年輕。克倫尼迪斯說：“我不知道尤因才 18 歲，從談話中我絕對聽不出來。在我看來，尤因的談話顯得非常成熟。”該算法現(xiàn)正接受發(fā)布之前的正式的同行評審。

　　對于量子計算界而言，唐的結(jié)果可謂是一記重拳，也可以說不是。唐否定了證明量子計算優(yōu)勢的最清晰最典型的例子之一。與此同時，唐的論文進(jìn)一步證明了量子算法研究和經(jīng)典算法研究確實(shí)可以相互促進(jìn)。

　　阿倫森說：“唐否定了克倫尼迪斯和普拉卡什認(rèn)為量子計算機(jī)可大幅提速的觀點(diǎn)，但是從另一個意義上來說，唐做出了一次重大的改進(jìn)，在他們的成果上更進(jìn)一步。要不是他們倆的量子算法，唐也許根本想不出這種經(jīng)典算法。”