據(jù)國外媒體 Quantamagazine 報道，來自 UT Austin，剛剛年滿 18 歲的 Ewin Tang 最近證明了經(jīng)典算法能以和量子計算機相近的速度解決推薦問題。該結(jié)果淘汰了量子加速的最佳案例之一。這位天才少年的驚人成就已在社交網(wǎng)絡中引發(fā)了激烈的討論。
國內(nèi)量子計算專家也對此事發(fā)表了不同觀點。如百度量子實驗室負責人段潤堯在朋友圈評論說，「這是有關(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)典化』?！?/p>
南科大研究副教授鄭盛根對機器之心表示，「這個算法如果能實用，個人覺得并不會挑戰(zhàn)量子計算，而是會推高量子算法的理論研究，把量子算法有效經(jīng)典化將成為熱點。也就是多年前有些學者提出的 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 等服務商如何確定你喜歡的產(chǎn)品。計算機科學家曾認為這是利用量子計算機快速解決問題的最佳案例之一——這也成為量子計算機這種未來機器的力量驗證標準。但是現(xiàn)在 Tang 推翻了這個驗證。
「推薦問題是量子加速最直觀的案例，但現(xiàn)在已經(jīng)不成立了?！筎ang 說，他今年春天從德克薩斯大學奧斯汀分校畢業(yè)，并將于今年秋天前往華盛頓大學攻讀計算機科學博士學位。
Ewin Tang 從很小的時候就顯露出了天才的一面。據(jù)介紹，他在 13 歲時就成為了 UT Arlington 有史以來最年輕的 4.0GPA（以及全 A）學生。2014 年，14 歲的 Tang 連跳三級，直接進入德州大學奧斯汀分校（UT Austin）學習數(shù)學和計算機科學。
在量子計算領域的之外，Ewin Tang 還參與發(fā)表過四篇生物材料領域的論文。他也是發(fā)表在《Journal of Biomedical Nanotechnology》上論文「In Vivo Imaging of Infection Using a Bacteria-Targeting Optical Nanoprobe」的第一作者。
2017 年春天，Tang 選修了量子信息課程，該課程由量子計算領域的杰出研究者 Scott Aaronson 講授。Aaronson 認為 Tang 是個非常優(yōu)秀的學生，并讓他擔任一個獨立研究項目的技術(shù)顧問。Aaronson 給 Tang 出了一些棘手的問題，包括推薦問題。Tang 有些不情愿地選擇了推薦問題。
Tang 說：「我當時很猶豫，因為我覺得推薦問題很難，但這已經(jīng)是他給我的最簡單的問題了?！?/p>
推薦問題是指給用戶推薦他們喜歡的產(chǎn)品。以 Netflix 為例。它知道你看過什么電影。它也知道其他數(shù)百萬用戶看了些什么。有了這些信息，它就能推斷你接下來最想看什么。
你可以把這些信息想象成一個巨大的網(wǎng)格或矩陣，頂部列出電影，底部列出用戶，網(wǎng)格交點的值量化了每個用戶對每個電影的喜愛程度。一個好的算法可以通過快速準確地識別出用戶和電影間的相似性、填補矩陣中的空白（做出相應的矩陣計算）來生成推薦內(nèi)容。
2016 年，計算機科學家 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ù)計算時間復雜度，當時任何已知的經(jīng)典推薦算法都只能實現(xiàn)矩陣維數(shù)的多項式時間復雜度。其中 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)典計算的問題。
「在我看來，這是機器學習和大數(shù)據(jù)領域中最早展示量子計算可求解經(jīng)典計算尚未解決的問題的案例之一。」巴黎計算機科學基礎研究所的計算機科學家 Kerenidis 說。
Kerenidis 和 Prakash 證明了量子計算機比任何已知經(jīng)典算法在解決推薦問題時都要快得多，但他們沒有證明不存在快速的經(jīng)典算法。因此當 Aaronson 在 2017 年和 Tang 開始合作時，他提出了這個問題：證明不存在快速的經(jīng)典推薦算法，繼而證實 Kerenidis 和 Prakash 的量子加速是真實的。Aaronson 當時確實是這么認為的。
Tang 在 2017 年秋天開始進行該研究，想要用推薦問題的研究作為畢業(yè)論文。幾個月后，他證明了不存在適用于該問題的快速經(jīng)典算法。但隨著時間的推移，Tang 開始思考或許這樣的算法可行呢。
「我開始認為存在一種可解決推薦問題的快速經(jīng)典算法，但我自己也不太確定，因為 Scott 似乎認為這樣的算法并不存在，而他是這方面的權(quán)威?！筎ang 說道。
最終，隨著畢業(yè)論文 deadline 臨近，Tang 向 Aaronson 寫信，坦誠了他的疑問：「我認為存在一種快速的經(jīng)典算法?！?/p>
整個春天，Tang 為找到這一算法而努力，他與 Aaronson 一起理清證明步驟。Tang 發(fā)現(xiàn)的快速經(jīng)典算法受到 Kerenidis 和 Prakash 兩年前發(fā)現(xiàn)的快速量子算法的啟發(fā)。Tang 展示了 Kerenidis 和 Prakash 在他們算法中使用的量子采樣技術(shù)可以在經(jīng)典計算機設置中重現(xiàn)。與 Kerenidis 和 Prakash 的算法類似，Tang 的算法也以冪對數(shù)時間運行，這意味著計算時間會因特征值（如數(shù)據(jù)集中用戶和產(chǎn)品的數(shù)量）的對數(shù)而發(fā)生伸縮，它比之前已知的所有經(jīng)典算法都要快上指數(shù)倍。
Tang 完成該算法后，Aaronson 想在公開之前先確認其正確性。「我仍然很擔心，這篇論文被放到網(wǎng)上后，萬一該研究是錯誤的，那么 Tang 學術(shù)生涯中第一篇「偉大」論文就將遭遇滑鐵盧?！笰aronson 說道。
Aaronson 計劃參加六月份在加州大學伯克利分校舉辦的一場量子計算研討會。該領域很多大牛都將出席這次研討會，包括 Kerenidis 和 Prakash。Aaronson 邀請 Tang 來到伯克利，在正式會議結(jié)束后非正式地展示其算法。
6 月 18 日、19 日上午，Tang 進行了兩次演講，同時回答了觀眾的提問。四小時的演講結(jié)束后，大家達成了共識：Tang 的經(jīng)典算法似乎是正確的。但是，當時身處現(xiàn)場的很多人都沒有意識到這位演講者是多么年輕?！肝也恢?Ewin 只有 18 歲，演講時并沒有得到這個信息。對我來說，Ewin 的演講非常成熟?！筀erenidis 說道。現(xiàn)在該算法正面臨正式的出版前的同行評議。
Tang 在《A quantum-inspired classical algorithm for recommendation systems》中提出的經(jīng)典推薦算法實現(xiàn)了 O(poly(k)polylog(m,n)) 的計算時間復雜度，比之前實現(xiàn)和 m、n 呈線性關(guān)系的時間復雜度的經(jīng)典算法速度有指數(shù)級提高。
論文地址：https://arxiv.org/abs/1807.04271
對于量子計算來說，Tang 的結(jié)果是一種倒退。抑或不是。Tang 去除了量子算法最明確的一個優(yōu)勢。同時，他的論文進一步證明了量子算法和經(jīng)典算法研究之間密切的相互作用。
「Tang『殺死了』Kerenidis 和 Prakash 的量子加速，但從另一種角度來看，他也極大地改進了后者，而且 Tang 的算法也建立在后者基礎上。如果沒有他們的量子算法，Tang 也不可能發(fā)現(xiàn)該經(jīng)典算法。」Aaronson 說道。
在 HackNews 上網(wǎng)友對此議論紛紛；有人認為即使是 Tang 他們在論文中求解的問題也過于簡化，推薦算法本身也不是很重要的問題類，能不能給學術(shù)界帶來深刻影響尚有疑問；有人甚至大膽假設經(jīng)典計算和量子計算在廣義上是等價的，當然這已經(jīng)被之前的「forrelation」問題所否定了（科學家近期證明了存在量子計算機能解決而經(jīng)典計算機不可能解決的問題）；還有人則持更加開放的態(tài)度，猜測仍然存在其它類型的量子算法可以轉(zhuǎn)換為相似計算復雜度的經(jīng)典算法。
機器之心的小伙伴怎么看呢？