编辑推荐：
计算图的完美匹配数是著名的 #P - 完全问题。国防科技大学研究人员提出并实现了光子完美匹配求解器，实验保真度超 90%，还能增强经典随机算法解决 NP 问题，为解决完美匹配问题提供了新方法。
在科学的奇妙世界里，计算领域存在着诸多复杂的难题，其中计算图的完美匹配数便是一个著名的 “硬骨头”，它属于 #P - 完全问题。这一问题可不像表面看起来那么简单，它在众多领域都有着广泛应用，比如稳定婚姻问题、富勒烯的 Fries 数计算、二聚体问题以及 Hosoya 指数计算等。然而，目前并没有多项式精确算法或完全多项式近似算法能高效解决一般图的完美匹配数计算。
传统的基于经典光场的光学方法在解决 NP 问题时，面对困难的计数任务显得效率低下。而利用量子多光子源的方法虽然有潜力，但由于对相干性要求极高，像光子源的高纯度、相对相位的稳定，以及路径和到达时间的一致性等条件很难满足，实现大规模光子硬件面临重重挑战。即便有一些改进方案，也会因为各种因素引入额外的指数衰减等问题。
在这样的背景下，国防科技大学的研究人员挺身而出，勇敢地向这个难题发起挑战。他们开展了一项极具创新性的研究，提出并实现了一种基于频率分组和多光子计数的光子完美匹配求解器。该研究成果发表在《Nature Communications》上，引起了广泛关注。
研究人员为实现这一目标，运用了几个关键技术方法。首先，利用硅波导产生宽带光子对，这是整个研究的 “基石”。其次，借助波长选择开关（WSS）对光子进行频率分组，WSS 在其中起到了关键的调控作用，它能够根据给定的图将不同频率的光子对分配到特定的输出端。
下面来看看具体的研究结果：
- 原理验证与实验设置：研究人员基于 Krenn 等人的理论，将完美匹配与量子实验联系起来。通过非线性晶体产生的光子对对应图的边，输出路径视为图的顶点。利用频率分组和多光子符合测量，自然地保留并计数完美匹配。实验装置主要包括产生宽带光子对的硅波导、用于频率分组的 WSS 以及超导纳米线单光子探测器（SNSPDs）等12。
- 计算完美匹配数的实验结果：固定泵浦平均功率为 200 μW，研究人员配置了不同顶点数的图进行实验。对于 2 - 顶点图和 4 - 顶点图，通过测量双光子和四光子符合事件，发现估计值基本能对应图的完美匹配数。对于 6 - 顶点图、8 - 顶点图和 10 - 顶点图，记录四光子事件 1 小时，得到的分布保真度均超过 90%。此外，还配置了一个 8 - 顶点图记录六光子事件，保真度达到 94.54%34。
- 增强图相关搜索问题的求解算法：多光子处理器可增强经典随机算法解决 NP 问题，如布尔可满足性（SAT）问题和密集子图问题。对于 SAT 问题，将一个四条款的布尔公式转化为 8 - 顶点图的 4 - 团问题，实验得到的四光子分布保真度为 98.25%，找到了满足公式的赋值。对于密集子图问题，在寻找 16 - 顶点加权图的最密集子图时，实验得到的四光子分布保真度为 92.49%，利用完美匹配采样的样本进行随机搜索，比均匀采样表现更好56。
研究结论和讨论部分意义重大。该研究提出的完美匹配求解器的求解过程与传统方法截然不同，它能从所有可能状态的叠加中自然地保留和计数完美匹配，这是经典方法无法做到的。而且，与常见的路径编码实验不同，在该研究的光学完美匹配求解器中，光子源固定，非线性过程的光学长度恒定，与问题规模无关，通过 WSS 就能轻松转换图，无需改变光路或晶体。实验中避免了破坏性干涉，对光子的不可区分性要求较低，也无需额外的滤波过程或特殊的光子光谱纯度结构设计。此外，该方法不受光子源纯度的限制，理论上可通过增加泵浦光强度、减小每个通道的带宽来增加可用通道数，从而扩大图的规模。虽然实验存在光子对源亮度与高阶激发强度之间的权衡，但通过优化实验条件，有望检测到数百个光子的事件，在计算上展现出优势。
总的来说，这项研究为解决完美匹配问题提供了一种极具前景的方法，不仅实验设置简单，还能方便地转换或扩展目标图。未来，随着更宽的光子对源和更多输出端口的 WSS 的应用，以及对潜在应用的进一步探索，这一成果有望在更多领域发挥重要作用，为相关计算问题带来全新的解决方案，推动计算领域的发展。
