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

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

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

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

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

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

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

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

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

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

Tang 說(shuō)：「我當(dāng)時(shí)很猶豫，因?yàn)槲矣X(jué)得推薦問(wèn)題很難，但這已經(jīng)是他給我的最簡(jiǎn)單的問(wèn)題了。」

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

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

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

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

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

「在我看來(lái)，這是機(jī)器學(xué)習(xí)和大數(shù)據(jù)領(lǐng)域中最早展示量子計(jì)算可求解經(jīng)典計(jì)算尚未解決的問(wèn)題的案例之一。」巴黎計(jì)算機(jī)科學(xué)基礎(chǔ)研究所的計(jì)算機(jī)科學(xué)家 Kerenidis 說(shuō)。

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

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

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

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

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

Tang 完成該算法后，Aaronson 想在公開之前先確認(rèn)其正確性。「我仍然很擔(dān)心，這篇論文被放到網(wǎng)上后，萬(wàn)一該研究是錯(cuò)誤的，那么 Tang 學(xué)術(shù)生涯中第一篇「?jìng)ゴ蟆拐撐木蛯⒃庥龌F盧。」Aaronson 說(shuō)道。

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

6 月 18 日、19 日上午，Tang 進(jìn)行了兩次演講，同時(shí)回答了觀眾的提問(wèn)。四小時(shí)的演講結(jié)束后，大家達(dá)成了共識(shí)：Tang 的經(jīng)典算法似乎是正確的。但是，當(dāng)時(shí)身處現(xiàn)場(chǎng)的很多人都沒(méi)有意識(shí)到這位演講者是多么年輕。「我不知道 Ewin 只有 18 歲，演講時(shí)并沒(méi)有得到這個(gè)信息。對(duì)我來(lái)說(shuō)，Ewin 的演講非常成熟。」Kerenidis 說(shuō)道。現(xiàn)在該算法正面臨正式的出版前的同行評(píng)議。

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

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

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

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

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

機(jī)器之心的小伙伴怎么看呢？