18歲華裔少年顛覆量子加速優勢，推動量子演算法經典化

來自專欄機器之心56 人贊了文章

選自quantamagazine，作者：Kevin Hartnett，參與：機器之心編輯部。

據國外媒體 Quantamagazine 報道，來自 UT Austin，剛剛年滿 18 歲的 Ewin Tang 最近證明了經典演算法能以和量子計算機相近的速度解決推薦問題。該結果淘汰了量子加速的最佳案例之一。這位天才少年的驚人成就已在社交網路中引發了激烈的討論。

國內量子計算專家也對此事發表了不同觀點。如百度量子實驗室負責人段潤堯在朋友圈評論說，「這是有關經典推薦演算法的非常有意思的進展。原先 Kerenidis 和 Prakash 證明了量子計算機能夠比任何已知演算法以指數級的速度解決推薦問題，但他們並沒有證明快速的經典演算法不存在。而 18 歲的 Ewin 則給出了一個快速的經典推薦演算法，從而說明 KP 量子演算法其實相對於經典演算法並無實際優勢。這是典型的因量子演算法思想激發經典快速演算法發現的例子，相信這樣的例子還會有一些，所謂『量子快速演算法的經典化』。」

南科大研究副教授鄭盛根對機器之心表示，「這個演算法如果能實用，個人覺得並不會挑戰量子計算，而是會推高量子演算法的理論研究，把量子演算法有效經典化將成為熱點。也就是多年前有些學者提出的 plan B: 如果量子計算機造不出來，那麼我們可以用量子計算的思想證明經典的東西。」

以下是對 Quantamagazine 相關報道內容的編譯：

一位來自德克薩斯州的少年將量子計算「拉下神壇」。在上月初發布在網上的一篇論文《A quantum-inspired classical algorithm for recommendation systems》中，18 歲的 Ewin Tang 證明普通計算機可以解決一個重要的計算問題，且其性能可與量子計算機媲美。

「推薦問題」在實踐層面上類似於 Amazon 和 Netflix 等服務商如何確定你喜歡的產品。計算機科學家曾認為這是利用量子計算機快速解決問題的最佳案例之一——這也成為量子計算機這種未來機器的力量驗證標準。但是現在 Tang 推翻了這個驗證。

「推薦問題是量子加速最直觀的案例，但現在已經不成立了。」Tang 說，他今年春天從德克薩斯大學奧斯汀分校畢業，並將於今年秋天前往華盛頓大學攻讀計算機科學博士學位。

Ewin Tang 從很小的時候就顯露出了天才的一面。據介紹，他在 13 歲時就成為了 UT Arlington 有史以來最年輕的 4.0GPA（以及全 A）學生。2014 年，14 歲的 Tang 連跳三級，直接進入德州大學奧斯汀分校（UT Austin）學習數學和計算機科學。

在量子計算領域的之外，Ewin Tang 還參與發表過四篇生物材料領域的論文。他也是發表在《Journal of Biomedical Nanotechnology》上論文「In Vivo Imaging of Infection Using a Bacteria-Targeting Optical Nanoprobe」的第一作者。

2017 年春天，Tang 選修了量子信息課程，該課程由量子計算領域的傑出研究者 Scott Aaronson 講授。Aaronson 認為 Tang 是個非常優秀的學生，並讓他擔任一個獨立研究項目的技術顧問。Aaronson 給 Tang 出了一些棘手的問題，包括推薦問題。Tang 有些不情願地選擇了推薦問題。

Tang 說：「我當時很猶豫，因為我覺得推薦問題很難，但這已經是他給我的最簡單的問題了。」

推薦問題是指給用戶推薦他們喜歡的產品。以 Netflix 為例。它知道你看過什麼電影。它也知道其他數百萬用戶看了些什麼。有了這些信息，它就能推斷你接下來最想看什麼。

你可以把這些信息想像成一個巨大的網格或矩陣，頂部列齣電影，底部列出用戶，網格交點的值量化了每個用戶對每個電影的喜愛程度。一個好的演算法可以通過快速準確地識別出用戶和電影間的相似性、填補矩陣中的空白（做出相應的矩陣計算）來生成推薦內容。

2016 年，計算機科學家 Iordanis Kerenidis 和 Anupam Prakash 發表了一種量子演算法，能以任何已知經典演算法的指數級速度解決推薦系統問題。他們能實現量子加速，部分原因在於簡化了問題：他們沒有填充整個矩陣並確定單個最佳推薦產品，而是開發了一種將用戶分為少數幾個類別的方法（例如，他們喜歡大片還是獨立電影），並採樣已有數據來生成足夠好的推薦。

他們在《Quantum Recommendation Systems》提出的演算法實現了 O(poly(k)polylog(mn)) 的冪對數計算時間複雜度，當時任何已知的經典推薦演算法都只能實現矩陣維數的多項式時間複雜度。其中 k 是推薦項的數量，m 是用戶數，n 是產品數。推薦演算法需要通過 mxn 的偏好矩陣計算出 k 個用戶最喜歡產品的排序。

在 Kerenidis 和 Prakash 發表他們的研究時，僅有少數幾例量子計算機有可能實現比經典計算機指數級快的求解速度的問題。大部分這類問題都是特定的，即它們是發揮量子計算機威力的狹窄範疇（這些問題包括「forrelation」）。Kerenidis 和 Prakash 的研究結果令人激動，因為它提供了一個真實世界中人們所關心的量子計算超越經典計算的問題。

「在我看來，這是機器學習和大數據領域中最早展示量子計算可求解經典計算尚未解決的問題的案例之一。」巴黎計算機科學基礎研究所的計算機科學家 Kerenidis 說。

Kerenidis 和 Prakash 證明了量子計算機比任何已知經典演算法在解決推薦問題時都要快得多，但他們沒有證明不存在快速的經典演算法。因此當 Aaronson 在 2017 年和 Tang 開始合作時，他提出了這個問題：證明不存在快速的經典推薦演算法，繼而證實 Kerenidis 和 Prakash 的量子加速是真實的。Aaronson 當時確實是這麼認為的。

Tang 在 2017 年秋天開始進行該研究，想要用推薦問題的研究作為畢業論文。幾個月後，他證明了不存在適用於該問題的快速經典演算法。但隨著時間的推移，Tang 開始思考或許這樣的演算法可行呢。

「我開始認為存在一種可解決推薦問題的快速經典演算法，但我自己也不太確定，因為 Scott 似乎認為這樣的演算法並不存在，而他是這方面的權威。」Tang 說道。

最終，隨著畢業論文 deadline 臨近，Tang 向 Aaronson 寫信，坦誠了他的疑問：「我認為存在一種快速的經典演算法。」

整個春天，Tang 為找到這一演算法而努力，他與 Aaronson 一起理清證明步驟。Tang 發現的快速經典演算法受到 Kerenidis 和 Prakash 兩年前發現的快速量子演算法的啟發。Tang 展示了 Kerenidis 和 Prakash 在他們演算法中使用的量子採樣技術可以在經典計算機設置中重現。與 Kerenidis 和 Prakash 的演算法類似，Tang 的演算法也以冪對數時間運行，這意味著計算時間會因特徵值（如數據集中用戶和產品的數量）的對數而發生伸縮，它比之前已知的所有經典演算法都要快上指數倍。

Tang 完成該演算法後，Aaronson 想在公開之前先確認其正確性。「我仍然很擔心，這篇論文被放到網上後，萬一該研究是錯誤的，那麼 Tang 學術生涯中第一篇「偉大」論文就將遭遇滑鐵盧。」Aaronson 說道。

Aaronson 計劃參加六月份在加州大學伯克利分校舉辦的一場量子計算研討會。該領域很多大牛都將出席這次研討會，包括 Kerenidis 和 Prakash。Aaronson 邀請 Tang 來到伯克利，在正式會議結束後非正式地展示其演算法。

6 月 18 日、19 日上午，Tang 進行了兩次演講，同時回答了觀眾的提問。四小時的演講結束後，大家達成了共識：Tang 的經典演算法似乎是正確的。但是，當時身處現場的很多人都沒有意識到這位演講者是多麼年輕。「我不知道 Ewin 只有 18 歲，演講時並沒有得到這個信息。對我來說，Ewin 的演講非常成熟。」Kerenidis 說道。現在該演算法正面臨正式的出版前的同行評議。

Tang 在《A quantum-inspired classical algorithm for recommendation systems》中提出的經典推薦演算法實現了 O(poly(k)polylog(m,n)) 的計算時間複雜度，比之前實現和 m、n 呈線性關係的時間複雜度的經典演算法速度有指數級提高。

論文地址：https://arxiv.org/abs/1807.04271

對於量子計算來說，Tang 的結果是一種倒退。抑或不是。Tang 去除了量子演算法最明確的一個優勢。同時，他的論文進一步證明了量子演算法和經典演算法研究之間密切的相互作用。

「Tang『殺死了』Kerenidis 和 Prakash 的量子加速，但從另一種角度來看，他也極大地改進了後者，而且 Tang 的演算法也建立在後者基礎上。如果沒有他們的量子演算法，Tang 也不可能發現該經典演算法。」Aaronson 說道。

在 HackNews 上網友對此議論紛紛；有人認為即使是 Tang 他們在論文中求解的問題也過於簡化，推薦演算法本身也不是很重要的問題類，能不能給學術界帶來深刻影響尚有疑問；有人甚至大膽假設經典計算和量子計算在廣義上是等價的，當然這已經被之前的「forrelation」問題所否定了（科學家近期證明了存在量子計算機能解決而經典計算機不可能解決的問題）；還有人則持更加開放的態度，猜測仍然存在其它類型的量子演算法可以轉換為相似計算複雜度的經典演算法。

機器之心的小夥伴怎麼看呢？