[[238644]]

尤因·唐的近照

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

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

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

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

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

　　唐說：“我之所以猶豫不決，是因為我看到推薦問題的***眼覺得這似乎是個難題，但這其實是他給我的最簡單的問題。”

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

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

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

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

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

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

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

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

　　唐說：“我開始相信有一種快速的經(jīng)典算法，但沒法向自己證明這一點，因為斯科特似乎認為沒有這樣的經(jīng)典算法，他可是權(quán)威人士。”

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

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

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

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

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

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

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