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

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

南科大研究副教授鄭盛根對機器之心表示,，「這個算法如果能實用,，個人覺得并不會挑戰(zhàn)量子計算，而是會推高量子算法的理論研究,，把量子算法有效經(jīng)典化將成為熱點,。也就是多年前有些學(xué)者提出的 plan B: 如果量子計算機造不出來，那么我們可以用量子計算的思想證明經(jīng)典的東西,?！?/p>

以下是對 Quantamagazine 相關(guān)報道內(nèi)容的編譯：

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

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

「推薦問題是量子加速最直觀的案例，但現(xiàn)在已經(jīng)不成立了,。」Tang 說,，他今年春天從德克薩斯大學(xué)奧斯汀分校畢業(yè),，并將于今年秋天前往華盛頓大學(xué)攻讀計算機科學(xué)博士學(xué)位。

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

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

2017 年春天,，Tang 選修了量子信息課程,，該課程由量子計算領(lǐng)域的杰出研究者 Scott Aaronson 講授。Aaronson 認為 Tang 是個非常優(yōu)秀的學(xué)生,，并讓他擔(dān)任一個獨立研究項目的技術(shù)顧問,。Aaronson 給 Tang 出了一些棘手的問題，包括推薦問題,。Tang 有些不情愿地選擇了推薦問題,。

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

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

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

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

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

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

「在我看來,，這是機器學(xué)習(xí)和大數(shù)據(jù)領(lǐng)域中最早展示量子計算可求解經(jīng)典計算尚未解決的問題的案例之一?！拱屠栌嬎銠C科學(xué)基礎(chǔ)研究所的計算機科學(xué)家 Kerenidis 說,。

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

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

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

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

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

Tang 完成該算法后,，Aaronson 想在公開之前先確認其正確性?！肝胰匀缓軗?dān)心,，這篇論文被放到網(wǎng)上后，萬一該研究是錯誤的,，那么 Tang 學(xué)術(shù)生涯中第一篇「偉大」論文就將遭遇滑鐵盧,。」Aaronson 說道,。

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

6 月 18 日,、19 日上午,，Tang 進行了兩次演講,，同時回答了觀眾的提問。四小時的演講結(jié)束后,，大家達成了共識：Tang 的經(jīng)典算法似乎是正確的,。但是，當(dāng)時身處現(xiàn)場的很多人都沒有意識到這位演講者是多么年輕,?！肝也恢?Ewin 只有 18 歲，演講時并沒有得到這個信息,。對我來說,，Ewin 的演講非常成熟?！筀erenidis 說道?，F(xiàn)在該算法正面臨正式的出版前的同行評議。

Tang 在《A quantum-inspired classical algorithm for recommendation systems》中提出的經(jīng)典推薦算法實現(xiàn)了 O(poly(k)polylog(m,n)) 的計算時間復(fù)雜度,，比之前實現(xiàn)和 m,、n 呈線性關(guān)系的時間復(fù)雜度的經(jīng)典算法速度有指數(shù)級提高。

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

對于量子計算來說,，Tang 的結(jié)果是一種倒退,。抑或不是。Tang 去除了量子算法最明確的一個優(yōu)勢,。同時,，他的論文進一步證明了量子算法和經(jīng)典算法研究之間密切的相互作用。

「Tang『殺死了』Kerenidis 和 Prakash 的量子加速,，但從另一種角度來看,，他也極大地改進了后者，而且 Tang 的算法也建立在后者基礎(chǔ)上,。如果沒有他們的量子算法,，Tang 也不可能發(fā)現(xiàn)該經(jīng)典算法?！笰aronson 說道,。

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

機器之心的小伙伴怎么看呢,？