在量子计算发展最初的阶段作出重要贡献的三位先驱科学家（从左至右）：保罗·贝尼奥夫（Paul Benioff）、戴维·多伊齐（David Deutsch）和彼得·秀尔（Peter Shor）

---

  编者按

✚

●

○

2021年10月25日，中国科学技术大学潘建伟团队在物理学期刊《物理评论快报》（Physical Review Letters）上同时报告了两个关于量子计算的新进展。其中一个，是66比特可编程超导量子计算原型机 “祖冲之2.0” 的工作 ，研究人员通过操控其上的56个量子比特，在随机线路采样任务上实现了量子计算优越性；另一篇论文是升级版的光量子计算原型机 “九章2.0”：对于高斯玻色采样问题，“九章2.0” 具有了部分可编程的能力，其一分钟完成的任务，世界上最强大的超级计算机需要花费亿年时间。

量子计算在一些特定问题上的巨大优势，令人期待其在帮助解决一些实际问题上发挥出自己的能量。那么，量子计算的概念是怎样提出来的？量子计算的实质是什么？我们如何证明量子计算理论上的优越性？

以下这篇文章，就以上问题进行了解答，并介绍了在量子计算发展最初的阶段作出重要贡献的三位先驱科学家。

撰文｜揍苏   江流

责编｜Melody

 ●                  　●                   　●

 量子计算概念的提出 

提及量子计算，人们大抵会想到1981年在麻省理工学院举办的第一届计算中的物理大会（First conference on the Physics of Computation）上，理查德·费曼（Richard Feynman）做出的关于量子计算的演讲。但实际上，保罗·贝尼奥夫（Paul Benioff）也参加了那次大会。与费曼讨论能否在经典计算机中有效模拟量子系统不同的是，贝尼奥夫主要讨论了是否能构造出没有耗散，且遵循量子力学进行操作和运算的计算机模型。

贝尼奥夫的这次报告主要基于他在1980年发表的学术杂志文章中的工作。在当时关于计算机的模型形式就有很多讨论，大部分的计算机模型都是考虑的开放耗散系统，一个很自然的问题就是，计算机模型是否能通过封闭且能量守恒的系统构造？如果存在，就可以减少很多计算机处理信息和运算过程中的能量损耗问题。贝尼奥夫在他1980年的论文当中，构造出这样无能量耗散的计算模型。

在介绍贝尼奥夫的工作之前，首先需要简单了解一下图灵机。图灵机是计算机科学中常用的一个理论模型，它的主要组成部分有无限长的纸带、读写头、一套控制规则和状态寄存器。纸带被分隔成了一个接着一个的小格子，每个格子上要么是0要么是1或者别的符号。计算过程就是让机器读入纸带，根据当前机器所处的状态和当前读写头所指的格子上的符号，通过控制规则，更改状态寄存器的数值。重复以上的过程，直到寄存器中存储的状态为某个特殊状态，触发图灵机停止运算。

在贝尼奥夫的工作中，他将图灵机中的每个组成部分和操作，在他构造出的基于量子系统的计算机模型中找到了对应。在他的构造中，一维自旋晶格构成了图灵机的纸带，在晶格中一个固定位置的粒子构成了寄存器，而所有可能的图灵机的状态都由所有可能的自旋投影结果构成，而读写头则是由一个沿着晶格移动的无自旋粒子构成。他证明了对于每一个图灵机和任意数量的问题规模，都存在一个对应的哈密顿量和一类合适的初态，让图灵机的每一步的计算对应到纯态的演化过程中。需要注意的是，这样的模型并不是完全没有能量的损耗，其能量的损耗会出现在诸如检查计算是否结束、让图灵机恢复到初态的过程中。毫无疑问，贝尼奥夫的这些理论工作都给量子计算机的发展奠定了坚实的理论基础。

贝尼奥夫于1930年5月1日出生于美国加州的帕萨迪纳市。他的父母都是知识分子，父亲是美国加州理工学院的教授，母亲则从加州大学伯克利分校拿到了硕士学位。贝尼奥夫在1951年在加州大学伯克利分校拿到了植物学的本科学士学位。随后的两年，他在Tracerlab主要从事和核化学相关的工作。之后他又回到了加州大学伯克利分校，并于1959年获得了核化学的博士学位。

1960年，贝尼奥夫进入了以色列的魏茨曼科学研究院做博后。此后他获得了尼尔斯·玻尔研究所的福特研究员奖金，并在所里从事了六个月的科研工作。从1961年开始，他开始了他在美国阿贡国家实验室的漫长工作生涯，并于1995年退休。如今他以退休后的名誉科学家的身份，继续参与实验室里的科研工作。

除此之外，1979年，贝尼奥夫还作为客座教授在以色列的特拉维夫大学教授量子力学基础课程。同时，他还在1979年和1982年担任法国国家科学研究中心（CNRS Marseilles）的客座科学家。

贝尼奥夫在2000年获得了国际量子通信、计算和测量组织的量子通信奖，以及日本玉川大学的量子计算和通信奖。他于2001年成为了美国物理学会（APS）会士。在2002年，他又被授予了芝加哥大学阿贡国家实验室杰出表现特别奖。2016年，阿贡实验室举办了一次会议，以纪念贝尼奥夫在量子计算领域的杰出贡献。

 “自然可以被有效模拟吗？”

戴维·多伊齐（David Deutsch）于 1953 年 5 月 18 日出生于以色列海法的一个犹太家庭，在剑桥克莱尔学院进行自然科学的本科学习，在牛津沃尔夫森学院进行理论物理学方向的深造，博士学位论文的研究方向是弯曲时空的量子场论。

作为量子计算领域的先驱者之一，使多伊齐名声大噪的是他发表于 1985 年的影响深远的论文 Quantum theory, the Church–Turing principle and the universal quantum computer。

在这篇开创性的工作中，多伊齐用发人深省的语言风格阐述了物理学视角下 “计算” 的含义。多伊齐对图灵表述的 Church-Turing 猜想—— “任意 ‘被自然地认为可计算的函数’ 均可被图灵机计算” 中关于 “自然地” 概念的模糊表述提出了不满，并给出了物理学意义下的表述—— “任意物理上可有限实现的系统均能被一个通用计算机在有限资源下完美模拟”。多伊齐称此为 strong form of Church–Turing principle，并指出经典图灵机不能满足这一猜想。

基于此，多伊齐给出了他对 “量子图灵机” 的构想，与其他同时代的量子计算先驱提出的概念相比较，贝尼奥夫在1982年提出的 “量子计算机” 虽按照量子力学运行，本质上却仍旧是一种经典计算，每一个计算环节的最终结果中并不包含量子干涉、纠缠等量子力学特性，可以被经典图灵机完美模拟的；费曼构想的 “量子模拟机” 具备了充分的量子力学特性，可以模拟经典图灵机无法完美模拟的量子物理系统，但并没有进一步考虑赋予其通用性。

多伊齐指出量子图灵机可以满足 strong form of Church–Turing principle，并且讨论了量子图灵机的若干特性，如量子随机性，量子关联，量子并行性，量子算法优势，并非常富有远见地指出了量子计算复杂度理论的研究意义，这些概念都极大地指导了后来量子计算科学的研究。

1992 年，多伊齐与 理查德·乔萨（Richard Jozsa）拓展了先前的研究，提出了 Deutsch–Jozsa 算法，这是最早的量子算法之一，能够相对任何可能的确定性经典算法带来指数级的加速。多伊齐在量子逻辑门理论，量子计算网络，量子纠错方案上均做出过贡献。此外，多伊齐还曾建议使用纠缠态和贝尔定理进行量子密钥分配，后来提出了量子密码学中重要的E91协议的阿图尔·埃克特（Artur Ekert）正是他的博士生。多伊齐是量子力学的多世界诠释的支持者，在理解其哲学含义方面开展了大量研究，并撰写著作将之传播给公众，他的作品《现实的结构》曾于1998年入围 Rhone-Poulenc 科学图书奖。

自 2012 年以来，多伊齐致力于发展 constructor theory，试图将计算的量子理论推广到不仅涵盖计算，而且涵盖所有物理过程的 “万物理论”。

多伊齐于 1998 年获得物理研究所颁发的狄拉克奖，在2008年被评选为英国皇家学会会士，2017年获得国际理论物理中心（ICTP）颁发的狄拉克奖章， 2018年获得了墨子量子奖。

 诗人Shor和他的算法 

作为国际奥林匹克数学竞赛奖牌得主，彼得·秀尔（Peter Shor）在学生生涯期间就展示了在数学上的惊人天赋。他于1981年获得了加州理工的数学学士学位，并在此期间参加曾普特南数学竞赛获 “Putnam Fellow”。1985年秀尔在麻省理工学院取得应用数学的博士学位，后于加州大学伯克利分校从事博士后研究。而后秀尔接受了贝尔实验室的研究职位，并在那里开发出了大名鼎鼎的Shor算法。

Shor算法展示了量子计算可以在质因数分解问题上实现比经典计算机近乎指数级别的加速，这是第一个让人们相信量子计算机可以在模拟量子物理系统之外得到广泛应用的算法，引发了物理学界之外广泛的讨论，开启了量子计算研究的热潮。

秀尔对于质因数分解算法的工作部分建立在计算机科学家丹尼尔·西蒙（Daniel Simon）的工作之上，秀尔曾在1994年4月在贝尔实验室内部做了一个关于该选题的报告，当时他还只是得到了部分结果，尚未真正解决质因数分解的问题。然而会后消息不胫而走，在人们口口相传之下变成了成功进行质因数分解，于是在那个周末，计算机科学家乌梅什·瓦兹拉尼（Umesh Vazirani）就曾给秀尔打电话询问他是怎么做到的。神奇而幸运的是，报告结束的五天内，秀尔确实与奔走相告的人们同期开展研究得到了完备的结果，解决了质因数分解的问题。

秀尔的发现一出，立刻带来了两个显著的效应，一方面人们首次看到量子计算机在物理系统模拟之外的应用潜力，极大地促进了量子计算方向的研究；另一方面，对密码学界的研究造成了不小的冲击，因为它可以用于破解在互联网上广泛使用的公钥加密方案如RSA协议，给信息安全提出了新的挑战。这些都极大地引起了学界和社会对量子计算、量子通信的重视和投入。

然而，尽管Shor算法的横空出世仿佛让量子计算研究步入快车道，一些同期的顶尖实验物理学家却对建造出一台实际的量子计算机提出了怀疑。

这种怀疑来自于遵循量子力学的任何物理系统的基本特性之一——退相干，任何量子系统只要存在与环境的相互作用，就不可避免地与环境产生量子关联，这等效于一种噪声使得处于量子态的系统迅速退化为经典状态。这一特性部分地解释了为什么我们在日常生活中从来不能直接观察到任何物理系统处于量子态——即使构成我们生活中方方面面事物的微观粒子均服从于量子力学描述。退一步讲，即使实验物理学家真的能够建造一个与环境完美隔绝的量子系统，为了实现量子计算的过程，外界仍需要对其进行制备、控制、读取等过程，在实际建造设备的意义上来说这无法使系统与环境噪声真正隔绝。

另一个让问题变得更加棘手的困难是，在经典计算中噪声问题可以通过比较直观的纠错技术手段实现，相关技术在通信和经典计算机中已经被证明成功而且获得了普遍的应用，但对于量子计算机中的量子比特，任何涉及直接观测的纠错手段都会导致量子态受到破坏而失去量子计算本身的意义。

面对以上挑战，秀尔再次挺身而出，构造了第一个量子纠错码方案，随后在其他多位研究者的努力之下，科学家们最终完成了量子容错计算的理论框架，使得脆弱的量子比特不再与噪声水火不容。

在这样两个量子计算的重大理论突破之后，人们终于相信实际构建一台量子计算机是有巨大应用潜力和原理上可行的了，实验物理学家和工程师们从此正式登上历史舞台，取得了丰硕的科学成果。

值得一提的是，秀尔也是一位出版过诗集的诗人，在中国科学家成功构建 “九章” 量子计算原型机实现 “量子计算优越性里程碑” 之时，他曾赋诗一首：