例如,若有100阶矩阵的积和式,计算复杂度大约10^32,用当今中国最快的超级计算机——太湖之光计算(每秒10^17次)大约需要4000万年。
算法已经没法优化了,我们还有什么办法来计算积和式吗?正如刚才,在高尔顿钉板问题上,我们如果没办法直接计算组合数,为什么不做个物理实验呢?
这种方法最早在伽利略时代就有应用:伽利略在计算摆线下方面积时,用一个圆形铁片在同样厚度的铁板上滚动,画出了一条摆线。用剪刀沿摆线剪下铁片,发现它的质量是圆形铁片的三倍,于是得到了这个面积是3πr^2,后来,人们才用微积分证明了这个结论。
为了计算积和式,我们需要的物理实验就是玻色采样问题。
4 玻色采样问题微观粒子分为玻色子和费米子,它们最大的区别是是否满足泡利不相容原理。光子就是玻色子,它不满足泡利不相容原理,两个光子可以处于完全相同的状态,我们称为全通同粒子。而电子就是费米子,两个电子不能处于全部相同的状态。
印度物理学家玻色
在量子力学中有一个基本问题:求解粒子的波函数φ,它表示不同粒子出现在不同位置的概率。如果有n个粒子,它们就会相互影响,它们的分布概率又怎么描述呢?此时我们就需要整体波函数,它描述了每一种粒子在每一个状态或者位置的概率分布,它等于(简化写法)
它的意思是:将每一个粒子波函数进行排列(P),相乘后再相加。这是因为这些粒子是全同粒子,可以交换位置,把所有可能的情况都考虑到,再把它们相加,就代表了各种情况下粒子分布的概率了,这就是整体波函数。
这种先排列,再相乘,再相加的问题,大家是否感觉似曾相识?这不就是积和式(3)嘛!终于,2010年,麻省理工学院的教授阿伦森和他的博士生阿尔希波夫一起证明了一个结论:玻色采样问题中粒子占据数分布概率正比于积和式的模方。