---

https://tinyurl.com/ycj9bj5x 神童照片

量子電腦能為機器學習大幅加速？

不好意思，這件事的最佳證據：量子推薦系統，已被華盛頓大學準博士生 Ewin Tang「殺
死」。

他在量子電腦的啟發下，開發了一種在傳統電腦上運行的推薦演算法，與以前的推薦演算
法相比能實現指數級加速，媲美量子推薦演算法。

「這曾是量子加速的最強例證之一，現在它已經不復存在。」

打破量子電腦優越性的 Ewin，秋天即將去華盛頓大學讀博的 Ewin，不是你的同齡人。

他今年只有 18 歲。


2017 年春天，17 歲的少年 Ewin 正在德克薩斯大學奧斯汀讀大三。

他選了一門深奧的課程：量子信息。

這門課的老師，是德克薩斯大學奧斯汀分校量子信息中心主任斯科特· 阿倫森（Scott
Aaronson）教授。

阿倫森老師曾在 MIT 任教 9 年，2016 年秋天加入 UT 奧斯汀。這位 37 歲的教授，在
學術界稱得上青年才俊。

他看著少年，不知道是不是看見了自己 17 歲的影子，覺得這位少年天賦異禀，決定帶著
他做點研究。

於是，一堆課題擺在了少年面前。最後，他不大情願地選了推薦系統算法。

而「不情願」的理由，與 14 歲上大學、「天賦異禀」的學霸人物設定很不搭。

少年接受 Quanta Magazine 採訪時說：猶豫，是因為我看起來感覺它好像很難，但這已
經是他給我的課題裡最簡單的了。

推薦演算法，可能是機器學習技術應用中群眾基礎最好的一個。它早已經被各種 App 大
規模應用，每天為幾億人推薦著新聞、商品、歌曲。

如此司空見慣，為什麼學霸少年會覺得難？


課是量子訊息，導師是量子訊息中心主任，這個推薦算法課題，研究的自然是它和量子計
算的交叉。

推薦演算法之於量子訊息，約等於燈泡之於電力。

一直以來，量子電腦最深入人心的特徵是計算能力強悍，而它究竟能用來幹什麼，就超出
了群眾的認知範疇。

大家都說，它擅長分解龐大的數字，對加密解密有著巨大的作用。

但如果僅僅是密碼學，與傳統電腦能完成的任務相比就未免太狹窄了。更何況，要真正用
量子計算攻克密碼，還要等個 10 年左右。

當下真能證明量子電腦優越性的問題，寥寥無幾而且局限在非常狹窄的細分任務上。

直到 2016 年，一篇論文：Quantum Recommendation Systems，也就是量子推薦系統，終
於在一個大眾關心的問題上，證明了量子電腦的優越性。
論文  https://arxiv.org/abs/1603.08675

論文作者，是法國科學研究中心（CNRS）高級研究員 Iordanis Kerenidis 和南洋理工大
學的 Anupam Prakash。

阿倫森教授把他們的算法稱為 KP 算法，還說它堪稱量子電腦能為真實世界中的機器學習
提供指數級加速的最強證據之一。

推薦系統就像一個用戶× 產品構成的偏好矩陣。對於傳統的演算法來說，矩陣中所有
的偏好信息要用到，而 KP 算法，用一種叫做「量子相位估算」的方法從中抽樣。與眾多
傳統演算法相比，速度呈「指數級提升」。

Kerenidis 說，據他所知這是第一次有機器學習和大數據領域的例子，證明了量子電腦可
以完成傳統電腦上不可能的任務。

少年要研究的東西，就和這個 KP 算法有關。


2017 年秋天，Ewin 的研究作為本科畢業論文開工了。

一開始，少年和阿倫森老師一樣，一心相信傳統推薦演算法不可能達到量子推薦系統的速
度。

可是，他的想法逐漸在改變。

論文截稿時間已近，他對老師說： 我認為快速的傳統算法，是存在的，KP 算法中的量子
相位估計，能找到替代品。

有想法還不夠。少年證明了可以用傳統算法來替代量子相位估計，從一個用戶偏好矩陣中
隨機採樣，形成一個小矩陣。

在傳統的電腦上，同樣可以做出像 KP 算法一樣快的推薦系統。

和兩位前輩一樣，少年的算法的運行時間也是用戶和產品的多重對數。也就是說，計算時
間隨著特徵的對數而縮放。在推薦系統中，「特徵」就是用戶和等著推薦的產品。

經過自己反復計算，阿倫森老師反複檢查，兩人反復討論，他的最終成果出爐了。這篇
35 頁的論文題為 A quantum-inspired classical algorithm for recommendation
systems，一個量子計算啟發的推薦系統傳統算法，前不久在 arXiv 上公開了。

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

少年宣告， 與傳統電腦上的算法，也就是他自己剛剛開發的這個相比，KP 演算法實際上
並不能帶來指數級加速。

量子加速的最強證據之一被推翻了。



這就像是一場高規格的論文答辯會。少年做了兩場演講，和諸位觀眾唇槍舌劍問答 4 小
時。最終，大家終於達成共識：算法正確，「答辯」通過。

QuantaMagazine 還說，這篇論文後來還正式投遞到了某期刊或者會議，正在進行同行評
審，等待發表。

阿倫森老師在自己的博客上，把這篇論文稱為「a striking new result」，驚人的新成
果。

他說，唐同學殺死了（KP 算法的）量子加速。




驕人的研究背後的作者 Ewin Tang，是今年秋天即將入學華盛頓大學的博士生。

沒錯，18 歲的博士生。

在我們剛剛高中畢業暑期狂歡的時候，大神已經準備下個月的讀博項目了？

是的，而且是一路開掛——

根據德克薩斯大學阿靈頓分校（UT 阿靈頓）的校報報導，小學階段，少年一路連跳。
12 歲時，Ewin 實現了「質的跳躍」，成為校園裡最年輕的學生，主修數學和電腦科學了
。


當大部分同齡孩子還在小學數學習題中無法自拔時，少年已經師從著名量子電腦專家阿倫
森教授，鑽研起高數和量子信息學，還受到了「unusually talented」的讚譽。

14 歲的 Ewin，在大學期間，還發表了三篇……論文。


是誰啟發了幼年的 Ewin 學大學課程的？秉持著「神童的父母多半也很厲害」的傳統信仰
，量子位找尋到了少年的家庭訊息。果然——





真是甜蜜的苦惱呢~


--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.17.233
※ 文章代碼(AID): #1RPQYokx (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1533388978.A.BBB.html