[[238644]]

尤因·唐的近照

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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