Solving perfect matchings by frequency-grouped multi-photon events using a silicon chip
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 c...
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2025-04-01
|
| Series: | Nature Communications |
| Online Access: | https://doi.org/10.1038/s41467-025-58711-8 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850172979177062400 |
|---|---|
| author | Pingyu Zhu Qilin Zheng Kun Wang Miaomiao Yu Gongyu Xia Jiacheng Liu Yong Liu Zhihong Zhu Ping Xu |
| author_facet | Pingyu Zhu Qilin Zheng Kun Wang Miaomiao Yu Gongyu Xia Jiacheng Liu Yong Liu Zhihong Zhu Ping Xu |
| author_sort | Pingyu Zhu |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-5865e85db4544769bce9a4131b6672ee |
| institution | OA Journals |
| issn | 2041-1723 |
| language | English |
| publishDate | 2025-04-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Nature Communications |
| spelling | doaj-art-5865e85db4544769bce9a4131b6672ee2025-08-20T02:19:57ZengNature PortfolioNature Communications2041-17232025-04-011611810.1038/s41467-025-58711-8Solving perfect matchings by frequency-grouped multi-photon events using a silicon chipPingyu Zhu0Qilin Zheng1Kun Wang2Miaomiao Yu3Gongyu Xia4Jiacheng Liu5Yong Liu6Zhihong Zhu7Ping Xu8Institute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer Science and Technology, National University of Defense TechnologyInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer Science and Technology, National University of Defense TechnologyInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer Science and Technology, National University of Defense TechnologyInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer Science and Technology, National University of Defense TechnologyHunan Provincial Key Laboratory of Novel Nano Optoelectronic information Materials and Devices, College of Advanced Interdisciplinary Studies, National University of Defense TechnologyHunan Provincial Key Laboratory of Novel Nano Optoelectronic information Materials and Devices, College of Advanced Interdisciplinary Studies, National University of Defense TechnologyInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer Science and Technology, National University of Defense TechnologyHunan Provincial Key Laboratory of Novel Nano Optoelectronic information Materials and Devices, College of Advanced Interdisciplinary Studies, National University of Defense TechnologyInstitute for Quantum Information & State Key Laboratory of High Performance Computing, College of Computer Science and Technology, National University of Defense TechnologyAbstract 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.https://doi.org/10.1038/s41467-025-58711-8 |
| spellingShingle | Pingyu Zhu Qilin Zheng Kun Wang Miaomiao Yu Gongyu Xia Jiacheng Liu Yong Liu Zhihong Zhu Ping Xu Solving perfect matchings by frequency-grouped multi-photon events using a silicon chip Nature Communications |
| title | Solving perfect matchings by frequency-grouped multi-photon events using a silicon chip |
| title_full | Solving perfect matchings by frequency-grouped multi-photon events using a silicon chip |
| title_fullStr | Solving perfect matchings by frequency-grouped multi-photon events using a silicon chip |
| title_full_unstemmed | Solving perfect matchings by frequency-grouped multi-photon events using a silicon chip |
| title_short | Solving perfect matchings by frequency-grouped multi-photon events using a silicon chip |
| title_sort | solving perfect matchings by frequency grouped multi photon events using a silicon chip |
| url | https://doi.org/10.1038/s41467-025-58711-8 |
| work_keys_str_mv | AT pingyuzhu solvingperfectmatchingsbyfrequencygroupedmultiphotoneventsusingasiliconchip AT qilinzheng solvingperfectmatchingsbyfrequencygroupedmultiphotoneventsusingasiliconchip AT kunwang solvingperfectmatchingsbyfrequencygroupedmultiphotoneventsusingasiliconchip AT miaomiaoyu solvingperfectmatchingsbyfrequencygroupedmultiphotoneventsusingasiliconchip AT gongyuxia solvingperfectmatchingsbyfrequencygroupedmultiphotoneventsusingasiliconchip AT jiachengliu solvingperfectmatchingsbyfrequencygroupedmultiphotoneventsusingasiliconchip AT yongliu solvingperfectmatchingsbyfrequencygroupedmultiphotoneventsusingasiliconchip AT zhihongzhu solvingperfectmatchingsbyfrequencygroupedmultiphotoneventsusingasiliconchip AT pingxu solvingperfectmatchingsbyfrequencygroupedmultiphotoneventsusingasiliconchip |