量子计算与机器学习

费因曼在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量子位元。量子计算往机器学习的实际应用又迈进了一步。

量子计算逐渐切入机器学习领域这一个趋势让我对台湾发展机器学习有乐观的理由：机器学习毕竟只是处于萌芽阶段的新领域，后续还有一段很长且方向多变的路要走，譬如应用量子计算于神经网络学派的深度学习。一个快速发展的领域也许有阶段性的领先者，但是快速的技术发展也可能让先行者的优势转变成负担。台湾有从自己优势领域切入的窗口，但是不加入就永远没有机会。