近日，国防科技大学计算机学院徐平研究员团队在量子计算领域取得重要突破。提出一种多光子频率维度量子模拟理论并实际求解了图论完美匹配计数、布尔可满足性、稠密子图等经典难题。相关成果以“Solving perfect matchings by frequency-grouped multi-photon events using a silicon chip”为题，发表在Nature Communications上。国防科技大学计算机学院的博士生朱枰谕为第一作者，徐平研究员为通讯作者。
无向图的完美匹配计数问题是著名的困难问题，属于#P完全复杂度类，经典方法无法有效求解。近期，一些基于多光子事件的实验方案为高效求解完美匹配计数带来了新的可能性，比如基于高斯玻色采样的方法以及基于路径重叠采样的方法。但是这些方法由于存在对系统相干性和光子不可区分性的严格要求，包括光子源的高纯度、相位的稳定性、路径和到达时间的一致性等，普遍存在较高的实验难度和较低的可扩展性。
光子的频率自由度具有高维扩展性，并且不同频率的光子能够在同一个波导中传输，大大降低空间资源消耗，在量子信息处理任务上有巨大的开发潜力。该研究工作针对求解完美匹配计数这一类问题的实际需求，采用光子的频率自由度，结合频率分组以及多光子事件的叠加特性，构建完美匹配类问题的哈密顿量，实现对该类问题的模拟计算，开发出高效求解完美匹配的模拟计算系统。该系统主要由三个步骤组成：
产生宽带的频率关联光子对；
根据给定的图，按照频率通道对光子对进行分组。在分组时，每个与频率相关的光子对构建一条边，并且这两个光子分别分布到两个输出端，这两个输出端被视为由这条边连接的两个顶点；
测量时保留每个输出端有且仅有一个光子的多光子符合事件并进行计数。
图1基于频率分组的多光子完美匹配求解系统的原理及实验设置。
在演示实验中，宽带光子对由硅波导中的自发四波混频过程产生。产生的光子对进入波形整形器进行频率分组，然后每一路输出接一个单光子探测器进行探测。该系统仅用固定的光源结构，通过配置波形整形器即可对图进行改变或扩展，并保持基本光路长度不变。在实验中构造了6顶点、8顶点和10顶点的图，并对1小时内四光子符合计数的分布进行记录。此外，还配置了一个8顶点图并进行了六光子符合计数采样。
图2 实验中的图配置及符合计数结果。实验配置的6顶点稀疏图(a)、6顶点稠密图(d)、8顶点图(e)、10顶点图(f)，以及对应的1小时内的四光子符合计数分布(c, g, h, i)。实验配置的8顶点图(j)及对应的18小时内的六光子符合计数分布(k)。
此外，所开发的多光子系统还能够提供样本作为种子，用于增强经典随机算法以求解NP问题，这种增强实际上来源于完美匹配计数与图的稠密度之间的正相关关系，即图的完美匹配计数越大通常代表这个图的稠密度更高。实验中对布尔可满足性问题和稠密子图问题进行了测试。
布尔可满足性问题是一个NP完全问题。考虑一个具有四个子句的布尔表达式：
，它能够转化为一个八顶点图的四顶点团问题。我们用所提出的多光子完美匹配求解系统对这个8顶点图进行构造，并记录了 2 小时内的所有四光子符合事件。
另一方面，k顶点最稠密子图问题为 NP 难问题，其定义为从给定的n顶点图中找到密度最大的k顶点子图，其中k < n为问题中指定的一个值。子图密度最大代表子图内部顶点之间所连接的边最多。在实验中构造了一个16顶点加权图，并记录其2小时内的四光子分布。随后利用所获得的样本来进行随机搜索，以找到最稠密四顶点子图，从结果能够发现从完美匹配求解系统中抽取样本作为随机种子时搜索效果显著优于用均匀采样样本的情况。
图3 布尔可满足性问题和稠密子图问题的样本增强验证。(a,b) 布尔可满足性问题的图构造及四光子符合计数分布。(c,d) 16顶点加权图的构造及四光子符合计数分布。(e) 利用均匀分布、实验分布、理想完美匹配分布进行随机搜索的结果。
对于以上实验中所有构造的无向图，实验结果的多光子分布保真度都超过了 90%。实验结果展示了所提出的多光子完美匹配求解系统对无向图配置的有效性、便捷性和可扩展性，并显示了其用于求解实际问题的潜力。
所提出的基于频率分组的多光子完美匹配求解系统的求解过程不是传统的搜索或优化，而是利用了量子叠加的特性，从同时到达探测器的所有可能状态的叠加中自然地保留满足完美匹配条件的状态并进行计数，这是经典方法所无法做到的。
本工作创造性地提出利用宽带光子对频率分组的多光子完美匹配求解系统。实验中展示了最多含16顶点的图的构造，验证了高维频率的优势，避开了复杂的相干性实验要求、同时还减少了空间资源、配置便捷简单。所开发的多光子系统还能够用于增强经典随机算法以求解NP问题，比如布尔可满足性问题和稠密子图问题等。对现有实验进行继续扩展时，需要更宽频的光子对源和更多输出端的波形整形器。所提出的实验装置还有望用于实现图同构和图相似度估计等更多应用。本工作得到了国家重点研发计划等项目的支持。
供稿：课题组
