摘要： 今年诺贝尔物理奖有关“量子计算”，中国成功发射了“墨子号”量子卫星，阿里、谷歌、微软、IBM等国际巨头公司都突然加速进军这一原本属于“自然科学”研究的领域……百年量子理论风云沉淀，一朝爆发。

量子卫星“墨子号”在酒泉卫星发射中心成功升空。 （拍摄：Reuters/China Daily）

钛媒体注：读完下面这篇文章（全文15000字）要花费的时间可能要比我们预计的 10min 还要长，但我们必须强烈推荐给你。

几天前揭晓的诺贝尔物理学奖，颁给了美国普林斯顿大学和布朗大学的两名学者，他们在20世纪70、80年代把拓扑（Topology）这个数学概念引入物理学，做了“物质拓扑相与拓扑相转变”方面的理论研究，简言之就是研究物质的奇异状态。诺贝尔组委会把电子学和超导体领域的发展归功于他们，并称“或将有助于未来量子计算机的发展”。

今年在整个前沿技术领域，“量子计算”出现的频率都特别高，这个过去仅在学术圈讨论的话题，开始频频进入企业圈，阿里巴巴就是最早宣称要进入“量子研究”领域的中国公司。而这并不偶然，自动汽车、自动驾驶、脑机交互、自然语言处理乃至线上广告、搜索引擎、推荐系统等都是机器学习的热门领域，从这一点来说的话，我们可以毫不夸张地说，量子计算实际上决定了包括特斯拉、Google、微软、Amazon、Facebook等公司在未来的发展方向和趋势。

什么是量子计算，以及它的革命性在哪里？作为一直最具“技术信仰”的媒体，钛媒体「特稿组」历时数月，深度访问国内外多位“量子计算”领域权威，也经过认真研究和梳理，将这世纪级的问题说一说：

2016年8月16日，北京时间凌晨1时40分。

中国的长征号系列火箭在酒泉卫星发射中心刚刚成功完成了它的第234次发射任务，这一次，它搭载的是“墨子号”量子实验科学卫星（QUESS，Quantum Experiments at Space Scale），这是世界上第一颗量子卫星，也是人类首次通过卫星实现地球和外太空之间的通信。

《纽约时报》（The New York Times）这样评价墨子号的意义：这是中国为争取站在量子研究最前沿而迈出的重要一步。

此时，距离我国量子卫星正式立项也只过去了不到5年而已，距离潘建伟在2003年提出发射量子卫星仅仅过去了13年时间，距离潘建伟回到国内建立起了中国第一个操控光子的量子属性的实验室只有15年。

而查尔斯·本内特（Charles Bennett）和吉尔斯·巴撒德（Gilles Brassard）在1984年提出第一份量子密钥分发协议——即BB84协议——以及1948年克劳德·香农（Claude Elwood Shannon）建立现代信息理论则是仅仅是几十年前的时间。

如果说香农用数学定义了信息的概念，那么 BB84协议向大家展示了量子理论应用到通信中的广阔前景和巨大想象力，信息收发者通过量子频道设定密钥，而基于测不准原理，任何觊觎信息的窃听者都会破坏到数据使得收发双方发现，这就保证了没有任何人能够在不被当事人发现的情况下窃取信息。

这就是量子通信的基础和最大优势，利用量子频道的超高安全性和信息容量、传输速度上的优势来接发信息，这正是量子计算在现实世界中最具实践场景、最具操作可行性的应用之一。

事实上，直到30多年前，费曼才提出量子计算机的设想，而直到100多年前，在解决黑体辐射问题的过程中，普朗克发现了辐射量子化的现象，他假设能量只能在微小、各异、相互远离的能量包中进行释放或吸收，才第一次提出了“量子”的概念。在此基础上经过后续半个多世纪的发展，量子理论发扬光大，它与经典物理理论有着5个显著不同的特性：

非决定论（indeterminism）

在牛顿体系中，只要知道观测对象的初始位置和速度，就能预测它的轨迹，然而，在量子理论中，唯一能预测的只有可能性。

量子干涉（interference）

在波理论中，当两个相干（coherent）的波源叠加时变产生干涉，而在量子理论中，即使单粒子也能显示出这样的特性，因此，量子干涉使得波粒二象性存在所有物质之中。

测不准（uncertainty）

这是量子理论的核心，亦即我们无法同时了解到量子的位置和动量，而一旦对例子进行测量，则又会失去这些信息。

量子叠加（superposition）

一个量子可以同时处于两种允许状态的线性叠加状态，这意味着一个量子可以同时处于这里或那里，在与外部环境发生关系的过程中，量子极容易丧失这一特性，而叠加态又是量子计算和量子通信的核心目标。

量子纠缠（entanglement）

意指同时拥有多个量子的强量子关联，1935年，爱因斯坦等人提出了 EPR 悖论来质疑量子理论的完备性，并试图以定域性隐变理论来替代量子理论，但是，1964年，贝尔不等式证明任何满足 RPR 假设的两个粒子经典关联必然在一定数量以下，而两个纠缠态的量子并不符合此不等式，因此，量子纠缠无法用任何经典关联进行解释，而只能是一种罕有的量子世界现象。

在量子理论发展的100多年时间里，我们将会看到围绕着这些难以捉摸的现象和概念，那些在人类历史上数一数二的天才们殚精竭虑为捍卫自己的观点而相互颉颃，而在二战以后，量子理论的这些特性又是如何帮助现代的科学家们建立新的算法和应用、如何利用量子通信、量子计算机等量子计算去想象世界的另一种可能性。

在历史上，从来没有一个理论像量子力学这样如此深远地改变了世界的面貌，也从来没有一门技术能像量子通信和量子计算这样给予人类的未来如此无尽的想象力。

直至1989年，蒂姆·伯纳斯·李（Tim Berners-Lee）才提出了“万维网”（World Wide Web）的理念，因特网的最早雏形 ARPANET 在1969年就出现了，但直到1981年 CSNET 的建立以及次年 TCP/IP 协议的标准化，它才真正突飞猛进地发展起来。

直到1994年，世界上第一台严格意义上的智能手机才问世，1993年时，互联网历史上最原始的搜索引擎才诞生，而在1956年之前，甚至没有人专门研究人工智能。

智能手机和互联网的发展经验告诉我们，技术或产品并不一定要依靠很长时间的积累和沉淀才能大获成功，符合市场和消费者需求的必然成功。而人工智能的故事同时也启示我们，突破技术本身的瓶颈究竟会是多么艰难而痛苦的漫长过程。

在横跨过往3个世纪的时间里，量子计算的发展轨迹不只是关于科学和技术的历史，不只是关于科学家的历史，不只是历史拼图的一部分，从某种意义上来说，反而是历史本身的轨迹构成了它的发展和进化。

先声

1820年4月21日夜，安徒生的密友、历史上首次制作了铝、被丹麦用来命名本国第一颗人造卫星的物理学家奥斯特（Hans Christian rsted）在实验过程中无意间发现，当电流开启时，离导线太近的指南针的磁针就会偏转，偏转的程度轻微到在场的几乎所有人都没有注意到这个小小的细节，但是，奥斯特此时已经意识到，这充满偶然性的不期而遇的发现将电击一般震惊世界。

和助手进行电磁实验的奥斯特。 （Louis Figuier: Les merveilles de la science, ou Description populaire des inventions modernes (1867), page 713）

抓住这瞬间的一次机会，仅仅3个月后，奥斯特就用拉丁文向全欧洲的大学投送了一篇4页的报告《基于磁针的电流效应之实验》（Experimenta circa effecturn conflictus electrici in acum magneticam）。一个药剂师的儿子就此颠覆了整个物理学的发展。

随后安培（André-Marie Ampère）、法拉第（Michael Faraday）这些伟大的天才一直没有放弃探究电磁背后的物理学的努力。到1831年，法拉第终于成功地使得机器驱动和磁力共同作用产生电力。而就在这一年，麦克斯韦（James Clerk Maxwell）也在爱丁堡出生。

安培的电磁理论是建立在他认为电荷间存在超距作用力的基础上的，而法拉第则坚持近距作用，然而，在亨利·卡文迪士（Henry Cavendish）及夏尔·库伦（Charles Augustin de Coulomb）等人的研究下，远距作用被成功量化，并能成功解释当时的大部分物理现象。

在这样的背景下，法拉第的力线、电紧张态(electrotonic state)等概念在当时的物理学界并没有受到多少重视和关注。然而天才的麦克斯韦很快就意识到法拉第思想的重要性，并试图通过数学的方法进一步探索出电磁背后的关系。

1865年，年轻的麦克斯韦在一次会议上宣读了他的论文《电磁场的动态理论》（A Dynamical Theory of the Electromagnetic Field），在其中，他完全抛弃了牛顿的力学模型，完整地提出了电磁场理论，并率先提出了“场”（field）的概念，此外，麦克斯韦提出了电磁场的普遍方程组，其中包括20个方程式及20个变量，直到1890年，赫兹才给出了只有4个矢量方程的简化方程组。

从某种角度上来说，正是麦克斯韦思想及其天才的方程组的漫长验证过程促进了后来人对量子力学的理解和接受。

首先，两派都不约而同地在数学语言上投入了大量的天赋和精力并取得了非凡的成就，就如麦克斯韦放弃了用力学模型来描述他的电磁场才使得其理论开辟出新的理论和应用光辉一样，量子力学则抛弃了使用文字而转向几何学来描述自然世界和物理。

其次，量子力学的物理学家们和麦克斯韦在理论体系的结构上有着更深的相似，他们把宇宙分为两层，第一层包括薛定谔的函数方程、海森堡矩阵及狄拉克的矢态，这一层能够被精确计算却无法被观察，第二层则涵盖辐射偏振强度、量子自旋等，它们无法被精确计算却可以观察。

麦克斯韦和量子力学一样认为自然寓于第一层的纯粹数学世界之中，而人类则存在于第二层的力学世界里，因此，我们无法用第二层的语言去描述自然，而只有数学语言可以做到这一点。

物理学家弗里曼·戴森（Freeman Dyson）这样评价麦克斯韦的成就：“麦克斯韦理论的最大重要性并不只是直接把解释和统一电磁现象，而在于提供了20世纪所有伟大物理发现的原型，这些伟大发现是爱因斯坦的相对论，是量子力学。”

1879年，麦克斯韦逝世，60年之后，那群意识到他的物理思想中的天才光辉的天才物理学家们——他们是薛定谔（Erwin Schr?dinger），是海森堡（Werner Karl Heisenberg），是狄拉克（Paul Dirac）——就如创世神一般开辟出了量子力学的新世纪。

自新世界

我可以断言没人懂量子力学。

——理查德·费曼（Richard Feynman）

普朗克提出“能量子” （Energieelement） 的概念，其后又将a此 表述修正为“量子”。

1874年，普朗克（Max Planck）向自己的导师求教研究方向，后者告诉他，物理学领域已经没有可发现的了，剩下的不过就是补窟窿而已。显然，包括这位导师在内的大多数人都已经满足于此时此刻的物理学规则阐释下的世界，他们并没有意识到，一场天翻地覆的新变革将在随后的世纪里如暴风骤雨一般袭来。

此时的历史社会发展使得钢铁、化工工业获得了突飞猛进的大发展，与此同时，城市照明等基础设施工程也热火朝天，而这些都对辐射强度和热度之间的关系提出了进一步的要求，于是，科学家们对热辐射的研究日趋深入，来自德国帝国技术物理研究所（Physikalisch-Technischen Reichsanstalt）的物理学家威廉·维恩（Wilhelm Wien）在1896年提出了维恩公式。

最初，普朗克仅仅是认为维恩的推导过程不够严密而试图通过更细致严谨的方式予以修正，然而，到了1899年，一系列进一步的实验得出的结果显示，这个公式只有在波长较短温度较低时才符合实验结果，同样是在这一年，约翰·斯特拉特（John William Strutt）提出了他的在高温公式——1905年，物理学家金斯（James Hopwood Jeans）修正了公式的一个错误，这就是日后的瑞利-金斯公式。

然而这个公式虽然在低频上与实验结果相符，但是随着辐射的能量随着频率的增加而无限增大，这就是标志着经典物理学陷入困境的保罗·埃伦费斯特（Paul Ehrenfest）所谓的“紫外灾变”（ultraviolet catastrophe）。

进入20世纪的第一年，英国物理学家威廉·汤姆逊（William Thomson）在《笼罩热与光的动态理论的十九世纪乌云》（Nineteenth-Century Clouds over the Dynamical Theory of Heat and Light）的演讲里的开场白是这样的：“将热与光认定是一种运动方式的动态理论的美好与清晰，如今却笼罩在两朵乌云之中。”

在时年76岁的这位开尔文勋爵看来，一朵乌云是阿尔伯特·迈克尔逊（Albert Abraham Michelson）和爱德华·莫雷（Edward Morley）为了验证以太存在与否而进行的实验的失败，而另一朵即是“紫外灾变”。

然而，新世纪的这代人自然不甘于在巨人肩膀上的前辈们的阴影中画地为牢，于是，一场新的革命风潮逐渐席卷物理学界，而且它来得异常迅疾。

这一年的10月，在不到12天的时间里，普朗克就和海因里希·鲁本斯（Heinrich Rubens）共同合作提出了新的辐射公式，所有的实验结果都证明了这个公式的正确，但是，他对此并不满足。是年12月14日，在反复思考过程中终于放弃了热力学第二定律的普朗克在德国物理学会上宣读了他的论文《关于正常光谱的能量分布定律的理论》（Zur Theorie des Gesetzes der Energieverteilung im Normalspectrum）。

在里面，普朗克提出了“能量子”（Energieelement）的概念，其后又将此表述修正为“量子”（Elementarquantum），在里面，普朗克提出了后来被普朗克常数的作用量子 h：

我们采取这种看法，认为 E 是由数目有限的相等部分组成的，因此我们应用了自然常量 ：

在这个新世纪元年的最后时间里，量子力学如惊雷一般倏忽现世，在看上去巍巍然的物理殿堂的角落暗暗埋下在日后一个世纪里将逐渐倾覆经典物理世界体系的引信。

这一年，21岁的爱因斯坦（Albert Einstein）刚刚在苏黎世联邦理工学院获得了教师文凭，这时距离他写出重写物理历史的论文还有5年的时间。

随着1905年讨论光量子、确定原子存在、提出狭义相对论的4篇论文的发布，小小的专利局文员爱因斯坦一举成为整个物理学界的焦点，次年，他将普朗克的量子假说应用于固体比热研究，到了1910年2月，沃尔瑟·能斯特（Walther Hermann Nernst）发布了自己的实验结果，证明了爱因斯坦理论的正确。

1911年第一次索尔维会议上的与会者合影，拍摄于布鲁塞尔的大都会酒店。

这是量子理论首次成功地解释了物理问题，于是自然而然地引起了物理界的重视，到1911年，在跨国化工集团索尔维的赞助下，第一次索尔维会议在比利时召开，包括普朗克、亨德里克·洛伦兹（Hendrik Antoon Lorentz）、居里夫人（Marie Skłodowska Curie）、庞加莱（Jules Henri Poincaré）、阿诺德·索末菲（Arnold Johannes Wilhelm Sommerfeld）及爱因斯坦等在内的物理学家都出席了这次会议，而此次会议讨论的主题就是量子辐射理论。

虽然爆发欧洲战争的氛围越来越紧迫，但是，量子理论的研究不仅没有受到外部环境的影响，反而取得了更大的进展，它恰如星星之火一般逐渐点燃了整个欧洲的物理学家对世界的天才认识和分析。

1913年，玻尔（Niels Henrik David Bohr）发表了题为《原子构造和份子构造》（On the Constitution of Atoms and Molecules）的3篇论文，引入了普朗克常数将量子假说和原子理论结合起来，建立原子模型，同时，玻尔阐明了光谱的发射和吸收，并且成功地解释了元素的周期表，使量子理论取得了重大进展。

但是，玻尔的理论本身是建立在将量子理论和经典力学结合基础上的结果，本身依然存在着不少缺陷，它不仅无法计算光谱的强度和结构，甚至也无法解释氨原子光谱。

随着在解答现象方面的困难越来越大，玻尔等物理学家陷入到经典物理和量子物理两者之间的矛盾境地，到了20年代中期，这种矛盾越来越突出。回忆起当时的情形，泡利（Wolfgang Ernst Pauli）的态度反应了物理界当时的困境：“那时候，物理学又陷入进退维谷的境地，无论如何对我来说那都太难了，我多希望我是一个喜剧演员或其他什么的，要是从来没听说过物理就好了。”

但是，在玻尔、泡利等或依然顽固坚守自己的学说或无能为力的同时，另外一群人却开始另辟蹊径，继续大刀阔斧地修正完善量子理论。

1923年，法国物理学家路易·德布罗意（Louis de Broglie）指出实物粒子具有波粒二象性，并提出了“相波”（phase wave）的概念，这启发了薛定谔使后者在3年之后开创了波动力学的新道路。1924年，泡利提出了不相容原理，到了下一年，荷兰物理学家埃伦费斯特的两名学生乌伦贝克（George Eugene Uhlenbeck）和高斯米特（Samuel Goudsmit）则在此基础上提出了电子自旋的大胆设想。

在1925年，海森堡发表了论文《关于量子—对运动学和动力学关系的理论性重构》（über quantentheoretische Umdeutung kinematischer und mechanischer Beziehungen），矩阵力学横空出世。从此，量子力学真正第一次登上了物理学历史的宏大舞台并一发不可收成为这个舞台最耀眼的明星。

两年之后，海森堡提出了测不准原理，同一年，玻尔则提出了互补原理，他认为之前经典物理学中互相排斥的性质在量子力学中可能互相补充，波粒二象性乃至测不准原理都是量子力学这一特性的体现。

1927年的索尔维会议集合了当时为止人类历史上最天才的物理学家。（ Photograph by Benjamin Couprie, Institut International de Physique Solvay, Brussels, Belgium）

1927年，第五次索尔维会议召开，主题本来定为“电子和光子”，但是在大会上，玻尔、海森堡、德布罗意和爱因斯坦围绕着导波理论、矩阵力学等量子力学议题展开了争辩，爱因斯坦暗示自己反对玻尔等人对量子力学的阐释，而玻尔不甘示弱地进行了反驳，最终，双方谁也没有真正说服对方。

3年之后，在第六次索尔维会议上，爱因斯坦首先用一个光子箱实验来质疑测不准定理，直到第二天，玻尔等人才找出爱因斯坦论点中的漏洞，有力地反击了后者，使爱因斯坦不得承认测不准原理的合理性，事实上，这也意味着爱因斯坦短暂承认了早在1927年的会议上玻恩、海森堡就一再强调的观点，即量子力学是一种完备的理论。

终其一生，爱因斯坦始终对量子力学持怀疑态度。然而，就像爱因斯坦自己说的那样，他从来不相信上帝，在爱因斯坦心中，唯一能称得上宗教的只有对能够被科学所解释的世界结构的无限崇敬。

关于量子力学的争论并没有就此停止，从1935年和1949年，以爱因斯坦为代表的EPR一派和玻尔的哥本哈根学派先后进行了3次论战，随着量子力学的发展，事实证明，无论是玻尔及哥本哈根学派还是爱因斯坦，谁都没有完全输掉这场量子力学的论战，而谁也没有彻底赢下它，正是这样的激辩以及对科学观的坚持和态度推动着量子力学这门学科焕发出最蓬勃、最具生命力的光彩。

在量子力学争论如火如荼的同时，战火也蔓延世界，战争在摧毁世界旧秩序的同时，也极大地推动了科学技术的发展，而量子计算的最初萌芽就发生在二战里。

前奏

19世纪的英帝国国力昌隆，在科学领域，英国同样也群星璀璨，在麦克斯韦震古烁今的电磁理论酝酿诞生的同时，查尔斯·巴贝奇（Charles Babbage）也在不断失败的处境中尝试着完成差分机和分析机，尽管至死都没有完成设备的组装和完整运行，但是，这些能够通过逻辑化的运作进行复杂数学运算的设备雏形却使得人们认识到通用计算机的可能性。

1936年，阿兰·图灵提出了现代计算机的概念。 （来源：NPL/Science Museum）

1936年，阿兰·图灵（Alan Turing）在论文《论数字计算在决断难题中的应用》（On Computable Numbers, with an Application to the Entscheidungsproblem）里提出了现代计算机的概念，天才的图灵是如此描述这样的设备的：“发明一台用来计算所有可计算数列的设备是完全可能的。”

1944年，世界上第一台电子数字可编程计算机巨人（Colossus）在英国问世，它的用途就是为了破解德军通信密码，在冷战期间，为了掩盖英国有能力破解洛伦兹密码机（Lorenz Cipher）的事实，丘吉尔下令销毁绝大部分巨人计算机。1946年，ENIAC在美国曝光，在战时，这台设备设计之初的主要目的就是来计算火炮射表，而它最早承担的项目还包括计算热核武器的可行性。

随着战争结束以及社会各行各业的复兴需求，体积庞大但在运算上有着惊人优势的计算机从战争期间的隐蔽战线开始越来越多地出现在民用和商业领域。

1951年，费朗替（Ferranti）公司为曼彻斯特大学开发出了世界上第一台商用计算机Ferranti Mark 1，同年，美国人口调查局采购了UNIVAC I，这是世界上第一台被大规模制造的计算机，仅仅3年之后，IBM 推出了“相对”而言更小更便宜的计算机IBM 650 ，这台设备净重超过900千克，算上电力供应装置之后则在1.35吨以上，售价高达50万美元或者每月租金为3500美元。

1947年，双体性晶体管问世，并逐渐取代真空管在以往计算机设计中的位置，1953年，世界上第一台可运行的晶体管计算机在英国问世，两年后，另一台包含200个晶体管、1300个固态二极管的晶体管计算机问世。相比真空管，晶体管的体积更小、耗能更少、更稳定而且寿命更长，但是最重要的是，它能容纳数以万计的逻辑电路。在1952年，集成电路概念首次被杰弗里·达莫（Geoffrey W.A. Dummer）提出，6年后，世界上第一个可运行的集成电路问世。晶体管和集成电路的出现意味着计算机有了更快的运行速度和更强大的计算能力。

1965年，英特尔联合创始人戈登·摩尔（Gordon Moore）在文章中提出了被后人补充进而成型的摩尔定律，10年后，摩尔本人再次对此定律做出调整：“在这10年末期，倾斜程度（半导体芯片上集成的晶体管和电阻数量）将每2年增加大约1倍。”

计算机的发展轨迹按照摩尔的预言波澜不惊地前行着，大众继续享受着计算机小型化、廉价化和性能提升带来的种种便利优势。但是，科学界却异常焦急，大量新的议题和项目迫切需要计算能力更加强大的计算机设备帮助，Altas、CDC6600、Cray 两代以及90年代面世的富士“数值风洞”（Numerical Wind Tunnel）、Hitachi SR2201等超级计算机尽管已经在一定程度上解决了科学家的需求，但是，他们对当时计算机的能力依然感到不满足而迫切地需要一种新的更加强大、速度更快的计算机设备。

匣中的失乐

数学上，算法是对函数进行有效计算的方法，算法研究的一个重要的切入点是寻找可以有效计算的函数，这类函数叫做递归函数。

1931年，哥德尔（Kurt Friedrich Gödel）提出并证明了后来被统称为哥德尔不完备定理的两条定理，而根据哥德尔不完备定理，一些函数在数学上是不能被算法计算的。

哥德尔对“计算”（computation）做出了清晰的定义，尽管在论文里这些定义看上去不尽相同，但它们最后都归于同一类可计算函数里。而邱奇-图灵假想(Church-Turning thesis)做出这样的判断，任何在算法上可计算的函数都能被图灵机计算。

计算机科学家把一个运行时间随着输入大小而像多项式展开那样增长的算法叫做“多项式时间”（polynomial-time），如果一个问题用多项式时间就能解决的话，大家就把它称作复杂类度为P的问题——绝大多数P类问题都用有效的算法解决，然而，大多数不属于P类的问题无论花多少时间也解决不了。

按照强邱奇－图灵假想（Strong Church-Turing Thesis）进一步推演的话，就是说，如果在物理计算机上计算一个可计算函数的时间是 T 的话，那么在图灵机上的时间则是O(Tc)，而这里的常数 c 仅仅由计算机使用的函数类型决定。

随着数字计算机的出现，由于机器本身的容量和时间有限，这就使得可计算和不可计算之间的差别在计算机的实际应用上显得越来越重要，皮特·休尔（Peter Williston Shor）这样评价道，“如果所有计算机跑完一个可计算函数的时间里，太阳都燃烧殆尽了，这在实用方面可一点都不好。”

于是，一种新的迥异于传统算法的计算机呼之欲出。

1970年，斯蒂文·威斯纳（Steven Wiesner）就设想量子信息处理是解决密码逻辑认为较好的一种方式，这是量子计算最早的火花。在10多年后，在爱德华·福莱德金（Edward Fredkin）的可逆计算理念的启发下，费曼为大家开辟了那条新路。

费曼相信，一台基于量子力学现象的计算机在模仿量子力学现象上有着近水楼台先得月的先天优势。

“自然不是经典的，如果你想模拟自然的话，那你最好去用量子力学。”

在1982年发表的一篇论文中，诺贝尔奖得主费曼认为，在计算机上模拟量子力学内在地就需要指数级增长的投入，而他给出的建议则是，使用量子计算机。费曼相信，一台基于量子力学现象的计算机在模仿量子力学现象上有着近水楼台先得月的先天优势——早在1980年，保罗·贝尼奥夫（Paul Benioff）就在论文里提到了基于图灵机制造微量子力学系统计算机模型的可能性。

1985年，牛津大学的大卫·道勅（David Deutsch）在一篇论文里给出了量子计算的抽象模型，但是，此时大家的疑问还是，量子计算机究竟能解决哪些实际问题。7年后，道勅和理查德·约饶（Richard Jozsa）在论文里给出了他们的肯定答案：

“比起任何基于确定性算法的经典计算机，量子计算机在解决问题上所花的时间要少得多；比起任何基于随机算法的计算机的预期时间，量子计算机也相对更少。”

但是仅仅有量子计算机的设想还是远远不够的，没有算法支持的计算机无疑远远都只能停留在遐想阶段，要让所有人都真正信服量子计算机的巨大先进性，他们还需要更具说服力的事实。

正是从20世纪90年代开始，量子计算的研究取得了前所未有的丰硕成果，在各大公司实验室和院校机构的共同推动下，量子计算从科学家论文中的设想、算法逐渐落实到到实际制造的机器上。

1994年，贝尔实验室的休尔发表了论文，在里面向大家展示了他的量子算法分解大数的质因数的速度如何领先于当时的已知任何计算机——分解一个1000位的数字，传统计算机大约需要耗费10京（《孙子算经》载“万万曰亿，万万亿曰兆，万万兆曰京”）年的时间，而利用量子计算机的话，只需要20分钟左右。

休尔的量子算法将会对 RSA 等在内的加密算法和系统造成了显而易见的冲击，在此以前，破解一个 RSA 129位密码需要8个月时间以及1600名计算机用户，然而用量子算法破解 RSA 140位密码也只要数秒的时间而已。

休尔的发现使得量子计算机掀起了一场的风暴，不仅席卷了物理学和计算机科学领域，让他们感受到新的计算工具蕴含的巨大潜力，亦使得包括之前一直相信使用 RSA 算法的国家部门和各公司开始认真对待关注这个概念。

量子计算机第一次从科学家的象牙塔里走到了世人面前。

1995年，舒马赫（Benjamin Schumacher）发表了论文，第一次提出了量子比特信息学上的概念，并创造了“量子比特”（qubit）的说法。

比特（bit）是传统计算机中最基础的构件，它只存在两个状态0或1之间，在量子计算机中，情况却并非如此。量子力学告诉我们，量子具有叠加态的特性，因而，量子计算机中的比特——即量子比特——同时就有了0与1的状态，它既可以是1，亦可是0。基于量子平行，我们可以将这两种状态看成是处于两个不同宇宙里，那么，当一个量子比特进行运算时，实际上是处于两个宇宙里的数值在同时执行。

包含3个量子比特的寄存器

3个比特可以代表8种状态，但是寄存器却只能记录其中的一个结果，而3个量子比特构成的寄存器同时也具备了其线性叠加态效果，于是可以同时记录8种数值结果。通过这样一个简单的例子就能看出来量子计算机惊人的计算能力，是同数目（设为n）比特构成的经典计算机的2n倍。

理论上来说，一个量子比特可以储存的信息是无限的，当被测量时，状态满足一些特定条件的量子比特才会释出0或1那样的结果，也就是说，测量会使得量子比特从叠加态坍缩，反之，量子比特中存储的信息将始终处于动态演化过程之中，并且，通过量子门就能读取其中的信息。

假设我们取数字15来作为要分解的对象，设它作N，随机选一个数字设作X，并且1<X<N-1，将X当做寄存器A中内容的指数然后对N进行模除，余数则置于寄存器B中，即：

我们将这个运算结果列表如下：

我们会发现上述取值的运算结果呈现出（1，2，4，8，1，2，4，8……）的重复数列，我们将重复的频次命为 f，那么这个运算中，f 的取值就是4。

通过寄存器B中一系列复杂的运算执行，上述的f可以在量子计算机中获得，得出的f值会带入下列公式计算出一个可能的因数。得出的结果不会一定就是正确的，但是生成f值的量子干涉会反复尝试对x进行代换从而筛选出正确的结果并排除错误的答案。

这就是休尔的量子算法的整体思路，它向科学界和大众真正展示了量子计算的强大威力。

计算机科学中一个最基本的问题就是非结构化搜索，1996年，贝尔实验室的拉夫·格罗夫（Lov Kumar Grover）在论文里提出了针对这一问题的量子算法。假设有 N 个黑箱，每个箱中包含确定的1或0，每次打开一个箱子记为一次搜索请求，那么如果我们想要寻找到包含1的箱子，那么最多讲需要进行N次请求，而格罗夫的算法则将其减少到了次。

量子计算机固然拥有众多优势，但是这些基于量子力学上的特性也使得它本身较之经典计算机更加不稳定。和经典计算机的设计、硬件并不一样，量子计算机的设计制造首先需要保证量子比特处于稳定的相干叠加态的之中。

量子计算机强大的能力是建立在量子相干态带来的量子平行上的，一旦相干态中的量子比特在和外部环境发生量子纠缠之后会陷入退相干状态，那么，此时的量子比特和传统比特一样只能表示一种状态，也就是说，不稳定状态下的量子计算机和经典计算机相比丧失了最大的优势——1995年，休尔和安德鲁·斯迪恩（Andrew Steane）分别独立发表了量子纠错的规划，试图以此来解决量子计算机在退相干上的隐患。

无论是休尔还是格罗夫的量子算法实际上都是建立在量子线路基础上的，而量子线路和经典计算机一样也包含导线——这里的导线在广义上还包括粒子、光子乃至地域传送、时间演化等——和逻辑门，前者用来传输信息，后者则负责操作。

机器纪元

如果量子计算仅仅是停留在模仿经典计算机算法的地步的话，那么量子计算本身在信息储存和操作具备的巨大优势就会仅仅被用来在计算复杂性理论（computational complexity theory）上留下一些成果，而现实的物理世界及问题则会被忽视。于是，在基于量子线路基础上的量子算法之外，还出现了其他的量子算法，而它们不仅确实能在一些应用场景中超过经典计算机，还能重新定义难解（intractability）和易解（tractability）问题的抽象概念。

• 绝热算法(adiabatic algorithm)

2000年，MIT和东北大学（Northeastern University）的物理学家团队提出了绝热算法（Adiabatic Algorithms），2004年，该算法被证明在多项式意义上等价于线路模型。

• 基于测量的量子算法（Measurement-Based Algorithms）

和量子线路模型以幺正演化（unitary evolution）作为基本机制来操作信息不同，该算法只使用非幺正测量手段作为可计算步骤，这套算法演变称两个主要门类，一是隐形传态下的量子计算（teleportation quantum computing），二是单向量子计算机（one way quantum computer）。在2003年，该算法被证明在计算复杂性理论问题上同样等价于线路模型。

• 拓扑量子场论（Topological-Quantum-Field-Theory Algorithms）

在2000年，有人已经证明，该模型可以在标准量子计算机上被高效模拟，但是该算法的最大优势在于高容错性，而这就意味着大规模量子计算机的可能性。

1996年，赛斯·罗伊德（Seth Lloyd）在论文里为费曼曾经提出的量子计算机的设想给予了肯定的答案，包括量子计算机在内的任何量子系统都能通过程序化来模仿任意量子系统的行为，而且他还给出了对量子计算机的未来展望：

“各式原子、分子以及半导体制成的量子设备的出现预示着量子模拟即将成为现实。”

1997年，第一个基于量子计算机的核磁共振模型提出，下一年，核磁共振技术就运用到了2量子比特位的寄存器中，而到了2000年，寄存器中的量子比特数量在美国洛斯阿拉莫斯国家实验室（Los Alamos National Laboratory）手中增加到了7个。

和经典计算机不一样，量子比特并不天然存在，除了粒子阱之外，人们还尝试了基于量子比特的偏振化光子、超导体、半导体以及拓补量子来作为量子比特，不断地寻找最稳定的量子比特载体。

2001年，IBM利用核磁共振技术激活7枚核自旋体使其成为量子比特，在成功运行了上兆次之后，终于成功地将15质数分解为3 × 5，量子计算机第一次将使得量子计算变成了现实——整整10年之后，中国的科学家利用4个量子比特实现了分解143。

2005年，人们成功地在粒子阱中控制住了8个量子比特，到了2010年，人们已经可以在粒子阱中制造出14个处于纠缠态的量子比特。

到了2012年，早已经不复往日风光的 IBM 依然在量子计算领域取得了惊人的成就，他们利用3D超导量子比特成功地使量子比特维持量子状态的时间延长到100微秒（μs，1微秒等于百万分之一秒）——对当时的科学家们而言，这微不足道的刹那时间已经超过了量子计算机进行有效的纠错机制的最低时间，而他们则能把更多的精力放在提高量子计算机规模的工程问题上。

在量子计算风起云涌的90年代，在IBM、贝尔实验室、MIT等各领风骚的同时，一家4人联合创办的公司在远离量子计算研究应用版图中心的加拿大悄悄地成立了，此时正是20世纪的最后一年。

在之后的很长一段时间中，这家叫D-Wave的公司也并没有引起多少人的注意和兴趣，直到2007年，这家默默无闻的公司忽然推出了16位量子退火处理器原型猎户座（Orion），而仅仅9个月后，他们又向外界展示了其27位处理器原型。

红色为模拟退火算法，黑色为量子退火算法

D-Wave的量子退火算法的原理大体是这样的：

和基于热波动原理的模拟退火（simulated annealing）不同的是，量子退火(Quantum annealing)利用了量子波动。量子波动使得量子具有穿透比它自身能量高的势垒的能力，即量子隧穿效应。量子退火通过模拟这一过程来实现对目标系统的优化。

模拟退火算法要跳出局部最小点A到达全局最优点B只能采用翻越势垒的方式实现，因此以一定概率暂时接受较差的当前解成为必须。量子退火算法则利用量子隧穿效应，可以直接从 A 点穿透势垒到达B点。因此，量子退火可能在某些问题上具有比经典模拟退火算法更好的性能。

这家公司就像一个粗鲁而强壮的野蛮人一般风风火火地撞进了由实验室和象牙塔里的科学家们经营维护的秘密花园，然后大无畏地荡涤一切，兀自平静地看着那群目瞪口呆猝不及防的人们。

加州大学伯克利分校教授阿麦什·瓦泽朗尼（Umesh Vazirani）这样评价 D-Wave 和他们的原型产品：“一个16位的量子计算机只比手机的处理器强一些，很难说它代表了什么实用突破……即使 D-Wave 的‘量子计算机’的确是真的量子计算机，就算它有上千个量子比特，它也不必一部手机强上多少。”

然而，4年之后，这家公司推出了运行128位的一体量子计算机D-Wave One，代号“雷勒”（Rainier）的处理器主要用来解决优化问题，这被认为是世界上第一台商用化的量子计算机系统，其售价将近1000万美元。推出这台机器之后仅仅4天，洛克希德·马丁公司就和D-Wave签署了一份购买其机器、维护服务的长年合同。

对D-Wave的怀疑并没停息，一支研究团队表示，D-Wave One里的量子退火在运算速度上并没有比经典计算机快上多少。

但是，对D-Wave批评质疑的局面并非一成不变。

MIT的教授斯科特·艾伦森（Scott Aaronson）自称“怀疑 D-Wave 者扛把子”（Chief D-Wave Skeptic），早在2007年他就宣称D-Wave原型机展示“什么都没法证明”。

随着D-Wave One的推出以及更多关于支持D-Wave的研究——其中就包括发表在《自然》（Nature）上的论文——的出现，艾伦森也渐渐改变了自己的倾向，尽管依然坚持自己的质疑，但是，他最终还是表达了对D-Wave的祝贺，并宣布“从‘怀疑D-Wave者扛把子’任上退休”：

“过去4年来，大家一直要量子计算群体去评价一家只有冷水和餐盘的食肆，现在我很高兴看到 D-Wave 终于端上了开胃菜。”

2012年，D-Wave推出了代号“维苏威”（D-Wave）的512位量子计算机D-Wave Two，同一年，这家公司和 Google、NASA合作在埃姆斯研究中心（Ames Research Center）组建了量子人工智能实验室（Quantum Artificial Intelligence Lab）。

不同的研究团队对D-Wave的能力有着几乎截然相反的评价，有人认为，在解决某些问题上，它的机器的最快运算速度是经典计算机的3600倍，而另外一些实验则显示，在解决Prog-QAP问题上，普通单核桌面处理器的速度最多是D-Wave的1.2万倍，在处理Prog-QUBO问题上，前者最多是后者的160倍。

实际上，D-Wave对自己的机器有着清晰的界定：

这台机器并非通用量子计算机，仅仅只用运行优化算法；

这台机器的量子比特是有噪的，在容错阈值之下是无法运行的；

并没有大规模的量子纠缠；

一些良好调整的经典优化算法有时能超过D-Wave Two。

D-Wave 2X 量子计算机。 （Photo by Stephen Lam/Reuters）

在不断的争议和批评中，D-Wave在2015年发布了他们基于“喀迈拉图”（chimera graph）架构的新一代1152位（实际上并没达到）量子计算机系统 D-Wave 2X。

一年之后，IBM推出了自己的5位量子计算机处理器，而正如它始终强调而D-Wave 欠缺的那样，这是一台通用量子计算机，尽管蓝色巨人已经显出倾颓迹象，但是它依然给自己的量子计算列出了未来10年周期的开发计划——在之后10年里开发出50~100位的量子计算机。IBM研究院总监阿尔文德·克里希纳（Arvind Krishna）这样说道：

“量子计算机和今天的计算机非常不一样，不只是因为样子或什么做成的，更重要的在于量子计算机能做的事情。”

未来将至

在D-Wave的一份官方PPT中，公司的CTO乔迪·洛斯（Geordie Rose）认为，量子计算机最具颠覆性和吸引力的就是在分子维度上模拟自然，它在制药、化工还有生物科技等领域都有着广阔的应用，由此，量子计算可以撬动涵盖上述3个总价值3.1万亿美元的市场。

这是10年前他在斯坦福大学演讲时的期许。

回顾历史，在麦克斯韦的19世纪，电磁物理推动了电力的发展，使得人类社会的文明程度上升到前所未有的地步，毫无疑问推动了工业和商业的进步。回首过去一百多年，战争结束后，包括太空探索、计算机、核能开发等技术革命几乎都与量子力学有关，而这些技术最终也无一例外地反过来促进了民用和商业。

量子计算研究的成熟和繁荣也毫无疑问地有着这样的效应。

早在2002年，就有了第一家从事量子钥分配的商业公司ID Quantique，10多年后，黑莓创始人迈克·拉扎里德斯（Mike Lazaridis）成立了1亿美元的风投基金投资量子计算，下一年，英国政府宣布投入2.7亿英镑来支持量子技术的研究和商业化。

现在，量子计算应用最深入、最具现实性的领域毫无疑问地是在通信方面。

早在1970年，斯蒂芬·威斯纳就提出了“量子钱”（quantum money）的概念，最早利用量子的测不准性来进行加密，直到1983年这一设想才得以以论文的形式公诸于世，在威斯纳思路的启示下，BB84协议问世。

量子通信的基本原理是这样的，收发双方的信息内容是可以被编译成光子偏振的，信息发送者利用随机偏振发送信息，接受信息者发现并记录下信息。然后，发送者在公频告知接受者偏振频率，两者按照正确的偏振比对选择的信息部分。如果在信息收发过程中有窃听者并试图转发信息的话，那么倾听者有一半的机会获得正确的信息。

由于接受者获得的信息中有一半是错误的，他可以在公频中将这些错误信息和发送者选取随机信息对比，然后重复收到错误、对比的过程，直至得出正确的完整信息。也就是说，在整个信息收发过程中，要做到隐瞒收发双方窃听信息是不可能实现的。

正是基于上述的原理，量子通信可以最大限度地保证用户的隐私和信息安全，也正因为这样，量子通信在国家信息安全层面有着越来越迫切的现实需求，从根本上来说，这也是包括中国、美国及欧洲纷纷跟进的原因。

1992年，本内特和威斯纳共同提出了超密编码协议（super-dense coding protocol），利用一个无噪缠绕比特信道和一个无噪量子比特信道模拟出了两个无噪经典比特信道，次年，本内特等六人发表的论文提出了隐形传态协议（teleportation protocol），利用两个经典比特信道和一个缠绕比特实现了一个量子比特的传输。

这两个协议的提出奠定了整个量子信息理论的基础，向我们展示了经典通信源和量子通信源结合、有噪通信源和无噪通信源结合的可能性。在随后20多年的时间里，量子通信开始受到各国的重视并快速进入应用阶段。

1993年，英国率先在10公里的光纤中实现了量子密钥分发，4年之后，洛斯阿拉莫斯国家实验室创记录地在48公里的地下光纤完成了量子密码本的传输，1999年，日本和瑞典合作完成了40公里光纤的量子密码通信。

中国在量子通信领域发表的论文遥遥领先于其他国家地区 （来源：博客）

2000年，中国在850纳米的单模光纤中完成了1.1公里的量子密码通信演示性实验，到2004年，中国科学家在北京与天津之间成功实现了125公里光纤的点对点的量子密钥分配，2005年，中国创造了13公里的自由空间双向量子纠缠分发世界纪录，同时验证了在外层空间与地球之间分发纠缠光子的可行性。2009年，成功实现了世界上最远距离的量子态隐形传输，证实了量子态隐形传输穿越大气层的可行性，同年8月，在合肥构建了全球首个全通型量子通信网络，实现了实时语音量子保密通信。2010年，中国成功实现了16公里的量子态隐形传输，比原世界纪录提高了20多倍。

中国科学技术大学、中国科学院以及北京邮电大学在论文发表数量上有着巨大优势。 （ 来源：博客）

在中国这个市场最大、资源最雄厚的地方，量子计算如野火一般烧遍各个领域，为焦土中的萌芽积攒下最肥沃的养料。尤其是在量子通信方面，中国在研究、应用方面所获得的成就全面领先于其他国家地区。除了墨子号的发射之外，现在，北京和上海之间建造的长约2000公里的“京沪干线”是世界上第一条量子通信网络。

与此同时，在通信之外的领域，量子计算同样也有着诱人的吸引力。

在航空领域，洛克希德·马丁之所以采购 D-Wave 的机器，就是因为先有的经典计算机在进行飞机软件实验时往往力不从心，无法应付大量繁复的数据。同样的道理，NASA 也早早意识到了量子计算在分析外太空行星轨道数据方面的巨大优势，也早早地和 D-Wave 建立起了合作关系。

在天气气候方面，量子计算也有着让人期待的表现，在处理计算大规模数据方面的优势使得人们对于天气气候模型的认识了解更深入及时的话，那么就能带来更准确的天气气候预报，而更准确的预报必然提高自然气候灾害的预防力度和治理效率，实际上密切关系着人们正常的生活工作。Google 的工程总监曾经如此评价道：“我们相信量子计算可以解决许过最具挑战性的计算机科学问题……如果我们想创造更有效的环境政策，我们就需要更好的模型来了解气候究竟发生了什么。”

在制药、生物科技方面，量子计算俨然一副救世主的面貌。这些行业推出一款可上市产品必然会经历一个漫长的实验分子结合的过程，而往往这些实验又以失败告终，因此，通过量子计算来节省大量的时间和成本不仅有利于这些公司的商业诉求，反过来也能极大地降低抗癌药等高价药的成本，最终帮助到普通病患。而在可以预见的未来，基因层级的分析实验等必然会成为医学研究的主要方向之一，而这同样需要借助到量子计算的力量。

事实上，量子计算同样能够推动人工智能和机器学习等的演化进步，从而实现高科技技术之间的协同效应。

1999年，阿拉姆·哈罗（Aram W. Harrow）、阿维纳塔·黑斯登（Avinatan Hassidim）及赛斯·罗伊德（Seth Lloyd）共同发表论文提出了一种崭新的量子算法以解决线性方程式系统，经典算法所需要的时间为O（Nk)，而该算法能将时间缩短至O(log(N)k2)。

机器学习就是识别系统中数据呈现出来的趋势，其主要任务就是在高维向量空间（high-dimensional vector spaces）里对数据进行操控和分类，经典机器学习的算法受制于数据量和空间维度所决定的多项式时间，而量子计算机则能通过利用张量积的空间（tensor product spaces）来操控高维向量。

这上述被称之为 HHL 的量子算法正好可以施用于支持向量机（support vector machine），而罗伊德参与的另一篇论文指出，所有的量子支持向量机都能被用作进行大数据分类，而且较之经典计算机在速度上有显著的优势。

而今，自动汽车、自动驾驶、脑机交互、自然语言处理乃至线上广告、搜索引擎、推荐系统等都是机器学习的热门领域，从这一点来说的话，我们可以毫不夸张地说，量子计算实际上决定了包括特斯拉、Google、微软、Amazon、Facebook等公司在未来的发展方向和趋势。

实际上，如果我们留意墨子号报道的话就会发现，在中国的量子卫星项目中，阿里量子隐形传态实验站也是地面科学应用系统的重要组成部分。

而早在2015年，阿里巴巴就与中国科学院联合成立了量子计算机实验室。

根据他们的规划，到2025年，量子模拟将达到当今世界最快的超级计算机的水平，初步应用于一些目前无法解决的重大科技难题；到2030年，研制具有50~100个量子比特的通用量子计算原型机，自主研发物理层设计、制造及算法，全面实现通用量子计算功能，并应用于大数据处理等重大实际问题。

除了处理购物网站页面搜索、购买、交易等方面产生的巨大数据之外，对这家中国目前市值最高的互联网公司而言，量子算法最大的价值和意义在于更好地利用这些数据产生更大的效益。

从金融、共享经济再到文娱产业，所有的这些产品与服务实际上都和中国互联网用户的数据息息相关，而中国的互联网用户又是全世界最庞大最复杂的群体，要优化甚至商业化这些数据，仅仅依靠经典计算机或者经典算法或许还能应付当前的局面，但要如阿里巴巴量子计算实验室创始人所言成为横跨3个世纪的百年企业的话，它无疑需要更具前瞻性和战略性的技术作为储备和杀手锏。

对它而言，对Google、微软、特斯拉等公司而言，它们都是抱着同样的心理。

而这亦是促使从我们这个漫长故事开头的奥斯特到麦克斯韦再到普朗克、玻尔以至图灵、休尔、格罗夫到今天的潘建伟等人成为时代风云人物的原因。

在历史的巨浪中，他们看见了浪花中所蕴含的方向和潮流，而后便紧紧追逐而去，他们知道，自己在当下的选择和坚持不仅是自己未来的一部分，更重要的是，还会成为未来与历史的浓墨重彩的一部分。

如果说量子计算时代已经到来的话，我们不得不说，至今我们依然没有一台真正公认的量子计算机问世；如果说量子计算时代还很远的话，我们又必须承认，利用量子计算技术产生的成果正越来越多地应用到我们的生活之中去。

这是量子计算的故事，也是历史的故事。（本文系BT传媒·《商业价值》杂志2016年10月刊封面文章，网络独家首发钛媒体，记者/胡勇）

本文参考文献附录：

1. Mark M. Wilde, “From Classical to Quantum Shannon Theory” (2016), PDF at arXiv:1106.1445; (1st ed.: “Quantum Information Theory”); 26 - 28 

2. Bence Jones, The Life and Letters of Faraday, 第 2 卷

3. H. C. Oersted, The Soul in Nature (London, 1852), p. 384 

4. James F A J L(ed.). The Correspondence of Michael Faraday，Vol.1. Institution of Electrical Engineers，1991，p. 287 

5. Freeman J. Dyson, Why is Maxwell's Theory so hard to understand? Conference: Antennas and Propagation, 2007. EuCAP 2007. The Second European Conference on 

6. Lewis Campbell; William Garnett, The Life of James Clerk Maxwell (London, 1882), p. 252 

7. M.J.Klein,Science,148(1965)p.176 

8. Beam Line: Summer Fall 2000, Vol. 30, No. 2, p.16 

9. Albert Einstein, in a letter March 24, 1954; from Albert Einstein the Human Side, Helen Dukas and Banesh Hoffman, eds., Princeton, New Jersey: Princeton University Press, 1981, p. 43. 

10. “Simulating Physics with Computers,” International Journal of Theoretical Physics, VoL 21, Nos. 6/7, 1982 

11. P. Benioff, The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines, J. Statist. Phys. 22 (1980),563–591

12. D. Deutsch, Quantum theory, the Church–Turing principle and the universal quantum computer, Proc. Roy. Soc. London Ser. A 400 (1985), 96–117 

13. D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proc. Roy. Soc. London Ser. A 439, (1992), 553–558 

14. P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, Proc. 35nd Annual Symposium on Foundations of Computer Science (Shafi Goldwasser, ed.), IEEE Computer Society Press (1994), 124-134. 

15. Vishal Sahni, Quantum Computing. New Delhi: TATA McGRAW –HILL Publishing Company LTD., 2007. p.121 

16. Lov K. Grover. A fast quantum mechanical algorithm for database search. In ACM Symposium on Theory of Computing, pages 212–219, 1996 

17. S. Lloyd, “Universal Quantum Simulators,” Science 273, 1073–1078 (1996). 

18. Du Weilin, Li Bin, and Tian Yu. Quantum Annealing Algorithms: State of the Art. Journal of Computer Research and Development, 2008, 45(9): 1501-1508

19. A. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for solving linear systems of equations. Phys. Rev. Lett., 15(150502), 2009. arXiv:0811.3171. 

20. S. Lloyd, M. Mohseni, and P. Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411, 2013.