秀尔的算法和诗

尽管费曼等人在1981年MIT会议上揭开了量子计算的序幕，但并未引起很大的反响，直到十几年后，美国数学家秀尔提出“秀尔量子算法”，才让量子计算研究开始步入快车道……

撰文 | 张天蓉

01 秀尔其人

彼得·秀尔（Peter Shor，1959 -，也称彼得·肖）目前是麻省理工学院（MIT）的应用数学教授，他出生于纽约市，在华盛顿特区和加利福尼亚州长大。秀尔从小表现出极高的数学天赋，就读高中时，他获得美国1977年数学奥林匹克竞赛第三名，同年又赢得国际数学奥林匹克竞赛银牌。1981年，他在加州理工学院获得数学学士学位，1985年，他在麻省理工学院获得应用数学博士学位。

在麻省理工学院获得博士学位后，秀尔在加州大学伯克利分校做了一年的博士后，然后接受了新泽西州贝尔实验室的职位。正是在那里，他开发了Shor算法，解决了大质数的因式分解问题。

费曼1981年在MIT作有关量子计算的主题发言时，秀尔还是加州理工的大四学生。他并不知道费曼演讲的内容，因为他主攻数学。不过，秀尔也对物理感兴趣，听过费曼的理论物理课。1985年，他又读到大卫·多伊奇关于量子图灵机、量子计算以及量子邱奇-图灵论题的文章。

秀尔发现，多伊奇和费曼在考虑量子计算时，都在思考着量子的基础，使他直觉意识到这很重要。不能“闭上嘴去计算”，必须思考量子的古怪性，继而才能思考量子古怪性的可能用途。

之后，秀尔听了查尔斯·本内特在贝尔实验室做的一次量子信息报告，以及1992年优曼许·沃兹内尼到贝尔实验室来做关于量子图灵机报告。秀尔开始思考是否可以用量子计算机更有效地解决一个实际问题，但没能真正取得进展，直到读到丹·西蒙的文章。据说丹·西蒙的出发点是想证明数字计算机比量子计算机强大，但他最终找到一个问题显示了相反的结果。

图1：彼得·秀尔的贡献

西蒙用了一个傅里叶变换来找出一个函数的周期。这点启发秀尔开始寻求在量子计算机上解决离散对数问题的方法。离散对数问题是一个有名的难题，如果你解决了它，很容易就找到了因数分解算法，就可以破解一些公钥加密系统，例如RSA。

秀尔算法一出，立刻带来了两个显著效应，一是展示了量子计算可以在质因数分解问题上实现比经典计算机近乎指数级别的加速，二是对密码学界的研究造成了不小的冲击，因为它可以用于破解互联网上广泛使用的RSA协议，给信息安全提出了新的挑战。这些都极大地引起了学界对量子计算、量子通信的重视和投入，开启了量子计算研究的热潮。

然而，因为量子比特的特殊性，无法直接观测，因而缺乏有效的纠错手段。两个主要的量子力学原理，海森堡不确定性原理和量子不可克隆定理，被视为纠错的最大阻碍。海森堡不确定性原理是说你无法完整地测量出量子态，量子不可克隆定理则是说你无法复制一个未知量子态。

面对以上挑战，秀尔再次挺身而出，构造了第一个量子纠错码方案，他把3位重复码嵌入另⼀个码。也就是说，将⼀个逻辑量子位，用9个物理量子位进行编码。秀尔的方案可以防止并纠正任何⼀个物理量子位上发生的任意量子错误。在这些发展之后，人们开始寻找其它的量子纠错码。

秀尔也提出了办法来克服量子态退相干不可测量的问题，以及量子比特不可克隆的困难，基本思想就是利用量子纠缠这个量子世界的独特现象。秀尔让编码⼀个逻辑量子比特的9个物理量子比特互相纠缠在一起。有关量子纠缠这方面我们不予详细介绍，有兴趣者可参考相关文献。

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

02 秀尔算法

秀尔量子算法是量子计算的一块金字招牌。

因为假如有了可用的量子计算机，我们便可以用秀尔算法破解目前保障银行安全常用的RSA加密算法。RSA的基础是因数分解问题。加密过程中将两个互素数p和q相乘得到N = p*q。加密是作一次乘法就完成的简单操作，但是反过来的解码过程则非常困难。

对经典计算机而言，RSA算法作“质因数分解”的解码过程的时间复杂度是指数级别。例如，要分解d个十进制数字相乘的整数N，蛮力算法需要遍历所有素数p直到sqrt(N），检查是否p能整除N。分解d=230的N需要1025次运算。2021年最快的经典计算机每秒钟运算1200万亿次（1.2x1015 /s，也得运算2000年左右）。

然而，秀尔量子算法[1]展示了：在量子计算机上，因数分解问题可以在N的多项式时间内被有效解决，即足够大的量子计算机可以破解RSA。IBM于2001年成功展示秀尔算法实例，使用7个量子比特的量子计算机，将15分解成3×5，之后又分解21=3x7。这两个数字都很小，但却表明了秀尔算法具体实现的可能性。

秀尔的整个算法，分为经典算法和量子算法两部分。经典算法用来完成经典计算方法本就可以在多项式时间内完成的部分，而将最困难的“傅里叶变换估算周期”，留给量子算法解决。

图2：秀尔算法总体流程图

如图2所示，秀尔算法将一个大整数分解为两个素数因子的过程，转化成了两部分：“外围的”数论部分和“内部的”周期查找问题。数论部分可以用经典计算机在多项式时间复杂度内完成。但是，周期查找问题对经典而言关键且困难，对此问题经典算法的复杂度是指数级别，而秀尔用量子计算机可将复杂度降到多项式级别。

秀尔算法中只有“周期查找”这一步，是需要在量子计算机上完成的，其他都可在经典计算机上完成。量子计算机运行完“计算周期”的子程序后，就会将结果，即周期r，返回给经典计算机，让它继续完成计算过程。

实际上，量子计算和经典计算各有利弊。量子比特的特点是叠加态，有可能被利用来实现并行计算而加快算法，但是，在量子计算的过程中一般不进行（或少进行）测量，因为测量伴随着叠加态的塌缩，一旦塌缩到一个本征态，便失去了量子计算的优势，而经典计算有容易掌控的优越性。因此，专家们认为，量子计算机或许永远不会单独存在，而是一直和经典计算机配合执行任务，各展其长。输出、输入以及复杂度简单的部分由经典计算完成，特殊问题的困难部分由量子计算完成，就像秀尔算法这样，便是用经典与量子配合起来完成破解RSA密钥的过程。此外，与许多量子算法一样，秀尔算法是概率性的。也就是说，它以高概率给出正确答案，并且通过算法的重复来降低失败的概率。

总结一下秀尔量子算法：

1，经典部分，利用数论知识，将因式分解化为周期查找问题；

2，量子部分，使用傅里叶变换计算经典部分要求的周期。

下面两个视频，分别概括了秀尔算法中的这两个过程：经典部分和量子部分【前往“返朴”观看视频】。

图3（视频1）：秀尔算法的经典部分

图4（视频2）：秀尔算法的量子部分

从视频2中我们看到：秀尔算法的量子计算部分，几乎利用了量子计算机的所有优势：一是叠加性，即量子位的多重表示。就是用哈达玛达门（Hadamard）制造出均匀叠加，叠加态可以同时进行平行运算，但却不能测量。因为一旦测量，便会塌缩到所有本征态的其中之一。因此，最好的办法是将量子算法部分“包”在经典部分的中间，例如秀尔的量子部分包括QFT（量子傅里叶变换）在内。从经典部分给量子部分输入少量的参数，量子给经典返回周期的数值。而将大量计算量，利用量子比特的平行运算能力，在量子计算机内部完成。量子计算部分被包住了，不测量就不会塌缩！然而，秀尔也巧妙地利用了量子态之间的纠缠性，引起部分塌缩但仍然保持叠加态。另外，量子傅里叶变换利用了量子相干性，因为物理中干涉衍射，其数学本质就是傅里叶变换。

03 纠错和容错

量子比特既棘手又脆弱。有用的量子计算机需要使用有效的纠错技术。

秀尔是怎样具体进行量子纠错呢？再次回想一下经典纠错，比如说：用“000”和“111”来代表“0”和“1”的方案，如果“000”中有一个比特发生了翻转，我们通过读出这三个比特发现错误，就可以纠正它。当然也有可能两个比特同时发生错误，这时纠错则将导致最终的错误。这样的话，会不会“越纠越错”呢？经典纠错不会，因为根据概率规则，两个错误同时发生的概率是发生一个错误概率的平方，而经典计算出错概率很小，例如假设是万分之一，那么这个小概率的平方只有亿分之一，更多的重复编码，可以把错误率逐步降低到几乎为0，这就是经典纠错的基本机制。

图5：秀尔纠错码，将单个量子比特的状态印在九个量子比特上

量子纠错遵循同样的思想。但量子比特除了（0、1）翻转之外，还有相位的变化。量子比特位的0和1发生翻转的错误，被定义为X错误，符号（相位）发生翻转的错误被定义为Z错误，这两种错误也有可能同时发生，这时将其定义为XZ错误。因此，量子纠错需要纠正这三类错误（X、Z 、XZ）。纠正X错误的情况与经典情况一样；为了纠正Z错误，可以用“000”和“111”的叠加态“+++”和“---”来编码。如此，一共就需要9个物理量子位，巧妙地组成某种嵌套式的编码，就可以同时纠正X和Z的错误，以及XZ错误了。这个用9个量子比特来代表一个逻辑量子比特，就是当年秀尔提出的第一个量子纠错码[2]，图5。

原则上，秀尔的“9个量子比特”代码可以保护单个逻辑量子比特免受错误的影响。但是，如果错误测量本身存在错误怎么办？那么，在尝试纠正不存在的错误时，计算系统可能会翻转一个位，并在不知不觉中引入一个真正的错误。在某些情况下，这可能会导致一系列错误在代码中的传播。

因此，在1996年，秀尔又提出了容错的概念。只要错误发生的概率低于某个阈值，容错代码便可以处理由环境、量子比特的不完美操作甚至纠错过程本身引入的错误。

如此一来，科学家们希望实现的目标便是“容错量子计算”。在这种计算中，建立起足够的冗余和适当的编码，使得即使有几个量子比特出现错误，系统仍能运行并返回准确的答案。量子比特数的扩张，以及量子纠错技术的重大进展，是实现量子计算的关键和挑战。

04 秀尔和诗

难得的是，秀尔不仅是数学家，还是一位诗人。他从小就喜欢诗歌，父亲给他读诗。在过去的四十年里，他也偶尔写诗和翻译诗歌，出版过诗集。例如，秀尔有一首“量子”之诗，描写量子现象之诡异[3]。

The Quantum（by Peter Shor）I am the spooky action at a distance,The seething chaos that fills up empty space,The wave function collapse that you shall never witness,The living grin upon the dead cat’s face.Am I a wave? Am I a particle? Am I analog or digital?The answers surely must be both or none.My laws say quarks and clocks alike show interference,That if you watch a state, it never changes,That two entangled systems act as one.I make superconductors lose all their resistance,I make the atom split, the laser gleam,And although you may be bewildered by my strangeness,I am real! ... You are living in a dream!

我将它翻译成中文：

《量子自述》（作者，彼得·秀尔）

吾乃深远幽之灵，

盈虚空间沸而腾。

波函数溃无以证，

死猫鲜活笑面迎。

亦粒亦波诡异事，

二者兼之或非矣？

夸克时钟皆干涉，

二物纠缠如我律。

吾令原子激光耀，

吾令超导电阻失。

妖物鬼魅大师惑，

君于梦境余为实。

参考资料

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

[2] Shor, Peter W. (1995). "Scheme for reducing decoherence in quantum computer memory". Physical Review A. 52 (4)

[3] PeterShorHomePage：https://math.mit.edu/~shor/

本文经授权转载自微信公众号“墨子沙龙”。

特 别 提 示

1. 进入『返朴』微信公众号底部菜单“精品专栏“，可查阅不同主题系列科普文章。

2. 『返朴』提供按月检索文章功能。关注公众号，回复四位数组成的年份+月份，如“1903”，可获取2019年3月的文章索引，以此类推。