在量子计算发展最初的阶段作出重要贡献的三位先驱科学家（从左至右）：保罗·贝尼奥夫（Paul Benioff）、戴维·多伊齐（David Deutsch）和彼得·秀尔（Peter Shor）。2021年10月25日，中国科学技术大学潘建伟团队在物理学期刊《物理评论快报》（Physical Review Letters）上同时报告了两个关于量子计算的新进展。
其中一个，是66比特可编程超导量子计算原型机“祖冲之2.0”的工作，研究人员通过操控其上的56个量子比特，在随机线路采样任务上实现了量子计算优越性；另一篇论文是升级版的光量子计算原型机“九章2.0”：对于高斯玻色采样问题，“九章2.0”具有了部分可编程的能力，其一分钟完成的任务，世界上最强大的超级计算机需要花费亿年时间。
量子计算在一些特定问题上的巨大优势，令人期待其在帮助解决一些实际问题上发挥出自己的能量。那么，量子计算的概念是怎样提出来的？量子计算的实质是什么？我们如何证明量子计算理论上的优越性？以下这篇文章，就以上问题进行了解答，并介绍了在量子计算发展最初的阶段作出重要贡献的三位先驱科学家。
提及量子计算，人们大抵会想到1981年在麻省理工学院举办的第一届计算中的物理大会（First conference on the Physics of Computation）上，理查德·费曼（Richard Feynman）做出的关于量子计算的演讲。但实际上，保罗·贝尼奥夫（Paul Benioff）也参加了那次大会。
与费曼讨论能否在经典计算机中有效模拟量子系统不同的是，贝尼奥夫主要讨论了是否能构造出没有耗散，且遵循量子力学进行操作和运算的计算机模型。贝尼奥夫的这次报告主要基于他在1980年发表的学术杂志文章中的工作。在当时关于计算机的模型形式就有很多讨论，大部分的计算机模型都是考虑的开放耗散系统，一个很自然的问题就是，计算机模型是否能通过封闭且能量守恒的系统构造？
如果存在，就可以减少很多计算机处理信息和运算过程中的能量损耗问题。贝尼奥夫在他1980年的论文当中，构造出这样无能量耗散的计算模型。
在贝尼奥夫的工作中，他将图灵机中的每个组成部分和操作，在他构造出的基于量子系统的计算机模型中找到了对应。
在他的构造中，一维自旋晶格构成了图灵机的纸带，在晶格中一个固定位置的粒子构成了寄存器，而所有可能的图灵机的状态都由所有可能的自旋投影结果构成，而读写头则是由一个沿着晶格移动的无自旋粒子构成。他证明了对于每一个图灵机和任意数量的问题规模，都存在一个对应的哈密顿量和一类合适的初态，让图灵机的每一步的计算对应到纯态的演化过程中。
需要注意的是，这样的模型并不是完全没有能量的损耗，其能量的损耗会出现在诸如检查计算是否结束、让图灵机恢复到初态的过程中。毫无疑问，贝尼奥夫的这些理论工作都给量子计算机的发展奠定了坚实的理论基础。
戴维·多伊齐（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，并指出经典图灵机不能满足这一猜想。
多伊齐指出量子图灵机可以满足strong form of Church–Turing principle，并且讨论了量子图灵机的若干特性，如量子随机性，量子关联，量子并行性，量子算法优势，并非常富有远见地指出了量子计算复杂度理论的研究意义，这些概念都极大地指导了后来量子计算科学的研究。
1992年，多伊齐与理查德·乔萨（Richard Jozsa）拓展了先前的研究，提出了Deutsch–Jozsa算法，这是最早的量子算法之一，能够相对任何可能的确定性经典算法带来指数级的加速。多伊齐在量子逻辑门理论，量子计算网络，量子纠错方案上均做出过贡献。
此外，多伊齐还曾建议使用纠缠态和贝尔定理进行量子密钥分配，后来提出了量子密码学中重要的E91协议的阿图尔·埃克特（Artur Ekert）正是他的博士生。多伊齐是量子力学的多世界诠释的支持者，在理解其哲学含义方面开展了大量研究，并撰写著作将之传播给公众，他的作品《现实的结构》曾于1998年入围Rhone-Poulenc科学图书奖。
作为国际奥林匹克数学竞赛奖牌得主，彼得·秀尔（Peter Shor）在学生生涯期间就展示了在数学上的惊人天赋。他于1981年获得了加州理工的数学学士学位，并在此期间参加曾普特南数学竞赛获“Putnam Fellow”。1985年秀尔在麻省理工学院取得应用数学的博士学位，后于加州大学伯克利分校从事博士后研究。而后秀尔接受了贝尔实验室的研究职位，并在那里开发出了大名鼎鼎的Shor算法。
Shor算法展示了量子计算可以在质因数分解问题上实现比经典计算机近乎指数级别的加速，这是第一个让人们相信量子计算机可以在模拟量子物理系统之外得到广泛应用的算法，引发了物理学界之外广泛的讨论，开启了量子计算研究的热潮。
秀尔对于质因数分解算法的工作部分建立在计算机科学家丹尼尔·西蒙（Daniel Simon）的工作之上，秀尔曾在1994年4月在贝尔实验室内部做了一个关于该选题的报告，当时他还只是得到了部分结果，尚未真正解决质因数分解的问题。
然而会后消息不胫而走，在人们口口相传之下变成了成功进行质因数分解，于是在那个周末，计算机科学家乌梅什·瓦兹拉尼（Umesh Vazirani）就曾给秀尔打电话询问他是怎么做到的。神奇而幸运的是，报告结束的五天内，秀尔确实与奔走相告的人们同期开展研究得到了完备的结果，解决了质因数分解的问题。
秀尔的发现一出，立刻带来了两个显著的效应，一方面人们首次看到量子计算机在物理系统模拟之外的应用潜力，极大地促进了量子计算方向的研究；另一方面，对密码学界的研究造成了不小的冲击，因为它可以用于破解在互联网上广泛使用的公钥加密方案如RSA协议，给信息安全提出了新的挑战。这些都极大地引起了学界和社会对量子计算、量子通信的重视和投入。
面对以上挑战，秀尔再次挺身而出，构造了第一个量子纠错码方案，随后在其他多位研究者的努力之下，科学家们最终完成了量子容错计算的理论框架，使得脆弱的量子比特不再与噪声水火不容。在这样两个量子计算的重大理论突破之后，人们终于相信实际构建一台量子计算机是有巨大应用潜力和原理上可行的了，实验物理学家和工程师们从此正式登上历史舞台，取得了丰硕的科学成果。
值得一提的是，秀尔也是一位出版过诗集的诗人，在中国科学家成功构建“九章”量子计算原型机实现“量子计算优越性里程碑”之时，他曾赋诗一首：冯·诺伊曼主题变奏诗（主题：任何考虑用算术手段来产生随机数的人自然都是有原罪的）。若上帝的妙手算力不及我们粗制滥造的装置，我们又如何相信那是上帝之神工？