天才少年Ewin Tang發現可替代量子計算的經典推薦算法

2020-12-05 電子發燒友

天才少年Ewin Tang發現可替代量子計算的經典推薦算法

李倩 發表於 2018-08-03 08:59:51

上個月初，發表在arXiv上的一篇論文引起了人們的興趣，作者是一位18歲的青少年——Ewin Tang。這位來自美國德克薩斯州的少年在論文中證明，用普通計算機就能解決重要的計算問題，並有可能達到和量子計算機相當的性能。

首先讓我們看看這篇論文的摘要：

這項應用放在實際中，可以用作我們熟知的推薦系統。各大電商公司和視頻網站經常向用戶推薦他們可能感興趣的產品。計算機科學家們將這一任務看作是這類問題的典型案例，如果在量子計算機上運行的會更快。所以很多人認為量子計算機是未來計算力的重要象徵。但現在，Tang的發現讓這一說法受到了質疑。

Tang說：「這是量子加速的最佳案例。」Tang今年春季畢業於德克薩斯州大學奧斯汀分校，並在秋季將成為華盛頓大學的博士生。

天才少年Ewin Tang

據2012年的一份報導，Ewin在12歲的時候就已經在德克薩斯州大學阿靈頓分校就就讀，他在10歲時就開始接收大學課程教育，並完成了20個小時的課程，包括微積分和微分方程，GPA達到4.0，是當時年紀最小的學生。

在私立學校學習完全部K-12數學課程後，Ewin就開始了大學知識學習，他在10歲時SAT成績就達到了1920分。除了學習大學課程，Ewin在課餘時間還會泡在他父親的實驗室裡，他的父親Liping Tang是一名生物工程教授。

新算法的發現

2014年，Tang連跳兩級進入了UT Austin的數學和計算機科學專業就讀。2017年春季，他接收了著名量子計算研究者Scot Aaronson教授的量子信息課程，Aaronson認為Tang天賦異稟，在研究上給予了他很多幫助，同時還讓他選擇想要研究的問題，包括推薦問題。

「我有點猶豫，因為推薦問題看起來很難，但已經是他給我的問題中最簡單的了，」Tang說。

推薦問題的核心是為用戶推薦他們可能喜歡的產品。關於這一研究領域，論智此前也做過相應報導：

2018年推薦系統入門指南

Netflix用機器學習為你推送專屬電視劇封面

Spotify揭秘：如何用算法實現歌曲精準推送

你可以想像數據在一個巨大的網格或者矩陣中，橫排代表所有電影，豎排代表觀眾，交叉點的值用數字表示觀眾喜歡電影的成都。一個好的算法能快速而準確地識別電影和用戶之間的相似性，從而生成推薦，並填補矩陣中的空白。

2016年，計算機科學家Iordanis Kerenidis和Anupam Prakash發表了一種量子算法，可以比任何經典算法都快速地解決推薦問題。他們將問題簡化：與此前只為了填滿矩陣並推薦最佳產品不同，他們開發了一種對用戶進行分類的方法——他們喜歡大片還是獨立小眾的電影？然後通過對現有數據採樣生成最佳推薦結果。

當時，量子計算機對推薦問題的貢獻非常少，大部分都是解決的很具體的問題。而二人的成果之所以令人激動是因為他們在現實人們關心的問題上證明量子計算機能做得比傳統方法更好。

Kerenidis表示：「在我看來，這是機器學習和大數據領域第一件只有量子計算機能完成的任務。」Kerenidis和Prakash證明了，量子計算機可以比任何經典算法都能更快地完成推薦算法，但是他們並沒有證明這種快速的經典算法不存在。所以2017年，當Aaronson和Tang共同研究時，他提出了這一想法，證明了確實沒有這樣一種經典推薦算法，所以確認了Kerenidis和Prakash提出的量子加速器是真實的。

2017年秋季，Tang開始他的研究，並將推薦問題作為它的論文主題。在幾個月的時間裡，Tang一直在努力證明上述那樣的快速經典算法是不可能存在的，但與此同時，他開始思考也許確實存在這樣一種算法呢？

「我有些猶豫了，但是Scott是權威。」Tang說道。但是隨著論文deadline臨近，Tang還是給Aaronson寫了封郵件：「我認為存在這樣一種快速的經典算法。」

接著，Tang和Aaronson開始努力證明這一存在，Tang發現的這種經典算法是直接收到了Kerenidis和Prakash二人提出的快速量子算法，Tang證明他們在算法中所用到的量子採樣技術可以複製到經典設置中。和Kerenidis和Prakash二人的算法類似，Tang的算法也是多對數規模，也就是說計算時間與特徵的對數成比例關係（例如數據集中的產品和用戶數量），同時這一算法比此前所知的經典算法都快。

Tang的論文發表前，Aaronson十分謹慎，因為一旦出現差錯，Tang的第一篇大paper會很影響他的事業。

六月，Aaronson在UC Berkeley舉辦了一場量子計算研討會，並邀請了Kerenidis和Prakash。會上，Tang對自己的發現做了展示，很多人對這一結果表示認同，同時，與會者都沒有意識到這位研究者如此年輕。

Aaronson表示：「Tang推翻了量子加速的成果，但是從另一個角度來說，Tang也為這一領域做出了巨大的貢獻。如果沒有前人對經典算法和量子算法的研究，就不會有今天的成果。」

打開APP閱讀更多精彩內容

聲明：本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人，不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用，如有內容圖片侵權或者其他問題，請聯繫本站作侵刪。 侵權投訴

相關焦點

  • 年僅18歲就要讀博,天才華裔少年發現可替代量子計算的經典推薦算法
    這位來自美國德克薩斯州的少年在論文中證明，用普通計算機就能解決重要的計算問題，並有可能達到和量子計算機相當的性能。首先讓我們看看這篇論文的摘要：這項應用放在實際中，可以用作我們熟知的推薦系統。各大電商公司和視頻網站經常向用戶推薦他們可能感興趣的產品。計算機科學家們將這一任務看作是這類問題的典型案例，如果在量子計算機上運行的會更快。
  • 18歲天才少年，再次顛覆量子計算，科學雜誌：他減慢量子算法進展
    在唐乙文開始選修量子信息這門課程前，他還發表過4篇論文，這都不是重點，重點是這些論文還是關於生物材料方面的。經典算法與量子力學比起傳統的算法，量子力學是一種新型的計算模式，它遵循的是量子力學的規律。我們知道，傳統的計算機是以我們熟悉的圖靈機為模型的。
  • 18歲天才華裔少年用一個經典算法,推翻量子加速神話!
    這一發現不僅推翻了兩位量子計算重量級人物的量子加速神話，而且證明了量子算法和經典算法研究之間存在富有成效的相互作用。在本月早些時候在網上發表的一篇論文中，18歲的Ewin Tang證明用普通計算機可以解決一個重要的計算問題，其性能表現可能與量子計算機相當。以最實際的問題「推薦問題」為例，這個問題中就涉及亞馬遜和Netflix等服務是怎樣確定用戶想要嘗試體驗哪些產品的。
  • 18歲華裔天才Ewin Tang榮獲福布斯30歲以下科學家30人
    福布斯30歲以下精英榜對Ewin Tang的推薦理由是，「將量子算法『去量子化』，允許常規計算機像量子計算機一樣快速地解決特定問題，這使她成為了科學界的頭條人物」。量子計算是計算機科學研究中最受矚目的領域之一，因為量子計算機在很多問題上均顯示出了超越經典計算機的優越性。
  • 18歲華裔少年顛覆量子加速優勢,推動量子算法經典化
    這位天才少年的驚人成就已在社交網絡中引發了激烈的討論。國內量子計算專家也對此事發表了不同觀點。如百度量子實驗室負責人段潤堯在朋友圈評論說，「這是有關經典推薦算法的非常有意思的進展。原先 Kerenidis 和 Prakash 證明了量子計算機能夠比任何已知算法以指數級的速度解決推薦問題，但他們並沒有證明快速的經典算法不存在。
  • 人物 | 18歲華裔少年顛覆量子加速優勢,推動量子算法經典化
    他開發了一種傳統計算上運行的推薦算法，與以前的推薦系統相比可以實現指數級加速，媲美量子推薦算法。以下是對 Quantamagazine 相關報導內容的編譯：一位來自德克薩斯州的少年將量子計算「拉下神壇」。
  • 十八歲華裔天才攜手「量子計算先驅」再次顛覆量子計算
    今年 8 月，剛剛年滿 18 歲的 Ewin Tang 證明了經典算法能以和量子計算機相近的速度解決推薦問題，這位天才少女（更正：不是少年）的驚人成就引來了媒體爭相報導，和人們的廣泛討論。在這一研究中，科學家們再次使用經典方式重構了此前被認為量子計算佔據優勢的算法。看來，量子計算方式可以帶來的優勢並沒有人們想像的那麼多。未來的超級計算機不一定是量子計算機，你覺得呢？
  • 18歲華裔博士顛覆量子計算,科學雜誌:他「殺死了」量子計算大發展
    他開發了一種新的可以在傳統計算機上運行並完成計算的推薦算法，這種算法比之前的推薦算法可以實現指數級別的加速。 而由於他開發的新算法的運行速度堪比量子算法，因此過去只能有量子計算機能完成的計算，如今普通的計算機也可以實現。
  • 18歲天才少年發表論文,「打臉」量子優勢驗證方法
    2017 年春，Tang 選了一門量子計算方向，由量子計算著名研究員 Scott Aaronson 教授所教授的量子信息課程。Aaronson 認為 Tang 是一位很有天賦的學生，給 Tang 提供了一個獨立研究項目機會，並親自擔當項目顧問。Aaronson 給 Tang 提供的研究機會有包括「推薦問題」在內的許多課題可選，而 Tang 當時則有點不情願地選擇了「推薦問題」課題。
  • 一個華裔量子計算的天才出現了
    可以在生物學上破解所有的結構，可以在軍事上瞬間預測對方飛彈運動軌跡，可以在網絡上即時破解密碼量子計算是如此全新的技術，以至於大家對此都了解的不夠，需要天才的不斷突破和領導大家往下面走。今天就是一個天才。
  • 18歲博士生顛覆量子計算，《科學》：他「殺了」量子計算的發展
    成為各國科學界都在努力發展的領域，美國就有一位華裔少年，他在量子力學領域上得出過驚人的發現，他是誰呢？唐乙文發現存在一種算法，能夠用來拒絕量子領域當中的推薦問題，經過好幾輪的答辯，唐乙文這才讓那些專家教授們信服。
  • 18歲少年用一個經典算法,推翻量子加速神話!
    「這曾經是量子加速計算的最明確的範例之一，不過現在已經不是了。」Ewin Tang說。 Ewin Tang在小學曾從四年級跳級至六年級，2014年，年僅14歲的他進入德克薩斯大學奧斯汀分校就讀，主修數學和計算機科學。2017年春，他選了量子計算方面的著名研究員Scott Aaronson講授的關於量子信息的課程。
  • 華裔18歲天才顛覆量子計算，科學雜誌：他減緩了量子算法的進展
    ——門捷列夫說到天才，很多人會想到智商超群的人，但是其實許多智商超群的人，過了特定的年齡階段，沒有去豐富自己的知識，終究也會變成普通人，華裔少年唐乙文就是一個智商超群的人，2000年出生，18歲的他被稱為天才，顛覆了量子計算，科學雜誌採訪他的時候，曾經寫道：他減緩了量子算法的進展。
  • 18歲博士顛覆量子計算，科學雜誌：他「殺死」量子計算的發展
    前不久，量子計算在「推薦問題」上被一位年僅18歲的華裔少年拉下了「神壇」，而這次的「贏家」卻是長期以來在許多方面一直處於劣勢地位的傳統計算機，這次的「變革」無疑是給一直佔據主導的量子計算以「當頭一棒」。何為量子計算？它和傳統計算又有何區別？量子計算是遵循量子力學規律調控量子信息單元進行計算，而傳統計算機，其理論模型是通用圖靈機。
  • 18歲華裔準博士生,「殺死了」量子計算大進展
    不好意思，這件事的最佳證據：量子推薦系統，已被華盛頓大學準博士生Ewin Tang「殺死」。他在量子計算的啟發下，開發了一種在傳統計算機上運行的推薦算法，與以前的推薦系統相比能實現指數級加速，媲美量子推薦算法。「這曾是量子加速的最強例證之一，現在它已經不復存在。」
  • 18歲僅華裔博士,顛覆量子計算,科學雜誌給出驚人觀念
    什麼是量子計算：量子計算是一種遵循量子力學規律調控量子信息單元進行計算的新型計算模式。在理解量子計算的概念時，通常將它與經典計算相比較。 少年強則國強 計算機的這優越性就在前不久，被一位18歲的華裔博士的研究成果打破了，他開發了一種新的可以在傳統計算機上運行並完成計算的推薦算法
  • 徐令予:18歲華裔少年挑落量子霸權
    【文/ 觀察者網專欄作者 徐令予】 量子計算的一個重要成果被一個18歲少年推翻。 自古英雄出少年！18歲的美國德克薩斯州華裔少年Ewin Tang的論文證明，經典計算機幾乎可以像量子計算機一樣快速地解決「推薦問題」。量子加速（又稱量子霸權）的一個最佳案例如今卻被拉下了神壇[1]。
  • 深度學習量子退火量子計算N種算法
    蒙特卡洛算法：即採樣越多，越近似最優解。換言之，儘量找好的，但不保證是最好的.視頻又例舉了比目前經典計算強大得多的量子算法，如：Shor 算法|詳見|量子計算🔴碾壓經典密碼體系？|和Grover 算法。前者用於質數分解大數字（典型應用於加解密領域），後者用於搜索海量的資料庫。
  • 非凡的20後華裔天才少年科學家
    由於她開發了使普通計算機可以進行過去只能由量子計算機完成計算的算法，她被《福布斯》雜誌評價為當今30位30歲以下的傑出科學人物之一。她提出這一算法時，年齡還不到20歲，是一位年僅18歲的碩士。早期生活唐是一個從小就天賦異稟的科研天才，14歲時直接跳過高中而被錄取奧斯汀德克薩斯大學。
  • 18歲華裔天才顛覆量子計算，《科學》他「殺了」量子計算的發展
    這是一個18歲的華裔天才少年，他雖是領域之外的人，卻依靠著自己的知識，顛覆了很多人對量子計算的認知，連著名的《科學》雜誌都評論道：他「殺了」量子計算的發展。這個年紀輕輕的天才少年便是唐乙文。在對這個問題研究的時候，唐乙文在其中有了新的發現，幾個月的研究讓他意識到關於這個問題應該存在著一種快速的算法來解決問題，但是這種想法與他的老師產生了分歧，老師認為這個仿佛客觀上並不存在。