量子计算探路艰难前途光明

• 作者: 李国杰
• 来源期刊: 中国计算机学会通讯
• 年，卷（期）: 2017,（1）
• 所属期刊栏目: 主编评语
• 页码范围: 7
• 页数: 1页
• 语种: 中文

摘要

近年来各种媒体频繁报道量子计算机的新闻,尤其是D-Wave公司不断冒出令人吃惊的消息,实用化的专用量子计算机已呼之欲出.量子计算机究竟进展如何,本期的专题文章从量子算法、量子程序设计和量子计算机的实现方法等各个角度做了较全面的介绍,读者可以从中窥视量子计算机的身影. 研究量子计算机最初的出发点是探索通用计算机的极限.目前研制的量子计算机是否已突破了经典图灵机的极限需要澄清.现已证明图灵不可计算问题,例如停机问题,在量子计算机上也不可计算,从可计算性的角度看,量子计算并没有本质性突破.从计算复杂性的角度来说,量子计算的能力有可能比经典图灵机强,Shor量子算法可以在多项式时间内解决大整数因子分解问题给人们带来希望.但量子计算机在多项式时间内能否解决经典的概率图灵机多项式时间内不能求解的问题,理论上还没有得到证明,这方面的研究还有很长的路要走.中科院计算所研究员孙晓明在《中国科学》2016年第8期上,对量子计算复杂性等问题做了全面深入的综述,有兴趣的读者可以读他的长文.