一位18歲的華裔天才少年給向來高高在上的量子計算「潑了一盆冷水」。
在7月上旬發表於網絡的一篇論文中，來自德克薩斯州的尤因·唐（Ewin Tang）證明，傳統計算機能夠以接近量子計算機的速度解決一個重要的計算問題。這個問題最常見的形式為「推薦問題」，它涉及亞馬遜和Netflix這樣的服務如何確定用戶可能想要嘗試的產品。
計算機科學家認為，在量子計算機能夠以指數級的更快速度加以解決的問題中，「推薦問題」是最佳實例之一，並且提供了對這些未來機器能力的重要驗證。現在，唐推翻了這一驗證。
「這是量子加速最明確的實例之一，但現在已經不復存在了，」唐說道。
01「推薦問題」的量子算法
「推薦問題」旨在就用戶可能喜歡的產品提供建議。
以Netflix為例，它知道你看過哪些電影，它還知道另外數百萬用戶看過的節目。根據這些信息，是不是可以算出你接下來最有可能想要觀看什麼內容呢？
你可以想像一下，這些信息被排列在一個巨大的網格當中，其中頂部列出的是電影，底部側邊列出的是用戶，網格中各個點的值用於量化各個用戶是否喜歡各部電影，或者喜歡到何種程度。一種好的算法可以通過快速和準確地識別電影和用戶之間的相似性並填充矩陣中的空白，以此生成推薦內容。
2016年，計算機科學家艾奧丹尼斯·科倫尼迪斯（Iordanis Kerenidis）和阿努帕姆·普拉卡什（Anupam Prakash）發明了一種量子計算算法，它能夠以快過任何已知傳統計算算法的速度解決「推薦問題」。
從某種程度上說，這兩位科學家實現量子加速是通過簡化問題來實現的：不是填充整個矩陣以及確定要推薦的單個最佳產品，而是把用戶歸類到少數幾個類別（比如用戶是喜歡大片還是獨立電影），並對現有數據進行採樣，以此生成足夠好的推薦。
在科倫尼迪斯和普拉卡什發表他們研究成果的時候，相較於傳統計算機，量子計算機似乎只能在少數幾個問題上以指數級的更快速度進行解決。而且，大多數問題實例都是專門化的——它們都是被設計來發揮量子計算機優勢的狹隘問題。
科倫尼迪斯和普拉卡什的研究成果令人振奮，因為「推薦問題」是人們關心的現實問題，而量子計算機在解決它時的表現優於傳統計算機。
「據我所知，這是機器學習和大數據領域的第一個實例，讓我們得以展示量子計算機能夠完成一些傳統計算機無法完成的事情，」供職於巴黎計算機科學基礎研究所（Research Institute on the Foundations of Computer Science）的科倫尼迪斯說道。
02「我認為存在一種快速的傳統算法」
用現在流行的話來說，唐從小就是那個「別人家的孩子」。
2014年，在從四年級直接跳到六年級之後，14歲的唐被德州大學奧斯汀分校錄取，主修數學和計算機科學。今年春季，他從該校畢業，並將在秋季前往華盛頓大學攻讀博士學位。
2017年春，唐開始學習由著名量子計算研究員斯科特·亞倫森（Scott Aaronson）教授的量子信息課程。亞倫森認為唐是一位天賦異稟的學生，並親自擔任後者一個獨立研究項目的顧問。亞倫森列出一些問題給唐挑選，其中就包括「推薦問題」，唐有點不情願地選中了它。
「我當時猶豫不決，因為當我看著這個問題時，看上去似乎很難，但這已經是他給我的問題中最簡單的了，」唐說道。
科倫尼迪斯和普拉卡什證明，相較於任何已知算法，量子計算機能夠以指數級的更快速度解決「推薦問題」；不過，他們沒有證明不存在一種快速的傳統推薦算法。因此，當亞倫森在2017年開始跟唐合作開展研究時，這就是他提出的問題：證明不存在快速的傳統推薦算法，從而確認科倫尼迪斯和普拉卡什實現的量子加速是真實的。
「在我看來，為了讓這件事板上釘釘，這似乎是一個需要完善的重要細節，」亞倫森說道。當時他認為並不存在一種快速的傳統推薦算法。
2017年秋季，唐開始了自己的研究工作，他打算把「推薦問題」當成畢業論文的主題。在幾個月的時間裡，唐難於證明快速的傳統算法是不可能存在的。但隨著時間的推移，他開始認為，或許這樣的算法真有可能存在。
「我開始相信存在一種快速的傳統算法，但我無法向自己證明這一點，因為斯科特傾向於認為它不存在，而他是權威人士，」唐如是說。
最後，在畢業論文截稿日逼近的情況下，唐給亞倫森寫了一封信，將自己日益增長的懷疑和盤託出。「唐寫信給我說，事實上，『我認為存在一種快速的傳統算法』，」亞倫森回憶道。
整個春季，唐都在做這項研究，他把結果寫了出來，並跟亞倫森合作闡釋證明中的一些步驟。唐發現的快速傳統算法受到了科倫尼迪斯和普拉卡什在兩年前發現的快速量子算法的直接啟發，他證明兩人在算法中使用的量子採樣方法可以被復刻到傳統計算環境當中。
唐的算法也是一種對數多項式時間算法——這意味著計算時間跟特徵的對數（比如數據集中用戶和產品的數量）成比例關係——而且它的速度要比任何之前已知的傳統算法快得多。
在唐完成了這個算法之後，亞倫森望在公開發表前確定它是正確的。「我仍然感到緊張，一旦唐在網上發表了論文，如果它是錯的，那麼（唐）學術生涯的第一篇重要論文就會折戟,」亞倫森說道。
當時，亞倫森計劃於6月份參加在加州大學伯克利分校舉行的一場量子計算研討會。屆時該領域的很多大腕都會出現在那裡，包括科倫尼迪斯和普拉卡什。在正式會議結束之後，亞倫森邀請唐來到伯克利，對他的算法做非正式介紹。
在6月18日和19日的上午，唐做了兩場講座，並對聽眾提出的問題進行解答。4小時的講座結束後，大家有了一個共識：唐的傳統算法似乎是正確的。然而，在座的很多人並沒有意識到這位演講者有多年輕。「我之前不知道尤因才18歲，當然我也沒有從演講中了解到這一點。在我看來，尤因的演講非常成熟穩重。」科倫尼迪斯說道。
現在，唐的算法正在接受正式的同行評審。
「唐推翻了（科倫尼迪斯和普拉卡什的）量子加速，但另一個意義上來說，他實現了一項重大改進，在他們的研究成果上更進了一步。如果沒有他們的量子算法，唐也不會想出這種傳統算法。」亞倫森如是評價說。
本內容為造就團隊編譯，歡迎轉發朋友圈，如需轉載，請註明來源
翻譯丨何無魚
校對丨李莉
來源丨Quanta Magazine