量子計算機很神？18歲華裔少年用經典計算機算得一樣快

 電商平臺和視頻網站該給用戶推薦哪些產品和新片？這背后的算法，被稱為“推薦問題”。推薦問題曾是量子計算“秒殺”經典計算機的最佳案例，然而，美國一位18歲華裔少年唐（Edwin Tang）近日提出了一種經典算法，其性能表現和量子計算相當。

　　這再次掀起了量子計算機到底能在多大程度上實現“量子加速”乃至“量子霸權”，超越經典計算機的討論。

　　“這曾是量子加速的最好例證，但現在不成立了。”這位得州大學奧斯汀分校的畢業生告訴Quanta Magazine雜志。畢業幾周后，唐在導師阿倫森（Scott Aaronson）的帶領下，在加州大學伯克利分校的一個重磅量子計算會議上公布了這個成果。

華裔少年Edwin Tang “量子位”微信公眾號 資料圖給神童布置的作業

　　今年九月，唐將去華盛頓大學攻讀博士學位。他的學習經歷頗有神童色彩，14歲時就連跳三級，直接進入得州大學奧斯汀分校就讀計算機和數學專業。

　　阿倫森是頂尖的量子計算專家，專注于測試“量子霸權”。這是一個由加州理工學院教授John Preskill在2012年提出的概念，即量子計算機在特定問題上表現超過世上最好的經典計算機。傳統的計算機運用要么是“0”，要么是“1”的二進制比特進行計算，量子計算機使用的量子比特則可以是“0”或“1”。理論上，10個量子比特就可以同時計算2的10次方次。

　　他估計，“量子霸權”需要超過49個量子比特。

　　阿倫森在教授一堂量子信息課程時，很快就發掘了唐的天賦。他交給唐一些需要獨立解決的問題，由他自己挑選。

　　唐不太情愿地選擇了“推薦問題”：“這看起來是個難題，但這已經是他給我的問題最簡單的一個了。”

　　一個視頻網站擁有的數據，就是所有用戶曾在上面瀏覽過的影片。據此，它要如何猜出你可能想要觀看的新影片？

　　這些數據等于一個網格，橫向是不同的電影，縱向是不同的用戶，依據用戶對該電影的喜好程度，可以在網格中填入相應的數值。

　　一個聰明的算法所要做的，就是快速而準確地找到其中的相似性，在空白的網格上填上數值。

　　2016 年，法國巴黎七大的Iordanis Kerenidis 和 新加坡南洋理工大學Anupam Prakash公布了一種“量子推薦算法”，比經典算法有了指數級的提高。這種算法并不企圖填滿整張空白網格，而是把用戶簡化成幾個大類。

　　這個案例當時是激動人心的。此前雖有人利用量子算法獲得了指數級的速度提升，但都是在很窄的應用問題上，更像是精致的小游戲。量子推薦算法則是在一個日常人都會接觸到的領域證明了量子計算的價值。

　　不過，這兩名計算機科學家只證明了量子推薦算法要比已知的任何經典推薦算法都要快得多，但卻沒有證明不存在更快的經典推薦算法。

　　阿倫森布置給唐的作業，就是要補上這個漏洞，證明沒有比得上量子算法的經典推薦算法。

　　題目本身就錯了

　　唐在研究的過程中，卻越來越覺得這樣的經典算法是存在的，他反復地自我質疑，因為阿倫森是領域里的權威。

　　最終，唐向阿倫森去信坦白了自己的想法。

　　在量子推薦算法的啟發下，唐發現他們所用的量子采樣技術完全可以在經典算法里復制。具體來講，把用戶數量、產品數取對數后，計算時間就會大大減少。

　　阿倫森反復驗證了這個經典算法的正確性，確保唐不會出道即“出糗”。

　　最終，在加州的量子計算會議上，面對著一眾領域內的“大佬”，唐連做了兩場報告，并得到了普遍的認可，包括提出量子推薦算法的Kerenidis。他表示，唐的報告很成熟，他完全意識不到唐才18歲。

　　下一步，唐的論文將接受正規的同行評議，以爭取正式發表。

　　“殺死”量子計算？

　　進入2018年，各大科技巨頭競爭“量子霸權”的格局越發激烈。IBM完成了50比特原型機；谷歌發布了研制高質量72比特量子計算機的計劃；微軟則宣布在5年內造出擁有100個拓撲比特的量子計算機。

　　不過，這不是個簡單的比誰比特數多的問題。一部分科學家對量子計算的前景仍持保守態度：在基礎量子理論層面上，學界還沒有解決量子比特的質量問題，即保持長時間、噪音少的量子糾纏。

　　在這個節骨眼上，唐的研究可以算是重創了量子計算，證偽了一個最能顯示量子計算機優勢的成果。但不能否認的是，唐的經典算法是在量子算法的基礎上演化而來的，這點亮了兩者之間的互動潛力。

　　正如阿倫森所說：“唐抹殺了Kerenidis 和Prakash的量子加速，但換個角度，唐的巨大成就是建立在他們的基礎上的。要不是先有了他們的量子算法，唐永遠做不出他的經典算法。”

　　在其他問題上，我們也完全可以期待由量子算法啟發出更多更好的經典算法。這或許是發展量子計算的“曲線救國”方案：就算短時間內造不出量子計算機，量子計算的思路本身就能創造價值。