Major quantum computing advance made obsolete by teenager (2018) | Hacker News
LinkMajor quantum computing advance made obsolete by teenager
https://www.quantamagazine.org/major-quantum-computing-advance-made-obsolete-by-teenager-20180713/
📌
Summary:
本文介紹了德州一名 18 歲少年 Ewin Tang 推翻量子電腦在推薦系統問題上優勢的重要發現。過去，推薦系統被視為量子電腦可實現指數級加速的典型問題，而這也是量子計算優勢的經典例證之一。Tang 在 2017 年開始研究此問題，最初試圖證明不存在快速的經典演算法，但後來反而在量子演算法啟發下，成功提出了一個多項式對數時間（polylogarithmic time）且遠快於之前已知經典演算法的全新經典演算法，幾乎達到量子演算法的效能。這項成果由知名量子計算研究者 Scott Aaronson 指導，並在同儕評審前的研討會上獲得專家認可。結果表明，部分被認為只有量子電腦能解決的問題，其實在經典電腦上也能有效處理，這一發現不僅打破了量子計算領域最確鑿的優勢案例，也彰顯了量子與經典算法研究的相互啟發與促進作用。Tang 的突破同時提醒我們，量子計算的潛力雖大，但部分標榜的指數加速仍需仔細驗證，無疑將促進現代計算理論與應用的更深入發展。
🎯
Key Points:
★ 問題背景：推薦問題是如 Netflix、Amazon 等透過用戶過去行為，利用矩陣填補（matrix completion）技術預測用戶偏好的實務問題，曾被視為能體現量子演算法指數級速度優勢的重要場域。
→ 2016 年，Kerenidis 與 Prakash 提出量子推薦演算法，能將問題簡化為以類別羣組進行取樣，極速生成「足夠好」的推薦結果。
★ Tang 的突破：受指導教授 Aaronson 啟發嘗試證明不存在快速經典演算法，卻意外發現可借鑑量子演算法中的取樣技術，成功設計出一套多項式對數時間的經典演算法，速度與量子方法接近，遠超過先前所有經典方法。
★ 研究過程：Tang 自 2017 年開始著手研究，經歷多次挫敗後才逐漸找到新思路；2018 年春季完成論文草稿，參加加州大學柏克萊量子計算研討會，經多位頂尖學者審核，普遍認可其解法有效。
★ 重要意義：此結果表明量子計算的指數速度優勢並非無懈可擊，部份標榜量子專屬的加速案例，經重新審視後可透過經典演算法模擬；同時也說明經典和量子計算領域間的交叉研究能產生創新，互為推手。
★ 人物背景：Tang 14 歲就讀德州大學奧斯汀分校，畢業於數學與計算機科學系，曾跳過小學多個年級，是極具潛力的年輕研究者。
🔖
Keywords:
#量子計算 Quantum_Computing
#推薦系統 Recommendation_System
#經典演算法 Classical_Algorithm
#量子加速 Quantum_Speedup
#Ewin_Tang
Hublai (charismatic megafauna)
卡拉今天看了什麼