Peter Shor，美国麻省理工学院数学系教授。Shor最著名的工作在量子计算方面，特别是用于设计量子算法，现在称为“Shor算法”，其分解速度比数字计算机上运行速度最快的算法要快。Shor于1959年出生于纽约市，他在帕萨迪纳的加州理工学院（Caltech）获得数学学士学位和博士学位，在麻省理工学院（MIT）的应用数学和加州大学伯克利分校做博士后研究。1986年，他加入新泽西州Murray Hill的AT＆T贝尔实验室，并于1997年搬到新泽西州Florham Park的AT＆T实验室。自2003年起，他成为麻省理工学院应用数学教授。他曾获得奈望林纳奖、哥德尔奖、麦克阿瑟奖、墨子量子奖等奖项。

视频

【墨子沙龙】Peter shor——量子计算与大数分解_腾讯视频

图文

先介绍一些计算发展历史的背景，以及一些计算实例，比如因数分解算法。然后介绍一下因数分解算法的发现历程，最后讲一下因数分解算法的内容。

计算发展历史的背景

计算机和物理实验有什么不同呢？有很多可能的答案，其中一个答案就是电脑能回答数学问题, 而物理实验回答物理问题。比如说要分解一个很大的数字, 一个好办法是用计算机来计算；而如果想要测试所有物体是否以相同的速率下降, 这时不会用电脑, 而是如果中所示，伽利略测试两台计算是否以相同的速度下落。

另一个答案是：物理实验是一个非常大的定制仪器,也许会占据整个屋子, 而计算机就是一个小盒子，可以放在桌子上或公文包里。现在让我们回到上世纪五六十年代，这时计算机刚刚问世，你能分辨图中哪个是计算机，哪个是加速器吗？

左边这个是粒子加速器，上世纪60年代，位于劳伦斯伯克利实验室，右边这个是神奇的ENIAC，它是上世纪五十年代发明的世界上第一台计算机，位于宾夕法尼亚大学。这两台仪器都是非常巨大，但之后计算机越来越小，而粒子加速器却越来越大。为什么会这样呢？这是因为你不需要对每个数学问题都建造一台新的计算机。这意味着建造计算机的人可以使用大规模生产，使它们可以越来越高效，越来越便宜，越来越小。而做物理实验的人每当遇到以前的实验结果无法回答的问题时，就只能设法突破物理实验的极限。(比如加速器要越来越大)

计算理论始于20世纪30年代，那时候计算机还没有发明。上世纪三十年代，在数学逻辑方面，哥德尔证明了著名的不完备性定理，即并非所有的数学命题都能证明是真或是假，所以有些数学问题是无法得到答案的。计算数学与计算机科学密切相关，在哥德尔证明了这个定理六年之后, 四位科学家区分了可计算函数和不可计算函数的定义, 这些研究都源于哥德尔的理论。如果我们阅读这些论文会发现，他们包含三种对可计算函数的不同定义，而可计算函数的这三种定义都给出了可计算函数是完全相同的事实，这就引出了邱奇图灵论题。

论文作者认为它是对的，这就是我们现在称为的“丘奇-图灵论题”。这个图灵机可以执行任何设备上的任何计算，这也是计算机的原始模型，它可以很很轻松的处理数学问题。

那么,任何设备是什么意思呢？图灵和邱奇并没有想到的一点是, 这是一个我们可以在真实世界中建造和运行的机器. 这样它就是一个物理问题，而不是数学问题了。随着实用计算机的发展, 不可计算函数和可计算函数的定义变得越来越不清晰。因为有的函数理论上是可以计算的，但需要非常长的时间来进行计算而且价值也不高，因此一个有效的程序必须要在合理的时间内完成计算。

所以什么是合理的时间呢？您也许会问在一个超级计算机上用一年时间进行计算合理吗？但是从数学的角度来说这是非常糟糕的, 所以一些理论计算机学家认为, 要在理论和实际中进行妥协。他们认为一个有效的算法应该满足以下条件：它的运行时间必须是在多项式时间以内, 比如N,N的平方,N的立方,N的一万次方等等, 而不是2的N次方这种指数级时间。

因此把能在多项式时间内求解的一类问题称为P，一个事实是大多数的函数是属于P类问题，因此大部分算法都是有效的。现在为了使P的定义更加有意义, 它不应该依赖于何种计算机类型。这就使得一些计算机科学家提出了量化丘奇论题, 它也有许多其他叫法。它指的是：图灵机可以有效的执行任何计算任务。它首先是由Alan Cobham在1965年提出的，而因数分解算法对计算机科学家的重要影响在于，它将显示这个“民间论题”(量化丘奇论题)是错误的。

那么，当我发现因数分解算法后记者会问：量子计算机比经典计算机快多少呢？答案就是：无法回答这个问题。船要比火车快多少呢？这不仅仅是取决于船和火车，还取决于目的地在哪里。所以对量子计算机和经典计算机来说，问题在于经过希尔伯特空间的捷径能否有一个从输入到输出。因此要考虑到许多因素, 而事实上这样的误解非常普遍, 这也说明了公众普遍接受了量化邱奇图灵论点, 即认为计算机中最重要的是足够的空间以及计算速度。然而量子计算机中的一步操作要比经典计算机中的一步操作长。但是量子计算机可以通过走希尔伯特空间的捷径来加速计算，而经典计算机无法这样做，这就大大减少了操作数。

去哪里寻找定量丘奇图灵论题的反例呢？可能会在难以模拟的物理系统中。那什么样的物理系统是难以模拟的呢？一个明显的答案就是湍流问题,它跟纳维尔-斯托克斯问题相关，它是七个千禧年难题之一。陶哲轩思考过这个问题, 认为它和一些系统的偏微分方程组很相似。

湍流就是这样一类很难去模拟的物理系统，而量子力学是另外一种很难模拟的系统，这首先是由Poplavskii和费曼提出的。用数字计算机来模拟量子力学是指数级低效的, 费曼曾指出, 量子计算机的态空间大小是指数级增长的。你把量子系统的状态存储到经典计算机中，然后去精确追踪它们，这需要天文级的时间，但是量子计算机也许能解决这个问题。

在量子算法领域的早期, 1985年, David Deutsch提出问题：量子计算机是否可以加速非量子力学问题的计算？并且他提出了一个非常新颖的例子。七年后，它和Jozsa合作提出了另外一个算法，然后有了更多的人找到新的算法。量子计算机可以加速这些计算，当然，这些算法是为一些问题特定构造的，量子计算机确实可以更快的解决这些问题, 然后呢？

量子算法

量子计算机擅长哪些事情呢？第一个擅长的事情是: 量子计算机可以更有效的模拟量子力学系统。这是Feynman和Manin首先提出的想法。也可以用量子计算机来寻找周期性，这就是Simon问题。还有用量子计算机来分解大数和求离散对数，还有Pell方程和一些其他数学问题也是寻找周期性，Grover则提出可以用量子计算机来有效进行更大空间的搜索。现在来看下什么是因数分解。

假设你有一个整数33，你想要找到两个整数相乘等于33，用3乘以11即可，两个数字相乘对经典计算机来说非常简单。但是如果我们有一个非常大的数字，想要找到它是由哪两个质数相乘得到，这就是一个非常困难的问题了。如果我们想要分解一个L位的数字, 最好的经典方法是数域筛法, 它需要指数级的时间, 而量子计算机只需要平方级的时间。

用已知算法来进行大数分解的资源消耗估计，需要的经典指令数目上升的非常快, 而需要的量子门操作数上升的很缓慢, 这是因为要分解更多位的数，需要的经典指令数目会指数倍的增加。这个发现对计算机科学家来说是令人兴奋的，但对密码学家来说，互联网的安全基于公钥加密，比如RSA加密系统是基于以下事实：很容易将两个因数相乘，但很难将一个大数进行因数分解。这意味着我们可以这样使用它：取两个质数并把它们相乘就得到一个密钥, 然后把它们分开，其他人就无法分解这个密钥, 这意味着人们无法破解你的信息。但是如果你有量子计算机的话，就可以破解信息，意味着你可以监听计算机之间的信息交流，比如在互联网上购买东西时的信息交流。这就是为什么这个算法在1994年提出后就像病毒一样迅速传播。

量子计算基本原理

接下来，我会讲一些量子计算机的基本原理, 包括叠加态原理，量子纠缠, 量子态空间的高维性，以及量子干涉。

叠加态原理是说如果一个量子系统可以处在两个可区分状态中的一种，那么它也可以同时处在这两种状态上，即它可以处在叠加态上。如下图所示，其中 和 是复数, 并且它们模的平方和为1，这叫做波恩定则。如果你对这个系统进行测量，看它是处在量子态A还是量子态B，得到状态A的概率是|α|平方，得到状态B的概率是|β|平方。

下面讲一下数学中的叠加态原理，量子态可以用复向量空间中的单位向量来表示，当两个量子态可以用两个正交向量表示，它们就是可区分的。

量子比特就是一个有两个可区分状态的量子系统。

一个常见的例子就是极化光子, 它只有两个可区分的极化方向: 垂直极化和水平极化。一个极化光子，你只能看到垂直极化或水平极化，其他的所有状态都可由这两种状态产生。比如右对角极化是垂直极化加上水平极化，左对角极化是水平极化减去垂直极化，也有右旋圆极化，其中相位滞后90度。

这听起来比较奇怪, 但量子力学就是如此奇怪。如果你有两个量子比特，那么它们就可以处在4种状态的叠加，现在不用水平极化和垂直极化来代表两种可区分状态，而是用0态和1态来表示，比如这种两比特状态, |01>-|10>，其中每个量子比特都没有确定的状态。

当两个量子系统从整体上看处在确定的状态, 但分开看却处在不确定的状态时，它们是纠缠的。这就是令爱因斯坦不安的地方, 他把这个称为“鬼魅般的超距作用”。许多其他著名的科学家也对此感到困惑，纠缠为什么令人不安呢？如果你用概率论来解释，这就导致了所谓的局域实在论，你将不得不接受这个结论：在一个地方进行的测量, 会影响到另外一个地方的测量结果，尽管这两个地点间没有任何联系，你可以认为它们分开的足够远。

如何解决这个问题呢？一种办法就是去接受这种“鬼魅般的超距作用”，另一种方法是承认量子力学中的概率定律与经典情况不同。量子力学可以加速计算的第三个特性是量子系统的高维性，如果你有n个量子比特, 则它们的量子态由一个2的n次方维的向量描述。下面这些就是这个向量空间的基矢。

量子计算机的线路模型

这个空间的高维性也是量子计算拥有强大计算能力的原因之一。接下来介绍量子计算机的线路模型，它是一个简化模型，就像图灵机的简化模型一样。不过一些量子计算机并不是严格的线路模型，它们会有些不同，不过这是一个很好的方式去理解量子计算机。

为了进行计算，我们需要给计算机输入, 需要改变计算机的状态，需要获取计算机的输出，那么如何做到这些呢? 对于输入，我们可以在二进制输入对应的状态下启动计算机, 比如，100101101, 我们把第一个量子比特置为1态，把第二个量子比特置为0态，其它量子比特同理置为某个状态。我们也许需要额外的空间来运行算法，所以我们需要在初始化时添加额外的0，就像这些0一样需要更多的空间。

下面来看看如何输出, 在计算结束时，量子计算机处在某种状态, 比如这种一般的量子态。但我们不能通过测量完全标定出量子态, 因为有海森堡不确定性原理。假设我们在标准基下进行投影测量，将会有||的概率得到结果i，比如你会有||的概率得到|0…001>，所以应该怎么做呢?

当观察量子计算机后却得到一个概率分布, 并且我们无法做得比这更好, 因为量子力学本质上是一种概率论。你肯定会问：那如何确定量子算法解决了问题呢？我们认为：当能够以很大概率得到正确结果时，该量子算法就解决了问题，这跟用经典概率算法解决问题一样。

现在我们需要量子力学的另外一个原理：线性原理，即孤立量子系统的演化是线性的。孤立量子系统中纯态的演化可以用作用在态空间上的密度矩阵来描述，干涉来源于量子态是用复数表示。

如果对0态施加一次H变换, 则各有50%几率得到0态或者1态，但是如果你应用两次变换，在这里就会有一个负号, 这就意味着|0>这一项抵消了, 即施加两次变换后，|0>会变成|1>,|1>会变成-|0>，这就是量子计算运行的一个例子。

下面讲讲计算，对单个或两个量子比特进行变换操作时, 相当于用2*2或4*4矩阵乘它们, 这跟经典计算机进行计算是类似的，即任何经典计算都由基本的与或非门组成。

量子算法背后的理论

现在介绍下快速量子算法背后的理论，我们要做的就是设计算法使得那些产生错误结果的计算路径相消干涉，这将降低得到错误答案的概率。让那些产生正确结果的计算路径相长干涉，这样你就能极大的增大获得正确答案的概率，这就是设计量子算法时需要做的，这也是设计一个量子算法很困难的原因。下面我想介绍一下因数分解算法，我们要做的就是进行模运算。

一个数除以M得到的余数就是模运算的结果, 比如13加9除以17的余数是5，而5乘7除以17的余数是1，我们将在因数分解算法中用到它。现在来讲下所有快速分解算法背后的思路, 比如我前面讲过的数域筛法，它是经典算法。还比如量子分解算法，要分解一个大数N，需要找到两个数a和b, 它们满足a的平方等于b的平方除以N的余数，但是a不等于正负b除以N的余数，然后你可以得到这个方程，a的平方减b的平方等于a+b乘以a减b ，它又等于N的整数倍，因为a的平方减去b的平方除以N的余数为0。

现在我们还剩两项，其中一项给出一个因数，另一项给出另一个因数。现在我们来分解下33，令a等于13，b等于2，而169除以33的余数是4，所以2的平方等于13的平方除以33的余数，然后用13的平方减去2的平方的结果除以33，其余数为0。15除以3的余数是0，所以15就给出因数3, 11给出因数11。所以最终得到33=11×3。这是欧几里得两千年前发明的算法, 我们可以用来计算因数分解问题。

下面用量子分解算法来对大数N进行分解，首先要找到一个序列的周期，一个序列的周期就是经过多久它会重复，即经过多久再次出现。你获得这个数后，你就知道了周期r，而x的r次方除以N的余数就等于1，如果我们幸运的话，r刚好是偶数，然后计算这个公式就能得到因数。

我们现在通过取最大公约数得到两个因子, 最后就可以给出一些不错的结果, 至少对于随机选择的x中的一半是如此。我们再举一个分解33的例子，取x等于5，然后得到序列:1,5, 5的平方25，5的立方为26,5的四次方为31 (结果为除以33的余数)，5的10次方除以33的余数是1，因此5的5次方除以33的余数是23，然后把33分解成（23+1）×（23-1），就等于24×22，最后24就给出一个因数3，22给出一个因数11，这样我们就分解了33，33=3×11。

因此我们需要找到x的次方除以N的余数的周期, 方法就是利用傅里叶变换可以很容易找到周期性。在找x的次方除以N的余数的周期时会遇到问题，问题就是这些序列可能会有指数级长的周期，解决办法就是利用量子计算机的指数级增大的态空间，去指数级加速傅里叶变换。正如你所知道的, 经典算法中用FFT(快速傅里叶变换)来计算傅里叶变换，我们可以改造成量子傅里叶变换。下面总结一下因数分解算法。

首先将第一个量子寄存器置为叠加态, 然后随机选择x, 如果i在第一个寄存器中, 就在第二个寄存器中计算x的i次幂除以N的余数, 这儿还是经典计算机的计算。我们可以使用经典方法来进行计算，然后就对第一个寄存器进行量子傅里叶变换，接着测量第一个寄存器，我们就得到了量子计算机的输出结果。然后在经典计算机上进行数据处理后，就得到因数了。

在分解算法中有一些很重要的地方, 我们在第二步中，用了第二个寄存器进行计算, 但是之后就再也不用它了，为什么不把这一步去掉呢? 这样不行，因为你去掉了这一步，就会去掉算法里面的干涉，最后就不会得到正确的答案了，这是因为量子力学定律。如果一个量子系统作用到另一个量子系统, 那么第二个量子系统也会反作用于第一个系统。

这个算法能成功的原因在于：当你进行完傅里叶变换后, 就在第一个寄存器中获得了干涉，如果第一个寄存器的值跟周期相近，那么所有的系数相加后得到相长干涉，而如果这个值不是周期，那么所有系数相加后就得到相消干涉，因此你最终得到的结果是接近周期的。

关于“墨子沙龙”

墨子沙龙是由中国科学技术大学上海研究院主办、上海市浦东新区科学技术协会及中国科大新创校友基金会协办的公益性大型科普论坛。沙龙的科普对象为对科学有浓厚兴趣、热爱科普的普通民众，力图打造具有中学生学力便可以了解当下全球最尖端科学资讯的科普讲坛。