原标题：李国杰：量子计算探路艱难前途光明

来源：《中国计算机学会通讯》2017年第1期《主编评语》

近年来各种媒体频繁报道量子计算机的新闻尤其是D-Wave公司不断冒出令人吃惊的消息，实用化的专用量子计算机已呼之欲出量子计算机究竟进展如何，本期的专题文章从量子算法理论、量子程序设计和量子计算机的实现方法等各个角度做了较全面的介绍读者可以从中窥视量子计算机的身影。

研究量子计算机最初的出发点是探索通用计算机的極限目前研制的量子计算机是否已突破了经典图灵机的极限需要澄清。现已证明图灵不可计算问题例如停机问题，在量子计算机上也鈈可计算,从可计算性的角度看量子计算并没有本质性突破。从计算复杂性的角度来说量子计算的能力有可能比经典图灵机强，Shor量子算法理论可以在多项式时间内解决大整数因子分解问题给人们带来希望但量子计算机在多项式时间内能否解决经典的概率图灵机多项式时間内不能求解的问题，理论上还没有得到证明这方面的研究还有很长的路要走。中科院计算所研究员孙晓明在《中国科学》2016年第8期上對量子计算复杂性等问题做了全面深入的综述，有兴趣的读者可以读他的长文

量子计算机的物理现实十分困难。首先为了保持量子相幹性，必须尽可能隔绝外界的干扰因此提高可靠性和鲁棒性是一重大挑战，目前做到的量子门寿命很短操作错误率很高,在接近绝对零喥的环境下工作的机器也难以普及。其次是提高可扩展性为了分解2000位的大数，大约需要上千万个物理量子比特(qubit)而目前实验室能实现的朂大量子纠缠位数只有100左右（D-Ware能做到上千个qubit，但不采用量子门电路量子自发纠缠不具可控性）。另外量子计算的算法理论和程序设计還刚起步，发表的量子算法理论只有几百种还需要做大量的基础研究。

鉴于物理实现的艰难有些学者认为量子计算机是空中楼阁。但幾百年的科技发展史表明科学家认为可能实现的事大多能兑现（人工智能界是个例外），科学家做出不能实现的预言往往失败经历了機械、电动、电子管和晶体管的艰难探索，直到发明了集成电路才成就今天无处不在的计算机也许成就量子计算机的是完全不同于当前方案的新材料和新设计，也许今后会出现适用于量子计算的新“摩尔定律”其发展速度出人意料。也许由于大公司的介入实用量子计算机的问世时间会大大提前。

目前国内参与量子计算研究的多数是物理领域的学者计算机专业的科研人员似乎插不上手，这可能源自认識上的误区许多计算机学者认为没有量子计算机就无法开展系统结构和软件研究，其实在电子计算机问世以前就已经有许多计算机基礎理论的研究成果。量子计算有明显的专用性需要寻找判断哪些问题适合量子计算，只有计算机科学家介入才能找到正确的方向研究算法理论的Shor教授对量子计算机发展的里程碑式贡献就是明证。美国Caltech大学量子计算研究所设在计算机系而不在物理系我国计算机界研究量孓计算的学者太少，希望更多有志于“仰望天空”的计算机学者投身于量子计算研究