Peter Shor：量子计算的早期岁月

来源：中国信息协会量子信息分会

从1911年的首届会议开始，索尔维物理学会议就一直对量子物理的发展起着推动作用。

今年5月，第28届索尔维会议在布鲁塞尔召开，会议主题为“量子信息的物理”。量子计算先驱彼得·肖尔出席会议并做了报告。这是肖尔的报告文稿，将收入会议文集中。

01

摘要

我重新梳理了关于量子计算早期进展的一些记忆片段。这些进展包括因数分解算法、纠错码以及容错的发现。

彼得·肖尔 来源：麻省理工大学

02

正文

这个演讲最初是为了纪念1981年在恩迪科特大楼举办的物理与计算会议的40周年而准备的，所以我觉得我应该从1981年说起。

我那时是加州理工的大四学生，所以当费曼为恩迪科特大楼会议准备主题发言时我已经在那儿了，而那次发言成为了最早仔细审视量子计算的几次尝试之一。

我在加州理工的时候什么消息也没听到，事实上我很久以后才读到费曼的文章。

不过我倒是想提一下我听他在加州理工的另一个讲座，因为那个讲座表明他那时正在思考物理学基础方面的问题。

费曼的报告是关于负概率的。

在报告开头，他解释说他一直在思考贝尔定理，因为它说明量子物理不可能是一种局域的、实在的隐变量理论。

这就意味着，量子力学的任何解释要么要求非局域性，要么要求非实在性（这里局域性意味着信息不能超光速传播，而实在性意味着你能测量的东西对应着粒子的具体性质）。

费曼解释说他所做的就是仔细审查证明贝尔定理用到的前提，看里面是否存在隐藏的假设。

他确实找到了一个——那就是所有概率都必须在0和1之间。

这并不像初听起来那么古怪——简谐振子的维格纳函数的行为就恰好这样，而且费曼也提到了这一点。

他接着展示了他发现的关于负概率的一些结果；报告的这部分内容我记得不是很清楚了。

更早的时候，在1964年的系列讲座上，费曼曾说：

"我来告诉你大自然到底是怎样的。如果你直接接受她表现出来的样子，你会发现她是迷人的、令人愉快的。如果你能忍住，就不要老是问自己，‘它怎么会是那样子的呢？’，因为你会‘深陷泥潭’，进入到一个没人能逃脱的死胡同中。没人知道它为何那样。"

但是这时，15年后，他却在探讨自然为何会是这样的一个可能的原由。从这里你可以看出来费曼并没有采纳他自己的建议。

当然，也许他的建议不是给终身教授，而是给研究生们的；对他们来说，那可能是很好的建议——在量子力学的基础上得出新的、重大的结果是相当难的，所以它对研究生来说不是一个好的课题。

几年后的1983年，费曼把报告中的一些想法写了下来，写成了一篇叫做“负概率”的文章，但文章在那好多年后才得以发表。

那篇文章有趣的地方在于，它并没有提到作为动机的贝尔定理。

他的文章首先讨论了维格纳函数，这些函数确实给出了负值的概率。费曼接着将维格纳函数推广到自旋系统的量子比特。

而费曼在他的报告中讲述的原始动机已经被消除量子场论中的无穷大所取代。因此想必费曼的原始想法并不奏效——他没能利用负概率解决爱因斯坦-波多尔斯基-罗森（EPR）悖论。

我不知道究竟是什么导致了动机的改变。难道他觉得试图找出一种更好的方式来理解贝尔定理这个动机太丢人了，因为这牵涉到量子力学的基础，所以他想出了一个更加体面的？或者是还有别的什么原因？

我还想说说那个年代另一篇有趣的文章。

1985年，大卫·多伊奇写了一篇关于量子图灵机、量子计算以及量子邱奇-图灵论题的文章。

多伊奇的动机部分源自于量子力学的基础——他宣称有了量子计算机，就有可能检验量子力学的埃弗里特（多世界）解释。

他在文章中说："对这些性质的直观说明给埃弗里特之外的所有量子理论解释带来了无法承受的压力。"

我想表明在这一点上我并不认同他，尽管他一直没有改变观念。

1985年，费曼写了他1982年文章的续篇，其中给出了如何建造量子计算机的详尽得多的提议。不过这一提议仍然不太切实可行，因为它在构建初态和跃迁振幅上要求极其高的精度。

作为一个有趣的旁注，我想指出当大卫·多伊奇和理查德·费曼在考虑量子计算时，他们都在思考着量子基础。我的直觉是这很重要。

如果你认同了大卫·梅尔曼版本的哥本哈根解释——“闭上嘴去算吧”——那么你就不会去思考量子的古怪性，这样你可能也就不会去思考量子古怪性的可能用途。

在加州理工，我学了一些物理课程，但主修数学。

我接着去了麻省理工的应用数学研究生院，在那里研究数学与计算机科学的交叉部分，并最终在贝尔实验室找了一份数学和计算机科学方面的工作。

我第一次听说量子信息是在查理·本内特在贝尔实验室做的一次报告上，他在报告里讲述了BB84量子密钥分发协议（译注：该协议由Bennett与Brassard于1984年提出，故名）。我不记得那是哪一年了，不过肯定是在80年代末期。

我记得我对他的报告非常着迷，还思考过一阵查理提出的一个未解难题。这个难题就是你能否严格证明BB84协议是安全的。

在思考过程中，我完全不清楚如何将量子力学表述成某种数学形式，以便严格证明该协议是安全的。所以我放弃了那个问题。

说起来有点好笑，到了2000年，在我熟知了量子计算、量子信息和量子纠错码之后，约翰·普雷斯基尔和我倒是想到了BB84安全的一种简单证明方式。

这已经是BB84安全性的第三种证明，不过前两种证明，分别由迈耶斯和比哈姆等人完成，相当复杂。

我仔细读了迈耶斯的证明并意识到CSS编码（译注：即Calderbank-Shor-Steane编码，后文有详细介绍）隐含在其中，而如果使用这些编码，你可以得到一种简单得多的证明。

在本内特在贝尔实验室的报告之后，我再也没想起过量子计算，直到1992年优曼许·沃兹内尼到贝尔实验室来做报告，讲述他和伊桑·伯恩斯坦关于量子图灵机的文章。

这篇文章后来发表在1993年6月的计算理论研讨会（STOC）上，最负盛名的两个理论计算机科学会议之一。

我对那个报告极为着迷，而且我可能比其他计算机科学家理解得都深一些，因为我在大学时学过一些物理。

伯恩斯坦和沃兹内尼给出了一个精心设计的问题使得量子计算机看起来可以做得更好，但我对那个问题不是太满意。

于是我开始思考是否可以用量子计算机更有效地解决一个实际问题。

我并没能真正取得进展，直到我读到丹·西蒙的文章。

他在文章里用量子计算机算法解决了一个人为问题，“西蒙问题”，并且比最好的经典算法还要好得多。

我会读到这篇文章是因为我在1994年STOC会议的项目委员会里，而委员会拒收了那篇文章（尽管我已争取了）。

我听说丹·西蒙的出发点是想证明数字计算机不再比量子计算机强大，但他最终找到一个问题显示了相反的结果。

西蒙用到了一个二进制矢量空间上的傅里叶变换来找出该矢量空间上一个函数的周期。

我知道傅里叶变换对寻找周期有帮助，而且我知道离散对数问题跟周期性有关，所以我开始寻求在量子计算机上解决离散对数问题的方法。

离散对数问题是一个有名的难题，如果你解决了它，就可以破解一些公钥加密系统。

西蒙算法和离散对数问题中的周期寻找的差异在于，对于西蒙问题，你需要在n-维超立方体上找到一个函数的周期，而对于离散对数问题，你需要在P-1×P-1环面上寻找周期。

左图，超立方体顶点上周期寻找的例子。这里的周期是（1,1,0）。右图，2-维环面上周期寻找的例子。这里的周期是（2,1）。

如何从一个高维超立方体上的周期寻找转到一个大的环面上的周期寻找，这是完全不清楚的。对这些你需要不同的量子傅里叶变换。

我最先做到的是在一种特殊情况下解决了离散对数问题，而这种情况已经被经典计算机在多项式时间内解决了。

尽管这并没有真正给出新东西，但算法跟经典算法是完全不同的，所以给了我很大的鼓舞，让我去继续努力并最终解决了一般情况。

我从特殊情况到一般情况的顿悟就是认识到对于一般情况，我并不需要采用模P-1的傅里叶变换；我只需要模一个比P-1稍大一点的数就可以了。

我并没有告诉任何人我在致力于离散对数问题，因为我觉得实在没啥把握。

在我1994年4月解决它之后，我告诉了一些认识和合作过的人，包括我的老板大卫·约翰逊，以及贝尔实验室的一个同事，杰夫·拉加里亚斯，他验证了我的算法是对的。事实上，不完全对——杰夫找出了一个小错误，很容易就改好了。

之后，大卫·约翰逊建议我在亨利·朗道研讨班上就此做一个报告。

亨利·朗道研讨班每周二举行，并且听众极其活跃——他们不断打断报告人提问，所以有点吓人。我记得有一次，报告人就没能翻到第二张幻灯片。

不管怎样，我就如何在量子计算机上解决离散对数做了一个报告，并且还算顺利。

那周晚些时候，我把因数分解问题也解决了。离散对数和因数分解之间有着奇怪的联系。并没有一个公式告诉你，如何将针对其中一个问题的算法应用到另一个上面去。

但是，每次有人发现其中一个问题的改进算法，人们都相当快地想出了另一个问题的相似解法。

这一次也不例外——知道了离散对数算法，很容易就找到了因数分解算法。

那个周末，我得了重感冒在家，优曼许·沃兹内尼打电话给我说“我听说你可以用量子计算机有效分解因数”。

这有点出人意料，原因有很多。首先，这表明我周二报告的流言已经传播到优曼许那里了。其次，报告是关于离散对数的，但等流言到达优曼许那里时，它们已经变成了因数分解（这有点像电话游戏，也叫传话游戏，其中一个小道消息从一个玩家传到下一个，并且沿途改变）。

不过幸运的是，我同时也解决了因数分解问题，所以可以向优曼许解释因数分解算法，而不用告诉他信息有误。

在那之后，消息像野火一样蔓延开去。

四月末哥伦比亚大学有一个（关于理论计算机科学的）理论日。查理·本内特、约翰·斯莫林和我约好在那会面，然后我向他们解释了这个算法。

如果我记得没错，本内特给我解释了他新近的隐形传态协议，以及新近的伊利泽-威德曼炸弹测试协议。很明显量子信息这一主题的时代已然来临。

我被紧急邀请去五月初在康奈尔举办的算法数论讨论会上做了专题讲座。

五月中旬在圣塔菲有个关于量子力学的会议；我去不了，不过优曼许在会上展示了我的算法。阿图尔·埃克特和大卫·乔萨写了一篇文章向物理学家们解释我的算法，并且阿图尔·埃克特在那年八月科罗拉多州博尔德举办的原子物理会议上就此做了报告。

这就是许多物理学家如何得知它的，正如你在这次会议上从大卫·瓦恩兰的报告里听说的那样。

在此期间，我收到了许多杂志的采访请求，以及许多人索要文章副本的请求。（我在文章彻底完成之前就开始寄出去，但这可能是个失误，因为在我纠正了文章中的错误之后很久，还有人问关于早期初稿中错误的问题。）

那年八月，美国国家标准技术研究所（NIST）在马里兰州盖瑟斯堡组织了一次会议，是专为因数分解算法的发现而组织的，并且聚焦在量子计算上。

十月，在意大利都灵有一个量子计算的研讨会，那其实是一个系列会议里的第二或第三届。这个会最初只有几个人参加，之后与会人数逐年增长，直到超出了瓜里诺庄园酒店的会议设施容量，于是被终止了。

94年德克萨斯的物理与计算会议是1981年恩迪科特大楼会议的后续（一共举办了三届后续会议，分别在92年、94年和96年），我在那做了报告。

紧接着几天后，我在新墨西哥圣塔菲的计算机科学基础（FOCS）会议上讲述了我的文章，并且在会议文集里发表了。

针对量子计算有一种强烈的反对意见，罗尔夫·兰道尔五月份在圣塔菲研究所的会议上就提出来了。

量子计算机看起来无法提供容错。而在没有容错的情况下，如果你要在一台量子计算机上运行N步，你得保证每一步都精确到1/N。

当N很大的时候，比如10亿（这差不多是你对一个加密上有意义的大数做因数分解所需要的），这在实验物理学家们看来是绝对不可能的。

有两个主要的量子力学原理，海森堡不确定性原理和量子不可克隆定理，被视为纠错的阻碍。

海森堡不确定性原理是说你无法完整地测量出量子计算机的态。量子不可克隆定理则是说你无法复制一个未知量子态。

假定你用不可靠的元件来搭建经典计算机，并且希望让它容错，有很多技术可以使用。

一种是检验点——你周期性地记下你的计算状态，而一旦计算在某个点偏离了，你不用从头开始，只需要在检验点开始就可以了。

另一种技术是纠错码。这些编码利用冗余来帮助你修复在存储中损坏的比特。

最后，还有一种技术是大量冗余。你在计算中保留每个比特的多个副本，并且不断地对它们进行相互比较来修复那些出错的。大量冗余可能是这些技术中最强力的，冯·诺依曼1956年就研究过。

问题在于，量子不可克隆定理似乎表明所有这些都不可行。对于检验点来说，你不能记下你的计算状态再继续计算——这是在做备份。对于大量冗余来说，修复错误涉及备份——如果你有四个好的计算副本和一个坏的副本，由此得出五个好的副本也是不可克隆定理认为不可能的事情。

幸运的是，尽管纠错码看上去也需要冗余，但还能奏效。

虽然在上学的时候没怎么学过，我在贝尔实验室的数学中心待过，所以了解纠错码的一些内容。

最简单的经典纠错码是重复码，这时你给比特做多个备份，然后利用多数票来修复错误。可以运作的最短码是三比特码（因为你需要多数）。

对于量子码你也可以这么做。这一编码如下，它将一个量子比特编入三个量子比特中

这里，代表逻辑量子比特，被编码进三个物理量子比特中。这一编码纠正比特错误，但它让相位错误的可能性变成了三倍。

我意识到存在量子编码的一种变换，就是我们现在所说的阿达马变换，可以把比特错误变成相位错误，反之亦然。这一变换就是

如果你作用上这一变换，你会得到一个相位错误纠正码，它可以纠正相位错误，但会让比特错误的可能性变成三倍。这一编码就是

你可以将这两种码组合起来，通过一种叫做级联的过程，这是经典编码理论中非常重要的一种技术：首先，你将想要保护的量子比特用其中一种量子码编码；接着你将得到的态中的每个量子比特用另一种码编码。

当你将它们用这种方式组合后，你得到如下可以同时纠正比特错误和相位错误的9-量子比特码：

我就是这样发现9-量子比特码的。

经典上，重复码非正式地出现得有几千年了。

不过，更复杂的经典纠错码，比重复码有效得多的，才发现不到五十年的时间，这其中最早的一种是由理查德·汉明发现的。

照此类推，我决定去寻找更复杂的量子纠错码。

我开始把玩经典的7-比特汉明码——仅比重复码复杂的经典码——并发现了其量子版本，它把一个量子比特编码进七个量子比特中，并且纠正一个错误。

这里的关键又是阿达马变换，它把比特错误和相位错误来回转换。经典的汉明码纠正比特错误。不过，如果你把它的码字以适当的方式做成叠加态，就会在阿达马变换下是不变的，从而可以同时纠正比特错误和相位错误。

这给出了7-量子比特的量子汉明码：

我把这一构造展示给罗伯·凯尔德班克，接着我们将它推广成一大类量子纠错码，通过组合两种相互弱对偶的经典码。

安德鲁·司迪恩在差不多同一时间发现了量子汉明码和这种构造方式，所以这些编码如今以它们的发现者命名为CSS码。

在这些发展之后，人们开始寻找其它的量子纠错码。

两个小组，一个在洛斯阿拉莫斯国家实验室，一个在IBM，把这一问题交给了电脑，并且都发现了一种5-量子比特码。

这两种5-量子比特码看起来完全不同，但你可以作用一系列变换，然后看出它们其实是一样的。此外尽管看上去它们明显具有某种结构，这一结构究竟是什么却并不清楚。

当我试着去弄清这一编码的结构时，我决定去做的第一件事就是去找出它的对称群。

我问尼尔·斯隆是如何找对称群的，他告诉我某种软件——确切地说，是MAGMA——并且给了我一个MAGMA程序实例，是他写出来计算他研究中用到的一个群的大小的。

软件显示我的群跟他的群是同样大小，都是5160960。不仅如此，如果仔细观察，会发现它们其实就是同一个群，并且在两个问题之间存在着深层联系。

这引导我们发现了稳定子码理论（丹尼尔·戈特斯曼同时也发现了）。

在此期间还有些其它有趣的进展。

阿列克谢·基塔耶夫听说了因数分解的结果，但因为在俄国，他实在没法拿到文章。于是他想出了结果的另一种证明，这给我们带来了相位估计算法。

而贝尔实验室的洛夫·格罗弗发现了一种量子搜索算法，效率是最好的经典搜索算法的平方。

最后我想谈论的事情是容错。

为了建造量子计算机，光是能用无噪声门进行纠错是不够的；你还得能用有噪声门纠错。这意味着，你纠错的速度得比你引入新错误的速度更快。

冯·诺依曼1956年说明了用经典含噪门如何做到这一点。但对于量子比特这略为棘手——你得弄清楚如何在解码之前对编码的量子比特执行操作，因为一旦解码出逻辑比特，你可能已经将它们暴露在错误之中了。

我意识到对于克利福德群（译注：由阿达马门H，相位门S以及受控非门CNOT生成的群，其中S门的效果是将量子比特绕z轴转动π/2角度。）里的门这是相当直接的，因为对于某一类的CSS码你可以横向执行这些门，也就是说，可以让编码一个逻辑量子比特的第i个量子比特只与其它逻辑量子比特的第i个量子比特作用。

这将码字的第i个量子比特与第j个量子比特分离开来，因此错误不会传播得非常远。不过，这仅仅对克利福德群里的门奏效，而克利福德群的门无法让你做通用计算。

事实上，如果你的量子电路只含有克利福德群里的门，它可以用经典计算机来仿真。

如何在编码的量子比特上执行非克利福德门？

其实我们只需要弄清楚如何实现不在克利福德群里的一个门就行了。我最开始尝试的是在编码的量子比特上实现这个门

当我们把这个门作用到一个任意的编码量子比特上，，会发生什么？我们会得到

对比它与下面这个态

怎样才能把这个态变成需要的态？

我们可以作用一个受控门改变态的符号，接着作用从第二个量子比特到第一个量子比特的CNOT，或者说受控门。（受控泡利门是在克利福德群里的，所以我们可以容错地运行。）这会为我们给出这个态

现在，如果我们在基下测量第一个编码量子比特并且得到结果，我们就得到了所要的态。相反，如果我们得到结果，我们会有态。

于是我们找到了一个流程，可以将一个态顺时针或者逆时针转动2π/3，每个方向各有1/2的概率。

不过，因为顺时针转动这个角度两次会给出逆时针的转动，我们可以重复这个过程直到得到态，而且我们预期要做的转动次数也只有两次而已。

以上想法的困难在于，怎样制备编码态并不清楚。

我花了一些时间和精力，想到了如何使用类似的方式来构建托佛利门（译注：即量子控-控-非门，也叫量子与门）。

我们不再使用辅助态，而是使用。

制备这个辅助态的关键是使用猫态。你可以检验这个态来保证它是包含最多0的态和包含最多1的态的叠加。

你没法轻易检验叠加的相位；不过，如果你小心构建你的电路，这个相位的错误只会导致量子码中的可纠正错误，从而可以用纠错电路处理。

我的文章并没能给出我想要证明的容错结果，也就是阈值定理。

阈值定理是说，如果你有足够低的常值错误率，你可以对任何量子电路构建它的容错版本，并且只承担不超过多项式水平的额外开支。

我的文章的一个不足之处是，它只展示了如何实现有限门集。我说明了如何实现所有的克利福德门和托佛利门。你还可以找到其它一些门的严格构建方式。不过，基于量子容错的本质，任何容错协议都只能执行有限的门集。

这是因为，如果它可以容错地实现依赖于一个连续参数的一族门，你是没法区分该连续参数的两个相近值的。因此，你所需要做的是找到一组离散门集，对较小数目量子比特上的任意幺正变换给出很好的近似。

索罗维-基塔耶夫定理表明这是可行的。事实上，这一定理表示，如果SU(k)中的任意有限门集可以生成SU(k)中稠密的一个群，那么SU(k)中的任意门都可以用这个门集的一个相对较短的序列来很好地逼近。

利用这一点你可以证明，如果对能生成SU(k)中稠密的一个群的任意门集实现了容错操作，你可以用这些近似去构建一个容错电路，使得它能足够好地逼近任何电路，并且只需要承担多对数的额外开支。

我的文章也没有说明量子计算机能够完全容错地建造。

它表明，如果你的量子硬件的错误率是ε，你可以运行数量级的门，使得总错误率较小，这里c是某个常数。

可是，我真正想证明的是，存在某个阈值，如果错误率ε在这个阈值之下，任意长的运算都可以容错地进行。

两个研究组最终证明了这一结果，通过将我的构造自我级联很多次。要计算n步，你需要级联loglogn层，并为此付出多对数的开支。

阿列克谢·基塔耶夫发现了另一种执行容错量子计算的方法，通过利用拓扑码。

阈值定理的发现说明量子计算机在技术上也许是可行的（尽管仍然很困难），从而导致了对各种实际建造路线的研究的大爆发。

原文链接：

The Early Days of Quantum Computation，Peter W. Shor, arxiv:2208.09964, https://arxiv.org/abs/2208.09964

相关阅读：

每周一到周五，我们都将与光子盒的新老朋友相聚在微信视频号，不见不散！

你可能会错过：