【量子電腦沒落？】18歲台灣華僑的新突破，傳統電腦演算法的速度逼近量子電腦！
August 9, 2018
量子電腦一直被認為可取代傳統電腦，華盛頓大學准博士生台灣華僑唐（ Ewin Tang ）打破了這個印象。他開發了一種在傳統電腦上運行的推薦演算法，速度可媲美量子推薦演算法。推薦演算法看起來十分複雜，而「推薦」實指我們平時瀏覽電商平台（ E-commerce ) 和視頻網站時，推薦的相關產品和視頻。
他告訴 Quanta Magazine 雜誌「這曾是量子加速的最好例證，但現在不成立了」。畢業幾周後，唐在導師阿倫森（Scott Aaronson）的帶領下，在加州大學伯克利分校的量子計算會議上公佈了這個成果。打破量子電腦的傳說的他，將於今年九月，去華盛頓大學攻讀博士學位。
今年他只有 18 歲。
17歲的艱鉅作業
他的學習經歷頗有神童色彩，14歲時就連跳三級，直接進入得州大學奧斯汀分校就讀電腦和數學專業。
阿倫森在教授一堂量子信息課時，很快就發掘了唐的天賦。他交給唐一些需要獨立解決的問題，由他自己挑選。唐不太情願地選擇了「推薦問題」：「這看起來是個難題，但這已經是他給我的問題最簡單的一個了。」
以視頻網站為例，一個視頻網站的數據是所有用戶曾在上面瀏覽過的影片。據此，它要如何猜出你可能想要觀看的新影片。
這些數據等於一個網格，橫向是不同的視頻，縱向是不同的用戶，依據用戶對該視頻的喜好程度，可以在網格中填入相應的數值。一個聰明的演算法所要做的，就是快速而準確地找到其中的相似性，在空白的網格上填上數值。
學術界有量子推薦演算法的突破
2016 年，法國巴黎七大大學的 Iordanis Kerenidis 和新加坡優質學府南洋理工大學 Anupam Prakash 公佈了一種「量子推薦演算法」，比經典演算法有了幾何級數的上升。這種演算法並不企圖填滿整張空白網格，而是把用戶簡化成幾個大類別。
這個案例當時是激動人心的。此前只在很窄的應用問題上，以相當的速度應用量子演算法。量子推薦演算法則把「量子推薦演算法」推及到日常生活當中。
不過，這兩名計算機科學家只證明了量子推薦演算法要比已知的任何經典推薦演算法都要快得多，但卻不能證明這個世界上沒有更快的經典推薦演算法。
阿倫森給唐的作業，就是要補上這個漏洞，證明沒有比得上量子演算法的經典推薦演算法。
作業的前設本身就錯了
一開始，少年和阿倫森老師一樣，一心相信傳統推薦演算法不可能達到量子推薦系統的速度。可是，他的想法逐漸在改變。論文截稿時間已近，他對老師說： 我認為快速的傳統算法，是存在的，KP 算法中的量子相位估計，能找到替代品。
在量子推薦演算法的啟發下，唐發現他們所用的量子採樣技術完全可以在經典演算法里複製。具體來講，把用戶數量、產品數取對數後，計算時間就會大大減少。
阿倫森反覆驗證了這個經典演算法的正確性，確保唐不會出道即出錯。
最終，在加州的量子計算會議上，面對著一眾領域內的專家唐連做了兩場報告，並得到了普遍的認可，包括提出量子推薦演算法的Kerenidis。
他表示，唐的報告很成熟，他完全意識不到唐才18歲。下一步，唐的論文將接受正規的同行評議，以爭取正式發表。
量子計算受創，卻可啟發更好的經典算法
進入2018年，各大科技巨頭競爭相成量子計算的霸主。IBM 完成了 50 比特（Bit) 的原型機；谷歌發佈了研製高質量72比特量子電腦的計劃；微軟則宣布在5年內造出擁有100個拓撲( topology )比特的量子電腦。
不過，這不是個簡單比比特數多寡的競賽。一部分科學家對量子計算的前景仍持保守態度：在基礎量子理論層面上，學界還沒有解決量子比特的質量問題，即保持長時間、噪音少的量子糾纏。
在這個問題上，唐的研究可以算是重創了量子計算，減低了量子電腦的優勢。但不能否認的是，唐的經典算法是在量子算法的基礎上演化而來的，這點點亮了兩者之間的互動潛力。
正如阿倫森所說：「唐抹殺了Kerenidis 和Prakash的量子加速，但換個角度，唐的巨大成就是建立在他們的基礎上。要不是先有了他們的量子算法，唐永遠做不出他的經典算法。」
在其他問題上，我們也完全可以期待由量子算法啟發出更多更好的經典算法。這或許是發展量子計算的「曲線」發展的向案：就算短時間內造不出量子電腦，量子計算的思路本身就能創造價值。
以下是唐的論文網址。
Source: Cornell University Library
https://arxiv.org/abs/1807.04271
資料來源：http://fortuneinsight.com/web/posts/21420
