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

　　這再次掀起了量子計算機到底能在多大程度上實現(xiàn)“量子加速”乃至“量子霸權(quán)”，超越經(jīng)典計算機的討論。

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

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

　　今年九月，唐將去華盛頓大學(xué)攻讀博士學(xué)位。他的學(xué)習(xí)經(jīng)歷頗有神童色彩，14歲時就連跳三級，直接進(jìn)入得州大學(xué)奧斯汀分校就讀計算機和數(shù)學(xué)專業(yè)。

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

　　他估計，“量子霸權(quán)”需要超過49個量子比特。

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

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

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

　　這些數(shù)據(jù)等于一個網(wǎng)格，橫向是不同的電影，縱向是不同的用戶，依據(jù)用戶對該電影的喜好程度，可以在網(wǎng)格中填入相應(yīng)的數(shù)值。

　　一個聰明的算法所要做的，就是快速而準(zhǔn)確地找到其中的相似性，在空白的網(wǎng)格上填上數(shù)值。

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

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

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

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

　　題目本身就錯了

　　唐在研究的過程中，卻越來越覺得這樣的經(jīng)典算法是存在的，他反復(fù)地自我質(zhì)疑，因為阿倫森是領(lǐng)域里的權(quán)威。

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

　　在量子推薦算法的啟發(fā)下，唐發(fā)現(xiàn)他們所用的量子采樣技術(shù)完全可以在經(jīng)典算法里復(fù)制。具體來講，把用戶數(shù)量、產(chǎn)品數(shù)取對數(shù)后，計算時間就會大大減少。

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

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

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

　　“殺死”量子計算？

　　進(jìn)入2018年，各大科技巨頭競爭“量子霸權(quán)”的格局越發(fā)激烈。IBM完成了50比特原型機；谷歌發(fā)布了研制高質(zhì)量72比特量子計算機的計劃；微軟則宣布在5年內(nèi)造出擁有100個拓?fù)浔忍氐牧孔佑嬎銠C。

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

　　在這個節(jié)骨眼上，唐的研究可以算是重創(chuàng)了量子計算，證偽了一個最能顯示量子計算機優(yōu)勢的成果。但不能否認(rèn)的是，唐的經(jīng)典算法是在量子算法的基礎(chǔ)上演化而來的，這點亮了兩者之間的互動潛力。

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

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