从比特到量子比特，量子计算为什么快？｜量子计算群英会（四）

图1：贝尼奥夫

在MIT1981年的第一届“计算与物理”的大会上，除了费曼给出一个关于模拟量子计算的演讲之外，另一位科学家，保罗·贝尼奥夫（Paul Benioff，1930-2022）也作了一个重要的演讲。贝尼奥夫报告的主要内容是基于他在1980年发表的文章，其中主要讨论了图灵量子计算机，及其实现的可能性等等。

贝尼奥夫在 20 世纪 80 年代初发表了四篇论文，为量子计算的基础做出了开创性贡献。他首次证明量子计算机在理论上是可行的，可以构建量子系统来传递信息或执行极其复杂的计算。

贝尼奥夫的工作，讨论了关于计算机模型的形式。大部分的经典计算机模型都是开放耗散系统，量子计算机模型是否能通过封闭且能量守恒的系统构造呢？贝尼奥夫在他的论文中，构造了这样几乎无能量耗散的计算模型。

1

经典图灵机

首先简要介绍图灵机，这是计算机的一个常用的理论模型，由英国人图灵提出并以他命名。

阿兰·图灵（Alan Turing，1912-1954）如今被誉为计算机之父和人工智能之父，是一位数学天才，传奇的人物。

著名的数学家希尔伯特在1930年发表他的退职感言中有一句名言：“我们必须知道，我们必将知道”，阐明了他的科学哲学观：认为数学中没有不可知之物，任何一个问题都有解。他对数学系统的具体要求，包括满足“形式化、完备性、一致性、确定性”这几个要点。也就是说，在形式化的基础上，必须满足剩下的三条。

不过，就在第二年，另一位数学家哥德尔便提出不完备性定理，严格证明了“完备”和“一致”不可能同时满足，粉碎了希尔伯特计划的美梦。

天才的图灵对此很感兴趣，努力钻研后，用一个巧妙的方法得出了结论：判定性问题无解！

图灵那年才二十出头，他花全力构建了一个完美的通用计算机，这个机器可以满足希尔伯特将“计算”形式化的要求，然后，图灵用此机器证明了，即使计算机有无限的内存空间，能够永远持续计算，对某些问题，也无法在有穷的步骤内给出“是”或者“否”的答案。可以举“停机问题”为例说明这点。

什么叫停机问题呢？对一台计算机而言，输入程序w后，计算机开始运转，可能有两种结果：1，计算机在有限的时间内结束运算而停机（好结果）；2，计算机进入死循环，永远停不了（坏结果）。我们当然不希望我们写出来的程序w产生死循环，最好是在机器运行它之前，就使用某种方法判定一下这个程序w是好是坏。于是我们就想：是不是能有一个另外的程序P，对于任意给定的输入程序w，能够判断w是会停机的好程序，还是会死循环的坏程序？这就叫做停机问题。根据图灵论文中的证明，不存在判定w“好”或“坏”的程序P，即不存在解决停机问题的通用算法。

计算机的程序可写成一个函数，例如，上面所说的停机程序P，可以写成P(w)。P(w) 是一个二值函数：如果结果是停机，P(w)=0；如果结果是死循环，P(w)=1。然后，我们可以用反证法来简单地证明停机问题无解，证明过程如下。

如果存在一个判断停机问题的程序P(w)，那么我们再构造一个新的程序Q(P(w))，这个程序与P的输出正好相反：如果w经P判断为停机，则Q作死循环；如果P判断w为死循环，则Q立刻停机。

这时，如果我们把w=Q输入P，新程序会得到什么结果呢？结果应该是Q(P(w))= Q(P(Q))。意思是说：P判定Q是死循环，但Q停机了，所以又不是死循环。也就是说，判定的结果是自相矛盾的：说是死循环又能停机，说能停机又变成死循环。因此，出现了计算机判定不了的情况，所以，最初的假设是不正确的，即判定程序P(w)不存在，不能解决停机问题。

图灵的论文是对希尔伯特计划的又一个致命打击，证明了不可能建立一套形式化的数学系统来保证确定性。图灵的研究结果同时也说明，不可能建立一台计算机在有穷步内确定任何公式是否可被证明，即人类思维永远无法被机器取代。

图2：通用图灵机

图灵对计算机和程序给出了严格的数学定义，这个模型后来被称为通用图灵机【1】

通用图灵机的主要结构有三个部分（图2）：状态控制器、读写头、一条无限长的纸带。纸带想象成由表示0或1的小格子组成，代表无限的内存，其中存储内容包括初始数据、运算规则、结果等。读写头是可以从带子上读、写、且能左右移动的“头”，也就是个“扫描器”，扫描器能沿着纸带来回移动，读取纸带上的内容，然后在纸带上进一步打印出更多的内容。状态控制器则指挥读写头，控制整个计算过程，就是根据当前机器所处的状态和当前读写头所指的格子上的符号，通过控制规则，更改状态寄存器的数值。一个能按照规则的“控制器”。计算过程便是重复读写及控制，直到状态变为某个特殊状态，触发图灵机停止运算为止。

改变纸带上的不同程序，便可以让机器执行任何“人类计算机”可以执行的过程。需要强调的是：图灵机并不是某个具体的计算机，而是图灵为了定义“算法”提出的抽象模型。

当时对图灵来说，研究希尔伯特计划很重要，但那只有数学上的意义。今天看起来，他发明的通用计算机对全人类文明社会意义非凡。

当然，正如前面说过的，即使抽象的通用图灵机可以模拟所有数学问题，也不能解决所有数学问题，比如“停机问题”。

图灵在42岁时，因为他的同性恋倾向遭受迫害而自杀身亡。图灵死后，人们在他的桌子上，发现一个被咬了一口的含有氰化物的苹果，颇似现在苹果公司的符号，不过这只是巧合。

2

贝尼奥夫

保罗·贝尼奥夫1930年出生于美国加州。在加州大学伯克利分校获得了植物学本科及核化学的博士学位。1960年，贝尼奥夫进入了以色列的魏茨曼科学研究院做博士后。此后他在玻尔研究所从事了六个月的科研工作。从1961年之后，他在美国阿贡国家实验室工作直到1995年退休。贝尼奥夫于2022年91岁在美国伊利诺伊州去世。

贝尼奥夫在阿贡国家实验室从事的是化学和环境科学工作，与量子计算技术没有直接的关系。因此，可以想象，贝尼奥夫的量子计算工作是靠他的“业余爱好”完成的。也许早年与玻尔共事的一段经历启发他思考物理学中的基本问题。他的工作涵盖量子计算机、量子机器人以及逻辑、数学和物理基础之间的关系。

贝尼奥夫除了从事量子信息外，还进行传感研究，探索用于进行实验的‘量子机器人’的概念。这在当年并不流行，是冷门领域，但他因为这些研究成为相关领域的先驱。总之，贝尼奥夫是一位非常有创意的思想家，他并不一定热衷于探索当时的‘热门事物。这是值得我们所有人学习的优秀的科学素质。

通用图灵机的理论是计算学科最核心的理论，那么，图灵机的量子版本应该是个什么样子，如何实现呢？贝尼奥夫在论文中【2】，将图灵机中的每个组成部分和操作，与他量子系统中的物理量对应起来。例如，他用自旋为1/2的粒子串起来的的一维晶格，对应于图灵机的无限长纸带。在晶格中的每一个固定位置的自旋粒子，均可作为寄存器。用一个沿着晶格移动的无自旋粒子，可以构成量子图灵机的读写头。量子图灵机的所有可能状态则由粒子1/2自旋的不同投影组成。量子图灵机进行的每一步计算，对应于每一个粒子自旋状态的变化。

图3：量子图灵机

贝尼奥夫通过图灵机的薛定谔方程描述，证明计算机可以在量子力学定律下运行。贝尼奥夫的工作为量子计算领域铺平了道路，被公认为是量子计算机的第一个理论框架。

实际上，将图3与图2比较可见，量子图灵机和经典图灵机的本质区别说起来很简单，就是在于用自旋为1/2的量子叠加态来替代了（0、1）的二进制逻辑。用现在计算机科学的术语来说，就是用量子比特来代替比特。

3

Qubit-来源

量子比特从英语Qubit翻译而来，这个术语1992 年才被发明出来并开始使用，它起源于两位美国理论物理学家伍特斯和舒马赫之间的一次有趣的对话。

图4：发明Qubit术语的科学家

威廉·伍特斯（William Wootters，1951-）是一位美国理论物理学家，也是量子信息理论领域的创始人之一，他在 1982 年与Wojciech H. Zurek的联合论文中，证明了量子不可克隆定理。

本杰明·舒马赫（Benjamin Schumacher，）也是美国理论物理学家，主要研究领域为量子信息论。他发现了一种将量子态解释为信息的方法，将信息压缩在一个状态中，这现在被称为舒马赫压缩，是香农无噪声编码定理的量子模拟。

伍特斯和舒马赫都曾经是著名物理学家惠勒在奥斯丁德州大学的学生，惠勒以善于用短语来概括深奥的物理概念而闻名，黑洞、虫洞都是他的发明。伍特斯和舒马赫也许继承了这个传统，有次他们开车前往机场，在讨论量子信息的过程中，发现语言中缺少了点什么，造成了似乎不能简洁地描述量子信息问题。于是，他们有了一个想法：“可能有必要为量子信息创建一个新的测量单位！”，接着，便冒出了“Qubit“这个词汇。

一开始他们觉得这很搞笑，因为Qubit的发音使他们想起了一种古老的长度单位“Cubit”（肘），是基于人体从肘部到中指尖的距离。古代有几个民族，都使用过这个单位，例如，肘是圣经中的诺亚方舟的计量单位。

但之后他们认为这是一个好主意，应该将这个术语引入学术界。因此，在1992年达拉斯举行的一次量子计算会议上，舒马赫在作演讲时便强调了一个重点：计算机如何编码信息？众所周知，普通计算机以bit的形式存储和处理信息，位（bit）是二进制数字的缩写，即二进制算术中的 1 和 0。但如果要谈论量子计算，使用比特并不是正确的方式。您需要一个描述“量子信息量”的单位，这就是 Qubit！因此，舒马赫在达拉斯会议上的演讲成为了第一次使用和定义该术语Qubit的科学演讲【3】。

4

量子比特vs比特

综上所述，量子计算与经典计算的主要区别是运算单元：经典计算机的基本运算单位是比特，而量子计算机的基本单元是量子比特。量子比特也叫量子位或量子元，实质上也就是等同于量子物理中的叠加态，或者是图3的量子图灵机中画的“自旋1/2”的粒子，或者也就是通常比喻的“薛定谔的猫”，又死又活！表达的都是同一个意思：Qubit。

理解叠加态，理解量子比特，是理解量子计算技术的关键。

虽然量子比特与比特，只区区相差“Qu”两个字母，但其物理内容却完全不同，具体实现更是天壤之别。比特的（0、1）两个数值，用电压的“高和低”很容易实现，而要实现量子比特，尽管有多种方法，但都非常困难。

比特只有两个可能的状态，即0和1。一个寄存器在任何时刻，只能处于两个状态之一：或是0，或是1。而量子比特是一种叠加态，它有两个本征态，即|0>和|1>，也可以将它们形式地对应于经典的0和1。但是，一个量子寄存器在任何时刻的状态|y>，不是“之一”，而是两种本征态的叠加：

此外，可以忽略没有物理意义的整体相位，这样一来，4个实参数便只剩下两个。被两个参数描述的所有叠加态，在4维实数空间中构成一个超曲面。更进一步，该超曲面对应于3维欧氏空间的一个球面，这就是我们常见到的表示量子比特的布洛赫球面，见图5右。

图5：比特和量子比特

图5中，两个孤立点（0，1）描述的比特，及描述量子比特的布洛赫球，十分形象地显示了比特和量子比特的异同。不同的是：比特只有两个状态，而量子比特可能的状态有无穷多，因为布洛赫球面【4】上有无穷多个点，每个点都是一个叠加态。但比特和量子比特也有相同之处，那就是：任何时刻所处的状态只是一个：比特或是0或是1；量子比特任何时刻的状态对应于球面上一个固定点，但这个点不只是|0> 或|1>，一般来说是它们的叠加，即既是|0> 又是|1>。

布洛赫球面以瑞士裔美国物理学家费利克斯·布洛赫（Felix Bloch，1905年- 1983）命名，布洛赫是一位诺贝尔物理学奖获得者，他对理解晶格中的铁磁性和电子行为做出了基础理论贡献，荣获1952年诺贝尔物理学奖。他也被认为是核磁共振的开发者之一。布洛赫球面，是他一个小作品。

图6：布洛赫球面的来龙去脉

我们在图6中简要总结了一下用布洛赫球面来表示量子比特的逻辑思路。如图6所示，量子比特（叠加态）|y>可以表示为球面上的一个点，因此，之前的公式（1）可以写成：

公式（3）是用球坐标中的极角q和方位角j两个参数，来表示布洛赫球面，也就是量子比特。此外，量子比特作为一种叠加态，有两个关键点必须强调。

1. 量子世界的本质是随机的，这个意思可以从本征态叠加态之关系理解。本征态和叠加态是相对的，依赖于物理量，也取决于（量子比特）基底的选择。例如对薛定谔的猫，一般我们说 “死猫”与“活猫”是基底，又死又活、半死不活是叠加态。然而这不是绝对的，也可以将又死又活 半死不活当作基底态，而“死猫” “活猫”便成为了叠加态，见图7。因此，原以为是固定态的基态，实质也是叠加态，所以本质上都是叠加态。

图7：叠加态和本征态是相对的

2. 叠加态叠加什么？叠加的是概率幅不是概率。概率幅和概率是不一样的，它们的区别很重要。如果两个本征态互不正交，概率幅叠加会产生干涉项，见图8。概率幅叠加后，模的平方中，除了两个基态系数模之外，还有两个基态的相干项，包含了两个波函数相对相位的信息，即两个波函数是相干的。

而经典的概率叠加，仅是概率混合的统计现象。量子物理中概率幅的叠加，反映了波动的本质。量子叠加能产生干涉，多种状态同时存在，使得量子计算机能同时对多种状态进行计算，即可以对特定算法进行平行计算，这是量子计算快于经典计算的奥秘所在！

图8：概率幅叠加产生干涉项

机器的“计算”是什么意思呢？经典计算中有许多逻辑门：例如AND（与门），OR（或门），以及NOT（非门）、与非门、或非门等等。这些逻辑门的各种组合，将各个“比特”的0、1状态变来变去，便能够完成各种复杂的计算。量子比特也需要类似的概念：“量子门”！这将在下一篇介绍。

参考文献

【1】通用图灵机-维基百科：https://zh.wikipedia.org/wiki/%E9%80%9A%E7%94%A8%E5%9C%96%E9%9D%88%E6%A9%9F

【2】"The Computer as a Physical System: A Microscopic Quantum Mechanical Hamiltonian Model of Computers as Represented by Turing Machines", Paul Benioff, Journal of Statistical Physics, 22, 563, 1980.

【3】Quantum coding，Benjamin Schumacher，Phys. Rev. A 51, 2738 – Published 1 April 1995.

【4】布洛赫球面-维基百科：https://zh.wikipedia.org/wiki/%E5%B8%83%E6%B4%9B%E8%B5%AB%E7%90%83%E9%9D%A2

由于微信公众号乱序推送，您可能不再能准时收到墨子沙龙的推送。为了不与小墨失散， 请将“墨子沙龙”设为星标账号，以及常点文末右下角的“在看”。

转载微信原创文章，请在文章后留言；“转载说明”在后台回复“转载”可查看。为了提供更好的服务，“墨子沙龙”有工作人员就各种事宜进行专门答复：各新媒体平台的相关事宜，请联系微信号“mozi-meiti”；线下活动、线上直播相关事宜，请联系微信号“mozi-huodong”。

墨子是我国古代著名的思想家、科学家，其思想和成就是我国早期科学萌芽的体现。墨子沙龙的建立，旨在传承、发扬科学传统，倡导、弘扬科学精神，提升公民科学素养，建设崇尚科学的社会氛围。

墨子沙龙面向热爱科学、有探索精神和好奇心的普通公众，通过面对面的公众活动和多样化的新媒体平台，希望让大家了解到当下全球最尖端的科学进展、最先进的科学思想，探寻科学之秘，感受科学之美。

墨子沙龙由中国科学技术大学上海研究院及浦东新区南七量子科技交流中心主办，受到中国科大新创校友基金会、中国科学技术大学教育基金会、浦东新区科学技术协会、中国科学技术协会及浦东新区科技和经济委员会等支持。

关于“墨子沙龙