量子計算與機器學習

費因曼在1982年於其著名的論文“Stimulating Physics with Computers”提出量子計算(quantum computation)的想法，原先是要解決用傳統電腦計算量子系統低效率的問題；提出這想法當時，只能算是理論學家心智的娛樂。David Deutsch與Richard Jozsa於1992年證明了在某些問題上量子計算比傳統計算有效率，這是量子計算的奠基之作。2年後，Peter Shor的質因數分解量子演算法(Shor’s algorithm)進一步展示了量子計算的威力。質因數分解看似只是純粹的數學問題，其實不然；我們每天用的通訊、提款、轉帳等的安全都得依賴公共密鑰基礎設施(PKI；Public Key Infrastructure)，而PKI的安全就是依賴大數的質因數分解不易。量子計算這就入塵世了。

1996年的Lov Grover’s algorithm讓量子計算與機器學習靠近了些。Lov Grover’s algorithm的一個應用是資料庫搜尋－這是一個在機器學習領域通用的演算需求。Lov Grover的量子演算法比傳統演算法速度有平方(quadratic)的改善。因為這優異的表現，量子計算被應用在支持向量機(support vector machine)－機器學習的五個重要學派之一(向量機屬於類比推理學派，從相似度判斷進行推論學習，其餘4學派分別是神經網路、符號理論、演化論、與貝氏定理學派)。2008年Aram Harrow、Avinatan Hassidim和Seth Lloyd提出了HHL演算法，這個演算法是針對對於n元線性連立方程式求解的問題，這也是機器學習常用的演算法之一。傳統計算時間正比於n的3次方，量子計算只需要對數n的時間。值得一提的是HHL演算法也被用來計算Google的網頁排名(PageRank)中的一些性質。2013年Seth Lloyd、Masoud Mohseni和Patrick Rebentrost提出了主成份分析(principal component analysis)方法，完成了量子支持向量機的最後一塊拼圖。

在過去1/4世紀中，人工智慧與量子計算這兩個原本獨立次學門的方向逐漸有交集，但距離實用還有一段距離，原因在於量子計算機的建構還有好一段路要走。加拿大量子計算機公司D-Wave最新的機型D-Wave 2000Q^TM只有2,000個量子位元，而且很多科學家質疑它不是真正的量子位元，充其量只能執行量子退火(quantum annealing)－一個取樣(sampling)的工具，在機器學習中可用於分類(classification)問題的監督學習(supervised learning)。5月NASA發表的論文結果顯示用量子計算機的量子退火取樣可以加快手寫數字的辨識，而且只用了940量子位元。量子計算往機器學習的實際應用又邁進了一步。

量子計算逐漸切入機器學習領域這一個趨勢讓我對台灣發展機器學習有樂觀的理由：機器學習畢竟只是處於萌芽階段的新領域，後續還有一段很長且方向多變的路要走，譬如應用量子計算於神經網路學派的深度學習。一個快速發展的領域也許有階段性的領先者，但是快速的技術發展也可能讓先行者的優勢轉變成負擔。台灣有從自己優勢領域切入的窗口，但是不加入就永遠沒有機會。