量子計算機被推翻提前被淘汰？ 科學家已經證實研究成果。在本月早些時候在網上發表的一篇論文中，18歲的Ewin Tang證明普通計算機可以解決一個重要的計算問題，其性能可能與量子計算機相當。
推薦算法是計算機領域中的一種重要算法，它可以用來為客戶可能喜歡的產品和服務提供建議。例如影視網站從海量數據中獲取到用戶數據，根據用戶過去喜歡或搜索過的影視內容，為用戶推薦與之相似的影視作品，而內容相似性的度量，是算法運用的關鍵。
我們可以將這些數據視為一個矩陣，橫向代表電影，豎向代表用戶，而網格中各點是某用戶對某電影的喜好程度的量化值。一個好的算法可以通過快速準確地識別電影和用戶之間的相似性，並填充矩陣中的空白以生成推薦。計算機科學家認為它是量子計算機上解決速度最快的也是最好的案例之一。 使其成為這些未來機器功能的重要驗證。現在唐的方案已經獲得了驗證。
2016年，計算機科學家Iordanis Kerenidis和Anupam Prakash發布了一種量子算法，該算法以比任何已知經典算法更快的速度解決推薦問題。他們通過簡化問題來實現這一量子加速：不是填寫整個矩陣並確定推薦的單一最佳產品，而是開發了一種將用戶分類為少數類別的方式 - 他們喜歡大片還是獨立電影？ - 並對現有數據進行抽樣，以便生成足夠好的建議。
在這之前，量子計算機解決某些問題比經典計算機有指數式加速優勢的例子已經存在，但這些問題都比較專門和單一，量子計算機的優勢有很大局限性。 Kerenidis和Prakash的研究結果令人興奮，因為這是一種具有普遍意義的算法，而且又有著人們非常關心的實際應用價值。
「據我所知，它是機器學習和大數據中的一個好例子，我們展示了量子計算機可以做一些我們仍然不知道如何用經典辦法解決的事情。」巴黎計算機基礎科學研究所的科學家Kerenidis說。
Kerenidis和Prakash證明了量子計算機能夠比任何已知算法以指數方式更快地解決推薦問題，但它們並不能證明快速經典算法不存在。因此，當Aaronson在2017年開始與Tang合作時，這就是他提出的問題 - 證明沒有快速的經典推薦算法，從而確認Kerenidis和Prakash的量子加速是真實的。
「在我看來，這似乎是一個重要的't'來完成這個故事，」Aaronson說，他當時認為沒有快速的經典算法存在。
Tang於2017年秋季開始工作，打算將推薦問題作為高級論文。幾個月來，唐掙扎著證明快速的經典算法是不可能的。隨著時間的推移，唐開始認為也許這樣的算法是可能的。
「我開始相信有一種快速的經典算法，但我無法向自己證明這一點，因為斯科特似乎認為沒有一種，而且他是權威，」唐說。
最後，隨著高級論文的最後期限結束，唐寫信給Aaronson並承認了一個越來越多的懷疑：「唐寫信給我說，實際上，'我認為有一種快速的經典算法'，」Aaronson說。
在整個春天，唐寫了結果並與Aaronson合作澄清證明中的一些步驟。 Tang發現的快速經典算法直接受到Kerenidis和Prakash兩年前發現的快速量子算法的啟發。唐表明，他們在算法中使用的那種量子採樣技術可以在經典環境中複製。與Kerenidis和Prakash的算法一樣，Tang的算法在多對數時間內運行 - 意味著計算時間與特徵的對數（如數據集中的用戶和產品的數量）進行縮放 - 並且比任何先前已知的經典算法指數化得快。
一旦Tang完成了算法，Aaronson希望在公開發布之前確定它是正確的。 「我仍然感到緊張，一旦唐在網上發表論文，如果這是錯的，那麼[唐'的職業生涯的第一篇大論文就會貶低，」亞倫森說。
Aaronson計劃於6月份參加加州大學伯克利分校的量子計算研討會。 該領域的許多大腕都將出現在那裡，包括Kerenidis和Prakash。 在官方會議結束後的幾天裡，Aaronson邀請Tang來伯克利非正式地介紹他的算法。
在6月18日和19日的早晨，唐先生做了兩次講座，同時向觀眾提出了問題。到四小時結束時，出現了一個共識：唐的經典算法似乎是正確的。然而，房間裡的許多人都沒有意識到演講者的年齡。 「我不知道Ewin是18歲，我當然沒有從談話中得到這個。對我來說，[Ewin]是一個正在進行非常成熟的談話的人，「Kerenidis說。該算法現在在發布之前面臨正式的同行評審。
對於量子計算，唐的結果是一個挫折。唐已經消除了量子優勢中最清晰，最好的例子之一。與此同時，唐的論文進一步證明了量子算法和經典算法研究之間富有成效的相互作用。
「唐正在殺死[Kerenidis和Prakash的]量子加速，但在另一種意義上，唐正在給予一個很大的改進，並在他們所做的基礎上進行。唐從未想出這種經典算法，但對於他們的量子算法，「Aaronson說。