18歲天才少年發表論文，「打臉」量子優勢驗證方法

來自專欄 DeepTech深科技210 人贊了文章

近日，德克薩斯州的一名少年在網上發表了一篇論文，質疑了當前「量子優勢」主流驗證方法的可靠性。在這篇論文中，18 歲的 Ewin Tang 證明了經典計算機能以與量子計算機相同的性能解決一種重要的計算問題——「推薦問題」（recommendation problem）。

「推薦問題」最實際的例子之一就是亞馬遜和 Netflix 這類商家如何判斷客戶可能需要哪些商品。計算機學家一直都將「能快速解決此類問題」看作是量子計算概念的標誌，也是驗證量子計算方法是否可行的經典手段。然而，Ewin Tang 的這篇論文橫空出世，打破了人們對於用「推薦問題」驗證量子計算可行性和優越性的執著。

論文作者，Ewin Tang 說：「這曾是最能體現量子計算優勢的方法之一，但現已不復存在。」Ewin Tang 於今年春季畢業於德克薩斯大學奧斯汀分校，並將於秋季開始在華盛頓大學攻讀博士學位。

2014 年，14 歲的 Ewin Tang 在跳級後就讀於德克薩斯大學奧斯汀分校，主修數學和計算機科學。2017 年春，Tang 選了一門量子計算方向，由量子計算著名研究員 Scott Aaronson 教授所教授的量子信息課程。Aaronson 認為 Tang 是一位很有天賦的學生，給 Tang 提供了一個獨立研究項目機會，並親自擔當項目顧問。Aaronson 給 Tang 提供的研究機會有包括「推薦問題」在內的許多課題可選，而 Tang 當時則有點不情願地選擇了「推薦問題」課題。

圖｜Ewin Tang

Tang 說：「我當時猶豫不決，因為它看上去很難，但這是所有課題中最簡單的一個。」

「推薦問題」旨在為用戶提供產品建議。比如 Netflix，它知道你看過哪部電影，它也知道其他數百萬用戶所觀看過的內容，而 Netflix 需要根據這些信息為你做出影視推薦。

我們可以將這些數據想成一種信息量巨大的表格，表格的列為各部電影，表格的行為每個具體用戶，而表格中每個數字格的值則用於量化用戶對於某部電影的喜好程度。此時，一個好的演算法可以通過快速準確地識別電影和用戶之間的相似性來填充表格中的空白格，進而生成推薦。

2016 年，計算機學家 Iordanis Kerenidis 和 Anupam Prakash 聯手發布了一種量子演算法，該演算法能以比任何已知的經典演算法都快的速度解決「推薦問題」。具體來說，該演算法通過簡化問題實現這一「量子優勢」：不用完成整個表格，而是將用戶進行分類（如某一用戶喜歡好萊塢大片還是小眾電影），再對現有數據進行抽樣，然後生成建議。

在 Kerenidis 和 Prakash 的開發這套演算法時，還沒有幾個人能實際驗證「量子優勢」的可行方法，大多數方法都有著很大的局限性。當時 Kerenidis 和 Prakash 的研究結果令人興奮，因為它提供了一個可實際驗證「量子優勢」的可靠方法。

巴黎計算機研究所科學家，Kerenidis 說：「據我所知，當時這是機器學習和大數據領域中的首個可靠方法，展示了量子計算機可以解決我們從經典計算上無從下手的一些問題。」

雖然 Kerenidis 和 Prakash 的研究證明了量子計算機能更快地解決「推薦問題」，但它並不能證明經典演算法達不到這樣的速度。而這也正是 Tang 所選擇的課題——證明沒有快速的經典推薦演算法，從而驗證 Kerenidis 和 Prakash 所展示的量子優勢。

Tang 於 2017 年秋季開始研究工作，打算將「推薦問題」課題研究寫成一篇畢業論文。幾個月來，Tang 絞盡腦汁地想要證明快速經典演算法並不存在，但隨著時間的推移，Tang 發現這種演算法或許是存在的。

Tang 說：「當時我開始相信快速經典演算法的存在，但無法向自己證明這一點，因為當時包括 Aaronson 在內的權威人士都認為這不太可能。」

最後，隨著論文的期限臨近，Tang 寫信給 Aaronson 闡述了他的觀點，Aaronson 說：「Tang 當時寫信給我，說他認為有一種可能存在的快速經典演算法。」

於是，在今年春天，Tang 與 Aaronson 合作在論文中闡明了證明快速經典演算法存在過程中的關鍵步驟。Tang 所發現的快速經典演算法可以說是直接受到了 Kerenidis 和 Prakash 兩年前發現的快速量子演算法啟發。Tang 表示，Kerenidis 和 Prakash 所使用的量子採樣方法可以在經典環境中予以複製。與 Kerenidis 和 Prakash 的演算法一樣，Tang 的演算法在多對數時間（polylogarithmic time）內完成運算，與量子演算法的速度相當，比任何此前已知的經典演算法都快。

Aaronson 當時希望在 Tang 公開發表演算法前確認一遍它是否正確。Aaronson 說：「我現在仍然對此感到緊張，因為如果 Tang 所發表的論文中存在錯誤，他的學術生涯也會受到影響。」

Aaronson 於 6 月參加了一個加州大學伯克利分校的量子計算研討會。包括 Kerenidis 和 Prakash 在內，該領域的許多大腕悉數出席。在正式會議結束後的幾天里，Aaronson 邀請 Tang 來伯克利簡單地介紹一下他的快速經典演算法。

在 6 月 18 日和 19 日的早晨，Tang 在伯克利做了兩次講座，並接受了提問。在四個小時的講座結束後，會場中的共識是 Tang 的經典演算法似乎是正確的。然而，房間里的許多人都沒有意識到演講者的年齡。Kerenidis 說：「我不知道 Ewin 只有 18 歲。對我來說，Ewin 只是一個正在進行成熟的談話的成年人」。

目前，該演算法正在經同行評審準備正式發表。

Tang 的發現為量子計算與經典計算間的相互影響提供了理論依據。但這並不意味著量子計算與經典計算相比沒有優勢。有網友對此評論「量子計算機就像是現代版的『鍊金術』」。誠然，至今我們仍未造出任何與傳統計算機有區別的所謂量子計算機，但就像鍊金術啟蒙了化學領域，對量子計算的研究也將引導未來更多的發現。