18歲華裔少年挑戰“量子計算優勢”

18歲華裔少年挑戰“量子計算優勢”

作者：徐令予

量子計算的一個重要成果被一個18歲少年推翻。

自古英雄出少年！18歲的美國德克薩斯州華裔少年Ewin Tang的論文證明，經典計算機幾乎可以像量子計算機一樣快速地解決“推薦問題”。量子優勢（又稱量子霸權）的一個最佳案例如今卻被拉下了神壇[1]。

 

 

推薦算法是計算機領域中的一種重要算法，它可以用來為客戶可能喜歡的產品和服務提供建議。例如影視網站從海量數據中獲取到用戶數據，根據用戶過去喜歡或搜索過的影視內容，為用戶推薦與之相似的影視作品，而內容相似性的度量，是算法運用的關鍵。

我們可以將這些數據視為一個矩陣，橫向代表電影，豎向代表用戶，而網格中各點是某用戶對某電影的喜好程度的量化值。一個好的算法可以通過快速準確地識別電影和用戶之間的相似性，並填充矩陣中的空白以生成推薦。

2016年，計算機科學家Iordanis Kerenidis和Anupam Prakash發布了一種量子算法，該算法解決推薦問題的速度比任何已知經典算法要快得多。他們通過簡化問題來實現量子加速：不是填寫整個矩陣並確定推薦單一最佳產品，而是先將用戶根據他們的喜好分類為人數不多的小組，並對現有數據進行抽樣，從而生成足夠好的建議。

在這之前，量子計算機解決某些問題比經典計算機有指數式加速優勢的例子已經存在，但這些問題都比較專門和單一，量子計算機的優勢有很大局限性。 Kerenidis和Prakash的研究結果令人興奮，因為這是一種具有普遍意義的算法，而且又有著人們非常關心的實際應用價值。

“據我所知，它是機器學習和大數據中的一個好例子，我們展示了量子計算機可以做一些我們仍然不知道如何用經典辦法解決的事情。”巴黎計算機基礎科學研究所的科學家Kerenidis說。

一個18歲的少年有何能耐改變量子計算的曆程？希望的種子埋下於四年之前。2014年，14歲的Ewin連跳幾級後入讀於德州大學奧斯汀分校，主修數學和計算機科學。2017年春天，Ewin選修了斯科特·亞倫森（Scott Aaronson）教授的量子信息課程，亞倫森教授是量子計算專家。亞倫森教授慧眼識英雄，很快發覺Ewin是匹千裏馬，於是主動提出願意為Ewin同學擔任獨立研究項目的顧問。

亞倫森教授給了Ewin一些可供選擇的課題，這其中就包括了“推薦問題”，Ewin選擇了它，但有點不情不願。“我有些猶豫不決，因為當我初看時，這似乎是一個難題，但這又是他給我的問題中間最簡單的一個。”Ewin說。

2017年秋季開始，Ewin全身投入工作，打算將“推薦問題”作為自己的大學畢業論文。亞倫森教授和Ewin的原始想法是：通過證明不存在快速的經典推薦算法，從而確認Kerenidis和Prakash的量子加速算法的真實價值。幾個月來，Ewin一直拚著命想證明關於“推薦問題”不存在任何快速經典算法。“山窮水盡疑無路，柳暗花明又一村。”隨著時間的推移，Ewin開始看到了構建快速經典算法的一線希望。

“我開始相信有一種快速的經典算法，但我無法向自己證明這一點，因為亞倫森教授似乎認為這不可能，而他是權威，”Ewin說。隨著畢業論文的最後期限接近，Ewin寫信把自己的懷疑告訴了教授。

在今年整個春天裏，Ewin把自己的想法變成嚴格的算法，並與亞倫森教授合作把算法中的一些步驟作出澄清和證明。Ewin發現的快速經典算法直接受到Kerenidis和Prakash兩年前發現的快速量子算法的啟發。Ewin發覺他倆的算法中使用的那種采樣技術也可以在經典環境中複製。與Kerenidis和Prakash的算法一樣，Ewin的經典算法在多重對數時間內運行，這意味著計算時間與數據量（例如數據集中的用戶和產品的數量）的關係是對數函數，它比任何先前已知的經典算法要快指數倍，與量子算法速度對等。

算法完成後，亞倫森教授希望在公開發布之前確定它是正確的，他真心希望自己的愛徒的學術生涯有一個好的開端。

亞倫森教授對Ewin同學的培養和提攜真可謂不遺餘力，為此他作出了一個重要的決定。6月份，亞倫森教授出席在加州大學伯克利分校舉行的量子計算研討會。該領域的許多大腕都將出現在那裏，其中包括了Kerenidis和Prakash。在正式會議結束後的幾天裏，由亞倫森教授出麵邀請Ewin同學來伯克利大學非正式地介紹他的新算法。

在6月18日和19日的早晨，Ewin做了兩次講座，同時接受觀眾提問。四小時的講座結束時，人們已經有了共識：Ewin的創新經典算法似乎是正確的。然而，會議室的許多聽眾都沒有意識到這位演講者的真實年齡。 “我不知道Tang先生是18歲，從他的演講中完全感覺不到這一點。對我來說，他就是一個非常成熟的演講者。”這位量子計算專家Kerenidis如是說。目前，Ewin的論文正式發布之前正在麵臨同行的評審。

下麵談談我的幾點不成熟的看法。

1）Ewin同學的研究結果給量子計算投下了陰影。他的結果消除了量子優勢中最清晰、最有說服力的一個例證。不過我們也應同時認識到，Ewin同學的論文進一步證明了量子算法和經典算法研究之間存在富有成效的相互作用。

正如亞倫森教授所說：“Ewin正在消除[Kerenidis和Prakash的]量子加速，但在另一種意義上，Ewin所做的經典算法改進正是在他倆的工作基礎上進行的。沒有他們的量子算法，Ewin可能想不出這種新的經典算法。”

所以應該進一步加強對量子計算的基礎科學研究。研製量子計算機不是為了取代現有的經典電子計算機，而是為了促進、支持和輔助經典電子計算機。

2）Ewin Tang的論文標題是：推薦係統的量子啟發經典算法。他的算法是受“量子啟發的”，所以他能夠看到量子算法技巧實際上並不真正需要量子計算機，他可以在經典計算機上複製那些“依賴於量子計算機的聰明想法”。有可能長期以來我們扭曲和放大了量子計算機和經典計算機之間的差異。

他的這個發現或許具有更普遍的意義。當然也不是從Tang的結果中直接得到更多的經典算法去代替量子算法，但另一方麵，他確實為挑戰更多的量子算法提供了新的思路。不過這僅是我的感覺。

3）必須認識到目前所有的量子算法僅僅停留在算法的理論研究階段，說白了就是紙上談兵，最多也隻能在經典的電子計算機上做做模擬。可以實際運用這些量子算法的量子計算機距離我們依舊十分的遙遠。

量子計算機目前麵臨的不止隻是工程困境，現在有些科學家甚至認為從原理層麵上來看，建造用來運行許多量子算法的量子計算機就是不可能完成的任務。2018年初的量子雜誌連載有三篇質疑量子計算機可行性的相關報導，其中的一篇介紹了以色列數學家Gil Kalai和他的研究工作。

Gil Kalai和其他專家合作發表了一篇論文[2]。Kalai的文章是關於Boson sampling的噪聲分析，結論是Boson sampling對噪聲相當敏感，在容錯量子計算機中很難實現明顯的量子加速。量子態的退相幹現象實質上是有關噪聲的物理過程，Kalai通過數學建模和分析得出兩條結論：1）把物理過程的噪聲抑製趨向於零的代價是無法承受的，換言之，要得到精確穩定的邏輯量子比特，需要的物理量子比特數會有指數型的增加；2）過程的噪聲減少是以係統靈敏度減少為代價的，就是說，量子糾錯會限製量子態承載信息的豐富多樣性。總而言之，我們不能既要量子態的豐富多樣，又要量子態的可控和穩定。Gil Kalai的觀點有待進一步的實驗驗證，但是他的研究至少讓我們進一步認識到，研製實用的量子計算機的道路十分艱難遙遠。

可實用的量子計算機還在未定之天，而必須運行在量子計算機上的一個重要的量子算法對經典電子計算機又不具備任何速度優勢。由此可知，在可預見的未來量子計算的實用意義不宜過分誇大，用量子計算機的威脅作為現階段工程建設的決策依據更不合適。

4）Ewin Tang的故事再一次告訴我們：“世有伯樂，然後有千裏馬。千裏馬常有，而伯樂不常有。故雖有名馬，祇辱於奴隸人之手，駢死於槽櫪之間，不以千裏稱也。”

 

[1]https://arxiv.org/abs/1807.04271

[2]“Gaussian Noise Sensitivity and BosonSampling”  https://arxiv.org/abs/1409.3093