玻色取样:通往量子霸权的光学之路(它2个文献都是我们海南琼大的导师钟是第一人的积和式的，如此我已读母校校长的量子电子学和组合数学专家的量子计算，也见潘建伟完成50光子玻色取样,比谷歌快百万倍;任正非凑热视频;也如“世界七大难题”的数学…
上面论文作者是：林梅(中国科学技术大学潘建伟团队), 汪喜林(南京大学)（也可参考量子理论博士J.
K. Percus独撰的《组合数学的方法》或海南琼大导师的《组合数学》。第一届墨子量子奖就授于1994年已对量子计算机做出先驱贡献的组合数学博士Peter
Shor )
缘于量子的叠加性质，相对于经典计算，量子计算一直被认为具有指数级的加速性。在量子计算里，每个比特不仅可以表示0或1，还可以表示成0和1分别乘以一个系数再叠加（注：是非完全指这里倒数第2段我导师的中国第一篇开创性的“积和式的(0,1)”），随着比特数增加，信息的存储量和运行速度会呈指数增长，经典计算机将望尘莫及。
量子霸权（quantum supremacy）一词是美国加州理工学院物理学家约翰·普瑞斯基尔(参见John Preskill的系列演讲)提出的，它代表了大多数量子学家们的看法：当可以精确操纵的量子比特超过一定数目时，量子计算机在特定任务上的计算能力就能远超经典计算机(注：“量子霸权出现,人类文明进入新纪元”由世界第一的谷歌CEO/世界第一的IBM主席/Gartner副主席和下面Aaronson评述讲解)。
在量子计算的版图上，光子、电子、离子等微观粒子都被科学家用来尝试实现可能的计算方案。其中，线性光学量子计算是量子计算的方案之一。所谓线性光学量子计算，就是以光子作为载体，经过一个线性系统完成操作，输出计算结果。实现大规模比特的通用量子计算机目前看来还具有很苛刻的门槛，于是，科学家希望能够首先让量子计算在特定任务上表现出比经典计算机更卓越的能力。其中，一个叫做“玻色取样(boson sampling)”的问题吸引了科学家的关注。
鉴于玻色取样量子模拟的重要意义和应用前景，光子学领域重要期刊发表了由来自巴西和意大利的多名量子光学专家联合撰写的光子体系玻色取样综述论文(注:这几个巴西和意大利刚毕业不久的年轻学者合写的这综述论文第一篇参考文献是上面图论博士Peter
Shor的/而最后篇是图论同构和高斯玻色取样的)，系统地展示了玻色取样的研究成果。该论文从理论出发，结合目前玻色取样实验的技术方案和研究现状，深入浅出地分析了玻色取样对于量子霸权的意义。
波色取样问题概述（注:本文最后2011年的参考文献[其实2010年已投去arxiv.org]的作者Aaronson和Arkhipov的其后这篇2013年的文章说“玻色取样”是他俩3年前的论文[正是这2010年的]提出的,命此名应是为纪念玻色，再其后世界著名教授Dowling等美国和澳大利亚合撰的2014年的这篇玻色取样综述就已有很多论文和3本书是Ryser的《组合数学》和现代计算史及量子计算与信息。如量子网络图论最近之论文Characterization
of quantum circulant networks having perfect state transfer对循环图论用于具有n个相互作用的量子比特的安排问题取得突破等，可参考这里最后的诺贝尔奖得主高徒的《量子图论导论》名著…):
所谓“玻色取样”问题，我们可以理解成一个量子世界的高尔顿板。高尔顿板问题是由(Karl Pearson的导师)高尔顿Francis Galton提出来的，这个问题的模型如图1所示，小球从最上方被扔下，每经过一个钉板，都有一半的可能从左边走，一半的可能从右边走，当有很多个小球从上往下随机掉落时，落在下面的格子里的小球数量分布上会呈现一定的统计规律，这个模型可以用来直观地认识中心极限定理。
图1 高尔顿钉板（图片来自淘宝搜索“道尔顿板”）
如果将“高尔顿钉板”发展出一个量子版本，即，由全同光子来代替小球，用分束器（当一束光通过分束器时会被分成两束强度较低的光，一束透射，另一束反射）来代替钉子，则这个游戏就变成“玻色取样”的量子模拟，如图2所示。更一般来讲，“玻色取样”是指，在n个全同玻色子经过一个干涉仪后，对n个玻色子的整个输出态空间进行采样的问题。采样过程和分布概率息息相关。例如，在图3中，3个全同光子输入一个7进7出的干涉仪，如果要对1、2、3，或者2、3、5输出口进行采样，目前理论认为至少需要计算一次对应口的分布概率。
Aaronson 和Arkhipov研究发现[1]，n光子“玻色取样”的分布概率正比于n维矩阵积和式（Permanent）的模方，从计算复杂度的角度来看，积和式的求解难度是“#P-hard”[2]，当前经典最优算法需要O(n2n)步，随着光子数的增加求解步数呈指数上涨。对于这样一个经典计算#P-complete困难的问题，在中小规模下就可以打败超级计算机。因此，“玻色取样”这个问题被量子计算领域的科学家盯上了，准备拿它小试牛刀，挑战经典计算机。
图2 “玻色取样”问题
图3 “玻色取样”基本概念：当n个全同玻色子经过一个干涉仪（线性变换器）之后，求特定分布的输出概率。例如，在一个7进7出干涉仪的1、2、3口同时输出3个全同玻色子，求3个光子在2、3、5口各输出一个光子的分布概率。[图片来源: Advanced Photonics 1, 034001 (2019)]
波色取样实验的各种变体
世界上有很多个课题组从实验上挑战玻色取样任务，根据实际需要，衍生出了各种玻色取样变体。Advanced Photonics 发表的综述论文着重介绍了散粒玻色取样和高斯玻色取样。
散粒玻色取样针对自发参量下转换（SPDC）光源概率性和低抽运强度的缺点，将k (k > n)个单光子SPDC源连接到线性干涉仪的不同输入端口，SPDC产生的一对光子分别用于预报和探测。当k远大于n时，相对于固定版本的玻色取样会产生指数级别的加速；而高斯玻色取样由Hamilton等人提出，它使用所有处于压缩态的光子，且允许使用更高的抽运功率，使得其同样在事件发生率上具有指数优势。
玻色取样实验进展
玻色取样实验的完成，有赖于三个基本模块：单光子源、线性干涉仪和单光子探测器。该综述列举了迄今为止主要的玻色取样实验所采取的技术方案，总结了各个实验小组在三大模块上的主要特点。
在光源方面，主要的方案有：基于单个非线性晶体（NLC）的单光子源、集成片上源、半导体量子点。
在干涉仪方面，主要的方案有：由定向耦合器网络组成的多端口波导电路、微光学干涉仪、若干波导或光纤芯连续耦合设备、利用光纤回路的时间编码线路。
在单光子探测方面，主要的方案有：雪崩光电二极管、超导纳米线探测器。
但是，受限于单光子源的品质和干涉网络的性能，玻色取样的高效率大规模实现一直是个难题，世界上多个课题组在改善光源的品质上做了大量的尝试。
作者指出，高质量的光子源是实现可扩展玻色取样的关键，而目前使用的参数下转换、自发四波混频和固态量子点源等方案都有各自的优势和亟需解决的技术难题。
玻色取样的验证
对于玻色取样任务来说，验证其是否从正确的分布中采样是至关重要的。目前而言，完全验证还难以做到，因为对于具有量子优势的实验来说，经典模拟的计算量将是指数级增长的，无法对大规模的实验进行验证。但是已有一些初步验证的方法被提出，来排除实验中可能出现的“错误”分布，如均匀分布，可分辨粒子的分布，平均场分布等，给玻色取样实验提供直接证据，说明实验的正确性。目前主要的方法有Baysian method, likelihood
ratio test, statistical benchmark, pattern recognition等。
总之，从原始理论的提出，玻色取样的理论和实验都取得了可喜的进展。技术的进步，诸如高品质的量子点光源和单光子探测器等，都为进一步的探索开辟了道路。
参考文献：
[1] S. Aaronson and A. Arkhipov, “The computational
complexity of linear optics,” in Proc. 43rd Annu. ACM Symp. Theory of Comput.,
A. Press, Ed., pp. 333–342 (2011).
[2] L. Valiant, “The complexity of computing the
permanent,” Theor. Comput. Sci. 8(2), 189–201 (1979).
注:这篇文章出处的链接是www.sohu.com/a/333494342_739961，并它的2篇参考文献中的哈佛大学的图灵奖得主Leslie Valiant的论文标题见是“积和式(Permanent)”的，而另一篇在上面第6段见Aaronson等发现n光子玻色取样的分布概率正比于n维矩阵积和式(Permanent)的模方…相关的主要开创者Cauchy以及Binet…