中科院范桁：从量子计算机分解 21=3×7 说开去

量子计算机可以用来做什么？这或许要从质数分解说起。关于这个问题，中科院物理所的范桁研究员作了一次由浅入深的分享。

以下为精编版：

大家好，非常荣幸来跟大家分享量子计算机分解质数乘法这个问题，今天从量子计算机分解21=3×7说起。我叫范桁，来自中国科学院物理研究所，我所在的实验室是固态量子信息与计算实验室。提纲大致分这么几个方面，第一是引子，从过去的算盘、计算器等等说起；第二个来讲解预备知识，比如欧拉定理等；第三个说一下质数分解、大数分解在公钥密码系统的应用；第四个我来说一下量子计算机怎么来分解大数；最后展望一下量子计算机的未来发展。

国际竞争激烈的量子计算

量子计算机现在是一个非常热的话题，特别是去年谷歌宣称他们达成了所谓的量子霸权。Alphabet和谷歌的CEO 皮柴（Pichai）宣称的量子霸权类似于莱特兄弟的飞机，实际上是一种变革性的技术，也是一个新技术的起点。

Alphabet/google CEO宣布达成量子霸权

除了谷歌之外，世界上很多的大科技公司包括中国的科技公司也都在量子计算方面投入了巨大的人力、财力等资源。加拿大D-Wave公司做出了量子退火机，IBM把超导量子计算机和稀释制冷机做成一个量子计算的一体机，来做商业方面的一些项目，包括微软、英特尔、很多风投公司在这个方面有很大的投入。我们国家也在量子计算方面有很多的进展，我将展示两个我自己参与的工作，第一个是利用12个超导量子比特实现强关联量子行走，第二个是用有20个量子比特的超导量子计算的芯片实现了薛定谔猫态的制备。现在就量子计算怎么来进行大数分解进行讲解。我们可以看到量子计算机它也是一种计算的机器。

加拿大D-Wave公司量子退火机

能做计算的机器已经有非常长的历史了，如图所示是某种进行计算的器械。后来发展中，有比较复杂的计算机器、还有一些占地比较大的计算机器，以及中国设计的计算机器——算盘。不管是过去的算盘、计算器、计算尺到现在的电子计算机，到将来正在发展的量子计算机，所有的计算机器它所运行的规律都不完全一致。比方说算盘，“二一添作五”，“三一三十一”等等这样的口诀，和电子计算机所运行的规律是完全不一样的。但是同时我们应该注意到“二一添作五”，“三一三十一”实际上在数学上都是正确的，就是说计算的机器运用了计算里面的某个规律，然后可以方便地给出计算的答案。这个计算的过程对于计算机来说可能是比较简单的，但是对人类来说也许是比较复杂的。这地方要说明的问题是量子计算机背后的数学也是正确的。今天跟大家来分享一下量子计算机到底怎么来分解两个质数的乘积的。

预备数学知识

首先讲一些预备的知识——模计算。模计算就是自然数1、2、3、5、6、7一直到很大，通过取模把这个数字限定在一定的范围之内。比方说钟表，从1、2、3、4一直到12，然后就回到了1这样的一个循环，那么能不能看到13呢？13取12的模实际上就等于1，14取12的模等于2，15取 12的模等于3等等。需要强调的是，12的倍数、24或者12的模就等于0，为什么要指出这一点呢，实际上这提供了非常大的方便。在计算的时候，0加任何数是不起作用的，1乘任何数不起任何作用，这个在模计算里经常用到。

下面来看一下费马小定理。费马大定理就是xⁿ+yⁿ=zⁿ，在n≥3的时候它没有正整数解。费马小定理说的是另外一回事情，有一个质数p和另外一个整数k，这个整数的p次方，在取p的模的情况下，它还等于k，这是一个非常奇怪、有意思的结果。如果这个k不是很特殊的话，比方说它不是p的倍数或者说是0等等这样的这个情况，有k^p-1=1(取p的模)这样的一个结论。

下面举一个例子，k从1、2、3、4一直取到12，p取质数13，来验证费马小定理的正确性。2¹³次方在取13的模的情况下等于多少？2¹³我们就可以把它写为 2¹³=（2⁴）³×2，2⁴等于16，16是13+3，在碰到13的情况下取13的这个模13=0，那么13=0的情况下21³在取13的模的情况下的就等于2，这是一个非常神奇的费马小定理。那么在用3这个例子来跟大家分享一下3¹³ 的模是多少。3³ =27，27可以写成26+1，26在取13的模的情况下它就等于0，那这样的话3³=1，最后就是根据这样的取模的计算会发现3¹³ =3。那么4就更简单，因为4=2×2，2¹³×2¹³还是2×2那么就等于4，通过简单的运算验证了费马小定理。

现在来讲解一下它具体的内容是什么。我们刚才说了费马小定理是取一个质数的这么一个模，那在计算里边取的这个模如果不是质数会发生什么情况？比方说它是质数的一个幂次或者是两个质数相乘：5×7、3×7、11×13、11×17等等，那这样的话我们取两个质数的乘积的模应该遵循怎样的一个规律呢？费马小定理并没有告诉我们答案，这个答案是欧拉给出的。

欧拉定理是费马小定理的推广，它指出我们在取n的模的情况下，我们需要定义一个函数φ(n) ，确定φ(n)之后我们会发现欧拉定理实际上就是费马小定理的推广。我特别需要指出p如果是一个质数的话那么k^p-1=1，那这地方我们需要的是什么呢？我们需要的是两个质数相乘，φ(p×q)是(p-1)×(q-1)这么一个数字。这些数字什么用处呢？实际上这个定理是有非常广泛的应用，比如现在所广泛使用的RSA密码系统。

举一个例子，这个例子在过去非常著名的，e=9007，这一个是编码的系统，n是一个有129位的数字，看起来这个数字是非常复杂的，不过我们知道这个n是两个质数的乘积，但是我们不知道它是哪两个质数的乘积。所以就是有这么一个n，现在问题是底下这一大串的数字具体的意义是什么？比方说敌人就发送了这么一串数字，那这个数字它的含义是什么呢？这是一个密码系统，加密的步骤是完全知道的。怎么加密呢？我们是有个消息（message），消息（message）就是一串数字，这串数字取e的幂次，然后再求n的模，最后我们就得到了X这串数字。但是我们现在要知道的是X这串数字具体是什么。这个RSA公钥系统怎么来解密呢？它并不是说所有人不能解密，收取这个信息的人当然是可以解密的，他自己有一个私钥，就是所谓的d，他做同样的计算，对X求d的幂次然后再取n的模，最后就把这个数字还原得到的就是消息（message）。

这个地方他用的是什么呢？他用的是前面说的2¹³取13的模，它还原到2；3¹³取13的模，它还原到3。那这个消息（message）是什么呢？这里用到了欧拉小定理，一个消息（message）上面有所谓的幂次，根据欧拉小定理，最后他还原到这个消息（message），这样就把密码破解了，意义就得到了。收取这个信息的人知道私钥d，但是对我们大众来说，我们只知道怎么加密却不知道怎么来解密。简单地说就是加密顺着计算是简单的，但是逆着运算解密是复杂的。RSA密码系统的解密问题提出来之后，很长一段时间都没有解决。这其实是一个悬赏的问题，悬赏100美金，不是100万美金，也是世界上一个著名的难题，后来这个难题解决了，大家把RSA129这个数字的分解出来了，分解的非常好，然后把这个密码也给破解了。最终的它的信息是什么呢？信息是the magic words are squeamish ossifrage，意思类似于挑食的秃鹰。RSA密钥系统是广泛应用的，它难在即使知道两个质数的乘积，也不知道这两个质数具体是什么。

RSA密码系统在现在的银行系统和互联网系统都是广泛应用的，不过银行有各种各样的加密系统，最终都着落在1024bit的RSA密码系统里，因此大家的资金都是安全的。密码系统很难破解的，或者说是不可破解的。这个公钥密码系统和我们历史上古典的加密系统是不完全一样的。小说狄公案里有这么一个故事，有一个围棋的棋盘，另外一面墙上还有一个佛经，佛经里藏有秘密，但是这个秘密始终没办法破解，最终狄公发现如果把一个正在下的围棋棋盘往这个佛经上一重叠，那黑子所对应的这个文字实际上就是秘密。这意思是棋盘实际上是相当于密码，佛经相当于是明文，最终这个密码和明文一结合就把秘密破解了。我们发现如果知道怎么加密那就知道怎么解密，这个和公钥系统是不完全一样的，因为所有人都可以加密，但是只有拿到秘钥的人才能解密。

取自小说《狄公案》之“湖滨案” ，作者高罗佩

量子计算分解大数算法

回过来我们再讲解这个问题，两个质数的乘积是个非常大的数字，要把数字分解出来就关系到银行系统的秘密是不是保密等等，这些应用还是非常广泛的。那么怎么能分解质数呢？是不是有一个非常好的算法或者量子计算机就能把它算的比较好。量子计算机也许能算得好，但是它背后的数学必须是正确的。那这个数学怎么来计算这个问题呢？有个叫张益唐的数学家把孪生子质数问题推进了一大步，他证明一对质数的距离小于7000万时，这样的一对质数是无穷多的。

张益唐

很快大家把这个质数的这个距离缩小了很多，比方说200、300左右，然后说这样的质数是无穷多的。那原始上是说什么呢？原始上是说孪生子质数是无穷多的。孪生子质数是什么呢？比方说3和5，3和5中间只差一个偶数2，这是一对质数；11和13 是一对质数，它们中间差一个2，把这样的一对质数叫孪生子质数。刚才说到密码系统是两个质数乘积，那么我们现在如果这两个质数就是孪生子质数，会得到一个结论：孪生子质数一个是x-1，一个是x+1它乘起来，如果取p和q，乘起来的质数取模的话，它就等于0了。简单地说就是如果能解 x²=1（取n的模），n是两个质数 p、q的乘积，那么质数的这个乘积就可以大概分解了。举个例子，知道3×5=15，那么用这样的办法来分解的话，4的平方取15的模就等于1，x²=1。简单地说4×4=16，16取15的模等于1，那我们就会发现x就等于4，x²=1，x=4这一个它就是一个解。我们把x得到了，那得到两个质数就是x-1=3，x+1=5，所以我们知道15等于3×5。Peter Shor根据这个规律，可以把任意两个质数的这个乘积分解。

那我们下面具体来看一下结论x²=1，我们会发现它有个解，这个解还有一个要求是它不要太平庸。因为x²=1，x=1可以就是解，但是这个解不管用，是一个平庸解。15=3×5，4²=1 这个4不是1，我们需要这种非平庸解。那我们举个例子，就是三七二十一。我们知道21是两个质数的乘积，那x²=1取21的模怎么来计算？我们发现假装能知道，试一下总是还可以试出来的。8²=64，64=63+1，63它是21的倍数，所以63在这里我就把它当成0了，那最后 8²=1。8²=1是x²=1取21的模的一个解，8+1=9，8-1=7，刚才说过要求7和9与21的最大公约数，我们就把这个数字就求出了，21和7的最大公约数是7，9和21的最大公约数是3，所以最终按照这个算法发现21=3×7。

量子计算机就是通过x²=1取n的模分解质因数的。求解到了x之后，取x+1、x-1与n的最大公约数，我们就把这个问题解决了。（x-1）×（x+1）=p×q ，为什么是p、q？因为我们取p、q的模实际上就是等于0，（x+1）×（x−1）是x² -1=0，所以是x²=1。右边是两个质数乘积p×q，左边反正是两个数字相乘，那我们就知道这两个数字实际上就是p、q的倍数，那我们就是来取它的最大公约数，就能得到p和q。大家可能会提出一个问题，你是用的一个孪生子的质数举了一个例子，然后就举了几个例子就说这个问题就可以解决，是不是所有这样的问题都可以解决呢？这个规律依赖于欧几里得定理，欧几里得定理指的是两个数字p和q，然后如果我们用另外两个整数比方说k和l来计算一下，一个是k×p ，一个是l×q，加起来这个最小的正数就是p、q的最大公约数，欧几里得定理实际上是辗转相除。这个地方简单地进行一个计算，因为p和q是互质的两个质数 ，所以它的最大的公约数就是1，根据欧几里得定理，它应该有kp-lq=1成立，就是这个结果肯定是正确的。然后我们把两边同乘以2，再进行简单的计算，最后发现（x+1）×（x-1）是p、q的倍数。简单地说就是所有的两个质数p、q乘积等于n，我都可以用 x²=1模掉n这样的一个方程给它求解，这就是量子计算机背后的原理。

量子计算中算法的实现

那量子计算机具体是怎么做的呢？用的是Shor算法，随便找一个正整数y，求它的幂次y、y²，y³，一直到会发现可能有y^r，所有求解一直都是要取n（p×q）的这个模，然后我们会发现 y^r=1，就有可能会找到这样的公式。如果r碰巧是个偶数，那就简单了 ，比方说r=2m ，我们就知道（y^m）²=1，这个意思是什么呢？如果r是偶数的话，x² =1这个解我已经找到了。问题是随便找了一个y 然后给它幂次，你真的是能把这个解找到么？Peter Shor算法里面已经说明，随便找一个y，然后求r的幂次，最终发现满足y^r=1，r是偶数的概率要超过50%。意思是我随便找一个y，然后我就这么计算，最后发现确实就把解给找到了，并且以50%的几率就找到了，那一次做不好的话，两次三次基本上就没什么问题。

Peter Shor

量子计算机怎么做呢？它的原理基本上就是随便找个y，找幂次，最终把这个问题就解决了。大家可能就会有问题，n=p×q这个问题很难，经典计算机很难去解决，但是好像我们按照刚才讲的这个道理，它就很容易被解决。经典计算就按照这样的计算法则去做为什么不可以呢？因为随便找个y然后求它的幂次，最终发现y^r=1 这个计算本身是困难而复杂的，计算量很大，所以这个问题要这样解和直接去分解n=p×q的难度是一样的。因此公钥密码系统按照求幂次分解质因数这个计算并不会简化计算，只不过我们发现一个神奇的规律，这个规律导致计算可以用这种办法来做。

量子计算机可以执行某种计算，这个计算可以把y^j一次全部做到从1一直到N，那如果N足够大，就会发现 y⁰=1，y¹=y，y²=y²然后y¹ 、y² 一直到y^r，y^r=1，所以它最终会变成一个循环，y¹一直到y^r-1 它是一个循环。最终我们就是会找到这么一个循环，这个循环我只要知道r，y是随便找的，取3、5、7、10都可以，那我们会发现最终是找到r，r是以50%的几率为偶数，那么√(y^r)=y^m 就是我们的解。量子计算机一步就可以把它的循环给展示出来，然后它只需要把这个循环的r给找到就行了，用量子的操作比较容易把它找到，因此量子计算机通过找y^r=1的方法来分解质因数是比较简单的。

今天主要讲了两个质数怎么相乘，两个质数怎么分解，乘起来怎么分解。最后给了一个比较有意思的算法，实际上就是来求解x²=1这个方程，并指出这个方程的求解就是去求y^r =1，在量子计算机里是比较容易去解决的。问题在于我们还没有量子计算机。如果有量子计算机来分解这个问题，也会遇到很多困难。第一，量子计算机需要非常精确，很遗憾的是现在的量子计算机很不精确。第二，量子计算机把RSA129这么大的这个数字编入到量子比特里需要很多的量子比特，遗憾的是现在我们量子比特不太多，谷歌有53个，我们自己的工作一个是12个、一个是20个，所以距离这个还有比较远的路。预测真的使用量子计算机来分解数字的话可能需要建造非常好量子计算机，个人估计大概要超过5年的时间。

量子计算展望

简单总结一下，今后我们量子计算机怎么做呢？实际上就是大规模的计算需要努力的方向，第一是操纵要精确，第二是比特数要比较多，第三就是运行时间要比较长，实际上就是朝着实用化的方向发展。最后用杨振宁先生的例子来说一下量子计算机的运行模式是非常特殊的，我们要让量子计算机去解决很多的问题需要给量子计算机恰当的算法才行。Peter Shor他就是把欧几里得定理、欧拉定理、费马小定理等结合起来，他最后发现“三七二十一”这个东西实际上可以用另外的易于被量子计算机所能执行的算法做出来。杨振宁先生是数学物理的大家，数学和物理结合才能给出很多的东西，他针对RSA密码系统也给我们写过信，讨论这个问题。

最后以杨振宁先生作为一个总结，有记者说杨振宁先生有一篇文章是把这个数学和物理结合起来，我理解的主要意思就是这个文章就是物理和数学的结合，比方说量子计算机就是量子和数学的结合、量子和计算机的结合、量子和信息科学的结合，它不是简单的借用，不是简单地说把计算机学好就可以做好量子计算机，它必须在数学和物理方面都有突破才行。所以杨先生说了不要太形式化，在数学上没有突破，然后说能解决物理问题应该是很困难的。另外一个就是数学家可能觉得在物理上没有突破，那这个问题就很难解决。所以我们量子计算机需要数学和物理等等的结合，才能取得更大的突破。今天的报告就到这里，谢谢大家！

-End-

1930年秋，第六届索尔维会议在布鲁塞尔召开。早有准备的爱因斯坦在会上向玻尔提出了他的著名的思想实验——“光子盒”，公众号名称正源于此。