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

近日，德克薩斯州的一名少年在網上發表了一篇論文，質疑了當前“量子優勢”主流驗證方法的可靠性。在這篇論文中，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 的發現為量子計算與經典計算間的相互影響提供了理論依據。但這並不意味著量子計算與經典計算相比沒有優勢。有網友對此評論“量子電腦就像是現代版的‘煉金術’”。誠然，至今我們仍未造出任何與傳統電腦有區別的所謂量子電腦，但就像煉金術啟蒙了化學領域，對量子計算的研究也將引導未來更多的發現。