量子计算如何验证（量子计算机为啥这么快）

量子计算如何验证（量子计算机为啥这么快）高尔顿这个装置最早是由19世纪的英国学者高尔顿发明的，所以叫做高尔顿钉板。你会计算小球落在不同槽中的概率吗？为了讨论量子计算机九章的原理，我们首先从以前讨论过的一个话题：高尔顿钉板说起。在街头，你是否见过这样的抽奖游戏：把一个小球扔到一个布满钉子的盒子里，小球经过许多次与钉子的碰撞，最后掉到某个槽里，根据小球掉的位置，会给你相应的奖品。钉板游戏

最近有一个新闻：中国科学技术大学潘建伟团队与中科院上海微系统所、国家并行计算机工程技术研究中心合作，成功构建76个光子的量子计算原型机——九章，求解高斯玻色取样只需200秒，而这个结果用当今的超级计算机——太湖之光计算，却需要20多亿年。

九章

有小朋友问：九章计算机真的这么快吗？玻色采样问题是什么？九章这么厉害，能不能破解我们的银行密码呢？今天我们就来讨论一下九章的话题。

要理解九章原理，我们必须理解许多数学概念。本文绝大多数内容都在讨论数学概念，中间过程对大多数读者并不友好，可能会感觉到晦涩难懂，直到最后才会有画龙点睛的一笔。本文针对新生事物进行解说和揣测，有不同意见可以留言，谢绝杠精。

1 高尔顿钉板

为了讨论量子计算机九章的原理，我们首先从以前讨论过的一个话题：高尔顿钉板说起。

在街头，你是否见过这样的抽奖游戏：把一个小球扔到一个布满钉子的盒子里，小球经过许多次与钉子的碰撞，最后掉到某个槽里，根据小球掉的位置，会给你相应的奖品。

钉板游戏

这个装置最早是由19世纪的英国学者高尔顿发明的，所以叫做高尔顿钉板。你会计算小球落在不同槽中的概率吗？

高尔顿

我们以4行钉板为例：如果小球要掉入最左侧或者最右侧的槽中，它必须一路顺着左边或者一路顺着右边运动，小球落入最左侧或者最右侧槽的方法数都只有1种。

但是，如果小球要运动到A的位置，就有两种方式了：要么从A的左上方向右到达A处，要么从A的右上方向左到达A处。所以，到达A处的路径数等于A左上和右上两个位置的路径数之和。A=1 1=2。

按照这个规律我们就能写出小球到达任意一个位置的方法数：等于它左上和右上两个肩膀上的数字之和。

大家看：小球到达各个位置的方法数，构成了一个杨辉三角（正如我们之前讨论过的）。而且，每次撞击钉板之后，小球向左和向右运动的概率都是1/2，因此所有的路径都是等可能的。到达某个槽的方法数越多，概率就越大。

在4行钉板时，落入槽中的方法总数有1 4 6 4 1=16种。其中落入中央槽的方法数有6种，概率就是6/16=37.5%；落入第2、4两个槽的概率是4/16=25%，而落到第1、5两个槽的概率就是1/16=6.25%。

不过，如果槽的数量增加，我们还能计算出这个概率吗？

我们来考虑一个问题：假如一共有n排钉子，对应了n 1个槽，落入第k个槽的概率有多大？根据数学计算，这个概率的表达式如下：

（1）

我们可以简单解释一下这个公式，不过如果数学不太好，也可跳过这一段，这并不影响理解本文。

因为有n排钉子，小球每次撞击钉子有2种选择，所以最终小球的路径方法数有2^n种。如果想要落入第k个槽，那么在n次与钉子的撞击中，需要有k-1次落到钉子右侧，n-k 1次落到钉子左侧。因此我们从n次碰撞中选择出k-1次向右运动，方法就是组合数C(n k-1)种。用落入该槽的方法数，除以一共的方法数，就得到了概率。

仔细观察这个表达式，我们会发现：假如要计算n=100时落入各个槽的概率，就需要计算到100的阶乘，即

这么大的数字，计算起来特别复杂。有没有什么更好的计算方法呢？

有，这就是采样法！我们可以实际做一个实验，让小球一次又一次落下，这就叫做采样。然后，观察每个球落入哪个槽中，并进行统计，最后根据各个槽中小球的频率分布，直接得到小球落入各个槽的概率。只要我们采样的次数足够多，根据大数定律，我们就能以足够高的精度获得这个概率。

不仅如此，如果我们已经通过实验得到了小球落入各个槽的概率，再利用公式（1），就能反向计算出不好算的那个组合数了！计算需要很久的时间，我们通过采样实验很快就完成了。

总结来讲：我们做了一个物理实验，通过实验得到概率，再反过来计算出了一个复杂的数学问题。这种方法在历史上经常会被用到。比如著名的蒲丰投针实验（我们以前也介绍过），就是通过反复扔一根针，得到了圆周率的结果。

其实，量子原型机“九章“的玻色采样过程与此类似。通过一套量子装置，得到了一个概率结果，这个概率结果如果用经典计算机计算非常复杂，但是用量子装置却可以立刻得到结果。

2 行列式

九章到底计算了一个什么问题呢？我们要从大学一年级时，我们学习过的线性代数上的一个概念——行列式说起。

把一些数字排列成一个mxn的矩形，我们称之为一个矩阵。对于一个2x2的矩阵，我们可以求出它的行列式：

我们可以用这样的方法记忆：右下的红线连接的两个数字相乘，减去左下的蓝线连接的两个数字相乘。

其实，行列式的计算在数学和物理上还是挺有用的。例如：两个平面向量X=(a c)和Y=(b d)，以它们为临边构成了一个平行四边形，它的面积S=ad-bc，实际上就是一个矩阵的行列式。

三阶行列式的算法与之类似，只是项数更多：

同样，我们可以用图表示出来：红色线连接的数字相乘再相加，蓝色线链接的数字相乘再相减。

三阶行列式可以用来计算一个平行六面体的体积——只需要把每个向量的三维坐标组成一个3x3的矩阵，计算它的行列式就可以了。

在物理上，计算安培力和动生电动势时，可以使用行列式的算法。

四阶以上的行列式又该如何计算呢？我们有一个普遍表达式：

(2)

Det(A)表示矩阵A的行列式，П表示连乘，sgn表示符号，在某些情况下是正的，另外一些情况下是负的。Sn表示n个元素的置换群，也就是将1、2、3…n这些元素进行全排列。公式大体意思是:将一些元素ai，σ(i)连乘，更换顺序后再连乘...然后再把它们做加法或者减法，就可以得到行列式。

行列式有很大的用处，而且，行列式有很多很好的性质，使得它可以找到更好的算法，降低计算复杂度。根据数学家们的计算，n阶行列式计算复杂度为O((log2)^n)级别，也就是：

计算1万亿阶的矩阵的行列式，计算复杂度也在100多步骤。行列式真是个物美价廉的好东西。

3 积和式

不过，行列式的亲兄弟——积和式就不这么友善了。它和行列式长得很像，只是行列式有加也有减，积和式全都是加。

例如：二阶积和式

N阶积和式

(3)

对比行列式的表达式（2），我们会发现它们都是对角标轮换后相乘再相加。只不过行列式有一个符号函数，有时取正有时取负，而积和式把所有的负号都去掉，变成了完全相加。

尽管只有这么一点点差别，但是积和式却没有行列式那么好的性质，计算复杂度非常高。按照目前最优的算法，n阶积和式的计算复杂度是O(nx2n) 随着n的增大，复杂度指数级上升。

例如，若有100阶矩阵的积和式，计算复杂度大约10^32，用当今中国最快的超级计算机——太湖之光计算（每秒10^17次）大约需要4000万年。

算法已经没法优化了，我们还有什么办法来计算积和式吗？正如刚才，在高尔顿钉板问题上，我们如果没办法直接计算组合数，为什么不做个物理实验呢？

这种方法最早在伽利略时代就有应用：伽利略在计算摆线下方面积时，用一个圆形铁片在同样厚度的铁板上滚动，画出了一条摆线。用剪刀沿摆线剪下铁片，发现它的质量是圆形铁片的三倍，于是得到了这个面积是3πr^2 后来，人们才用微积分证明了这个结论。

为了计算积和式，我们需要的物理实验就是玻色采样问题。

4 玻色采样问题

微观粒子分为玻色子和费米子，它们最大的区别是是否满足泡利不相容原理。光子就是玻色子，它不满足泡利不相容原理，两个光子可以处于完全相同的状态，我们称为全通同粒子。而电子就是费米子，两个电子不能处于全部相同的状态。

印度物理学家玻色

在量子力学中有一个基本问题：求解粒子的波函数φ，它表示不同粒子出现在不同位置的概率。如果有n个粒子，它们就会相互影响，它们的分布概率又怎么描述呢？此时我们就需要整体波函数，它描述了每一种粒子在每一个状态或者位置的概率分布，它等于（简化写法）

它的意思是：将每一个粒子波函数进行排列（P），相乘后再相加。这是因为这些粒子是全同粒子，可以交换位置，把所有可能的情况都考虑到，再把它们相加，就代表了各种情况下粒子分布的概率了，这就是整体波函数。

这种先排列，再相乘，再相加的问题，大家是否感觉似曾相识？这不就是积和式（3）嘛！终于，2010年，麻省理工学院的教授阿伦森和他的博士生阿尔希波夫一起证明了一个结论：玻色采样问题中粒子占据数分布概率正比于积和式的模方。

阿伦森

这句话很难理解，我们再打个比方。玻色采样问题的实验装置就好像有一个光子的高尔顿钉板，它的钉子是分束器，它的小球是光子。

光子进入这个装之后，会形成整体波函数，最终光子从哪个出口出来并不一定，但是却有一定的概率分布。现在给定光子从输入端中的某些位置如进入，求从某些口输出的概率大小。阿伦森就是证明了，这个概率情况与一个矩阵的和积式的模方有关。

具体来讲，这个概率是

其中S表示一种输出情况，P(S)就是这种情况的概率，s1s2…表示此时各个能级的量子数，A就是与这套干涉装置对应的矩阵。

如果我们能够通过采样，计算出这个概率P，就能通过这个公式反推出积和式Perm(A)。我们知道，如果用经典计算机，计算积和式是非常困难的。潘建伟团队的“九章“正是这样一套实验装置。

潘建伟团队利用更好的光源、干涉装置和光子探测器，获得了76个光子的输出结果。在200秒内采样了数千次，完成了玻色采样过程，得到了各种情况下的概率。这个概率如果使用经典计算机太湖之光计算，大约需要20多亿年，主要问题是因为积和式的计算过于复杂。

不过，九章只能算是一个原型机，而不是计算机。因为它使用量子的方法去模拟量子过程，速度当然会超过经典计算机。这就好像点燃一个爆竹问碎片怎么飞，物理方法1秒就知道了，可是用计算机去计算可能要知道爆竹的结构、火药的种类，甚至要知道每一个分子和原子的位置，要获得足够的精度，计算量非常大。这并不是因为经典计算机不行，而是因为世界太复杂。

不过，经典计算机的优势在于通用性，既可以算爆竹爆炸，也能算炮弹的轨迹。可是九章目前只能处理玻色采样问题，或者可以计算和积式。而且，任意给一个和积式，能否转化成相应的光路也未可知。对于更多其他的问题，例如证明量子计算机优越性的大数的质因数分解问题，九章更是无能为力。

所以，至少到目前为止，我们的银行密码还是安全的。即便有一天，人们真正造出了通用量子计算机，它也只能在某些方面优于传统计算机，许多的生活场景例如打电话、玩游戏，可能还是经典计算机更有优势。量子霸权时代，还远远没有到来。