量子計(jì)算機(jī)很神？18歲華裔少年用經(jīng)典計(jì)算機(jī)算得一樣快

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　題目本身就錯(cuò)了

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

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

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

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

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

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

　　“殺死”量子計(jì)算？

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

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

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

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

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