利用硅芯片通过频率分组多光子事件求解完美匹配

Solving perfect matchings by frequency-grouped multi-photon events using a silicon chip.

作者信息

Zhu Pingyu, Zheng Qilin, Wang Kun, Yu Miaomiao, Xia Gongyu, Liu Jiacheng, Liu Yong, Zhu Zhihong, Xu Ping

机构信息

Institute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer Science and Technology, National University of Defense Technology, Changsha, China.

Hunan Provincial Key Laboratory of Novel Nano Optoelectronic information Materials and Devices, College of Advanced Interdisciplinary Studies, National University of Defense Technology, Changsha, China.

出版信息

Nat Commun. 2025 Apr 22;16(1):3670. doi: 10.1038/s41467-025-58711-8.

DOI:10.1038/s41467-025-58711-8

PMID:40263297

原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC12015585/

Abstract

Computing the number of perfect matchings of a graph is a famous #P-complete problem. In this work, taking the advantages of the frequency dimension of photon, we propose and implement a photonic perfect matching solver, by combining two key techniques, frequency grouping and multi-photon counting. Based on a broadband photon-pair source from a silicon quantum chip and a wavelength-selective switch, we configure graphs up to sixteen vertices and estimate the perfect matchings of subgraphs up to six vertices. The experimental fidelities are more than 90% for all the graphs. Moreover, we demonstrate that the developed photonic system can enhance classical stochastic algorithms for solving nondeterministic-polynomial-time(NP) problems, such as the Boolean satisfiability problem and the densest subgraph. Our work contributes a promising method for solving the perfect matchings problem, which is simple in experiment setup and convenient to transform or scale up the object graph by regulating the frequency-correlated photon pairs.

摘要

计算一个图的完美匹配数是一个著名的#P完全问题。在这项工作中，利用光子的频率维度，我们通过结合频率分组和多光子计数这两项关键技术，提出并实现了一种光子完美匹配求解器。基于来自硅量子芯片的宽带光子对源和波长选择开关，我们配置了多达16个顶点的图，并估计了多达6个顶点的子图的完美匹配数。所有图的实验保真度均超过90%。此外，我们证明了所开发的光子系统可以增强用于解决非确定性多项式时间（NP）问题的经典随机算法，如布尔可满足性问题和最密集子图问题。我们的工作为解决完美匹配问题贡献了一种有前景的方法，该方法实验设置简单，通过调节与频率相关的光子对方便地变换或扩大目标图。