Ewin Tang, PhD Student, University of Washington [1]

Ewin Tang 14歲就讀於德州奧斯汀分校，主修數學與計算機科學，在量子信息中心（UTQIC）跟隨Scott Aaronson研究量子計算。2018年秋季，Ewin Tang開始在華盛頓大學跟隨James Lee攻讀理論計算機科學博士。福布斯30歲以下精英榜對Ewin Tang的推薦理由是，「將量子演算法『去量子化』，允許常規計算機像量子計算機一樣快速地解決特定問題，這使她成為了科學界的頭條人物」。

量子計算是計算機科學研究中最受矚目的領域之一，因為量子計算機在很多問題上均顯示出了超越經典計算機的優越性。例如快速分解質因數的Shor演算法，讓量子計算機具有潛力破解已被廣泛使用的公開密鑰加密演算法（RSA加密）；高效求解線性系統的HHL演算法，則在機器學習等領域具有眾多應用。

推薦系統問題就是量子計算機對於經典計算機可能具有優勢的一個問題。在Ewin Tang於奧斯汀量子信息中心做研究時，Scott Aaronson希望她能夠嚴格地證明，不存在任何經典演算法可以在推薦問題上媲美量子演算法，幾乎所有科學家都相信這一點。然而，Ewin Tang在量子演算法的啟發下，利用採樣方法提出了一個「去量子化」的經典演算法，不但比已知的所有經典演算法都快，還達到了量子演算法的複雜度。Ewin Tang的結果在理論計算機領域無異於一場「地震」，一方面人們知道了經典計算機的能力比人們想像中更強大，另一方面也一定程度上削弱了量子計算機的意義。「Ewin Tang tried to ruin us.」一位加拿大的量子計算科學家開玩笑說到。

Quantum Computing Memes for QMA-Complete Teens Fig.1.04 [2]

隨後，Ewin Tang又連續地證明了，數據科學裡的主成分分析問題，和低秩線性系統求逆問題，都存在量子啟發下的經典演算法，可以和量子演算法一樣高效。Ewin Tang的結果也引起了許多科學家的跟隨，已經有其他研究者運用「Tang方法」，證明了類似的問題下也存在著「去量子化」的經典演算法。Ewin Tang毫無疑問地成為了科學家最受矚目的新星之一，也成為了其他量子計算科學家「又愛又恨」的人物，儘管她現在僅僅18歲。

Quantum Computing Memes for QMA-Complete Teens Fig.1.22 [2]

Ewin Tang的結果可能會引起人們對量子計算的擔憂，但這不會使量子計算失去用武之地。一方面，量子演算法可以啟發人們得到「去量子化」的快速經典演算法，這本身就體現了量子計算的價值。另一方面，許多量子演算法已經被嚴格地證明是「安全」的，不會被Ewin Tang「破壞」。例如高效求解線性系統的HHL演算法是不存在經典演算法可以逼近的，而「Tang方法」需要低秩矩陣假設。正如Ewin Tang在推特上說，「我們已經接近於在機器學習找到經典計算機和量子計算機能力之間的分界線。」

阿里達摩院量子實驗室（AQL）主任施堯耘認為，量子和經典計算不斷相互超越會成為常態，相信未來還會有更多Ewin Tang的例子出現。

參考文獻：

[1] Forbes 30 under 30: 2019

[2] Quantum Computing Memes for QMA-Complete Teens

編輯：蜜汁醬

推薦閱讀：