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

Pingyu Zhu, Qilin Zheng, Kun Wang, Miaomiao Yu, Gongyu Xia, Jiacheng Liu, Yong Liu, Zhihong Zhu and Ping Xu ()
Additional contact information
Pingyu Zhu: National University of Defense Technology
Qilin Zheng: National University of Defense Technology
Kun Wang: National University of Defense Technology
Miaomiao Yu: National University of Defense Technology
Gongyu Xia: National University of Defense Technology
Jiacheng Liu: National University of Defense Technology
Yong Liu: National University of Defense Technology
Zhihong Zhu: National University of Defense Technology
Ping Xu: National University of Defense Technology

Nature Communications, 2025, vol. 16, issue 1, 1-8

Abstract: 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.

Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/s41467-025-58711-8 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:16:y:2025:i:1:d:10.1038_s41467-025-58711-8

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/s41467-025-58711-8

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().