18歲華裔少年讓「量子計算領域的重大進展見鬼」!
年僅18歲的尤因·唐(Ewin Tang)已證明,典型計算機能夠與量子計算機幾乎一樣快地解決「推薦問題」。這個重大研究結果否定了量子計算機可大幅提速的最佳例子之一。
尤因?唐的近照
尤因?唐將在今年秋季進入研究生院。
圖片來源:Vivian Abagiu攝於得克薩斯大學奧斯汀分校
來自美國得克薩斯州的一名天才少年給量子計算界潑了一盆冷水。在本月早些時候發表於網上的一篇論文(https://arxiv.org/pdf/1807.04271.pdf)中,年僅18歲的尤因·唐(Ewin Tang)證明了普通計算機能解決一個重要的計算問題,而性能可能與量子計算機相當。
舉個最實際的例子,「推薦問題」涉及亞馬遜和Netflix等服務如何確定你可能想要嘗試哪些產品。計算機科學家們之前認為,這是最佳例子之一,證明了用量子計算機來解決要快得多,因而推薦問題成為證明這些未來機器強大功能的重要例子。現在唐否定了這個證明。
唐說:「這曾是證明量子計算機可大幅提速的最經典例子之一,現在再也立不住腳。」他在今天春季畢業於得克薩斯大學奧斯汀分校,秋季將攻讀華盛頓大學的博士學位。
唐在2014年14歲那年,直接跳過四到六年級後,入讀得克薩斯大學奧斯汀分校,主修數學和計算機科學。2017年春季,唐報名就讀量子計算領域的著名研究人員斯科特·阿倫森(Scott Aaronson)所教的量子信息課程。阿倫森認為唐是特別有才華的學生,主動表示願意在一個獨立研究項目當他的顧問。阿倫森扔給了唐幾個問題來選擇,包括推薦問題。唐有點不情願地選擇了推薦問題。
唐說:「我之所以猶豫不決,是因為我看到推薦問題的第一眼覺得這似乎是個難題,但這其實是他給我的最簡單的問題。」
推薦問題旨在為商家推薦用戶可能喜歡的產品。不妨以Netflix為例。它知道你看過哪些電影。它知道其他數百萬用戶觀看哪些電影。結合這些信息,你接下來可能想要觀看什麼電影?
你可以想像這些數據排列在巨大的網格或矩陣中,頂部列出了電影,一側列出了用戶,網格中各點的值量化了每個用戶是否喜歡每部電影或喜歡的程度。一種好的演算法會快速準確地識別電影和用戶之間的相似之處,填充矩陣中的空白,以此推薦電影。
2016年,約爾達尼斯?克倫尼迪斯(Iordanis Kerenidis)和阿努帕姆?普拉卡什(Anupam Prakash)這兩位計算機科學家發布了一種量子演算法,該演算法解決推薦問題的速度比任何已知的經典演算法都要快得多。他們實現這種速度的提升一方面得益於簡化問題:不是填寫整個矩陣、確定需要推薦的單一最佳產品,而是開發了一種將用戶分成少數類別的方法:他們喜歡大片還是獨立電影?然後對現有數據採樣,以便推薦的內容足夠合適。
巴黎計算機科學基礎研究所的計算機科學家克倫尼迪斯說:「在我看來,這是機器學習和大數據領域的首批例子之一,表明了量子計算機可以做一些我們仍然不知道如何用經典計算機來做的事情。」
克倫尼迪斯和普拉卡什證明了量子計算機能夠以遠超任何已知演算法的速度解決推薦問題,但他們並沒有證明不存在一種快速的經典演算法。因此,當阿倫森在2017年開始與唐合作時,這就是他提出的那個問題:證明沒有一種快速的經典推薦演算法,從而證實克倫尼迪斯和普拉卡什認為量子計算機可大幅提速的觀點屬實。
阿倫森產:「在我看來,這是故事的一個重要細節。」他當時認為,不存在快速的經典演算法。
唐於2017年秋季開始研究這項工作,打算將推薦問題作為高級論文課題。唐花了幾個月努力證明不可能存在快速的經典演算法。隨著時間的推移,唐開始認為可能存在這種一樣演算法。
唐說:「我開始相信有一種快速的經典演算法,但沒法向自己證明這一點,因為斯科特似乎認為沒有這樣的經典演算法,他可是權威人士。」
最後,隨著高級論文的最後期限漸漸臨近,唐寫信給阿倫森,承認自己越來越感到懷疑:「唐寫信跟我說『我認為有一種快速的經典演算法』,」阿倫森如是說。
在整個春季,唐都在撰寫研究結果,並與阿倫森一起闡清證明中的幾個步驟。唐發現的快速經典演算法直接受到克倫尼迪斯和普拉卡什兩年前發現的快速量子演算法的啟發。唐表明,他們在演算法中使用的那種量子採樣技術在經典環境中可以複製。與克倫尼迪斯和普拉卡什的演算法一樣,唐的演算法以多重對數時間運行,這意味著計算時間隨著特徵(如數據集中的用戶和產品數量)的對數而變化,而且比任何之前已知的經典演算法快得多。
一旦唐完成了演算法,阿倫森想要在公開發布之前確信結果是正確的。阿倫森說:「我仍然惴惴不安,一旦唐將論文放到網上,萬一結果是錯的,唐在其職業生涯上的第一篇重大論文就糗大了。」
阿倫森早就計劃6月份參加加州大學伯克利分校的量子計算研討會。這個領域的許多大腕都悉數到場,包括克倫尼迪斯和普拉卡什。阿倫森邀請唐前往伯克利,在正式會議結束後的幾天里非正式地介紹他的演算法。
在6月18日和19日這兩天早上,唐做了兩次講座,從容地回答了聽眾拋出來的問題。四小時過後,大家達成了一個共識:唐的經典演算法似乎是正確的。然而,在座的許多人沒有意識到這位演講者到底有多年輕。克倫尼迪斯說:「我不知道尤因才18歲,從談話中我絕對聽不出來。在我看來,尤因的談話顯得非常成熟。」該演算法現正接受發布之前的正式的同行評審。
對於量子計算界而言,唐的結果可謂是一記重拳,也可以說不是。唐否定了證明量子計算優勢的最清晰最典型的例子之一。與此同時,唐的論文進一步證明了量子演算法研究和經典演算法研究確實可以相互促進。
阿倫森說:「唐否定了克倫尼迪斯和普拉卡什認為量子計算機可大幅提速的觀點,但是從另一個意義上來說,唐做出了一次重大的改進,在他們的成果上更進一步。要不是他們倆的量子演算法,唐也許根本想不出這種經典演算法。」
TAG:智多趣 |