IDEAS home Printed from https://ideas.repec.org/a/nat/natcom/v16y2025i1d10.1038_s41467-025-58711-8.html
   My bibliography  Save this article

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

Author

Listed:
  • 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
    Hefei National Laboratory)

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.

Suggested Citation

  • Pingyu Zhu & Qilin Zheng & Kun Wang & Miaomiao Yu & Gongyu Xia & Jiacheng Liu & Yong Liu & Zhihong Zhu & Ping Xu, 2025. "Solving perfect matchings by frequency-grouped multi-photon events using a silicon chip," Nature Communications, Nature, vol. 16(1), pages 1-8, December.
    • Handle: RePEc:nat:natcom:v:16:y:2025:i:1:d:10.1038_s41467-025-58711-8
    DOI: 10.1038/s41467-025-58711-8
    as

    Download full text from publisher

    File URL: https://www.nature.com/articles/s41467-025-58711-8
    File Function: Abstract
    Download Restriction: no
    File URL: https://libkey.io/10.1038/s41467-025-58711-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Sören Wengerowsky & Siddarth Koduru Joshi & Fabian Steinlechner & Hannes Hübel & Rupert Ursin, 2018. "An entanglement-based wavelength-multiplexed quantum communication network," Nature, Nature, vol. 564(7735), pages 225-228, December.
    2. Kaiyi Qian & Kai Wang & Leizhen Chen & Zhaohua Hou & Mario Krenn & Shining Zhu & Xiao-song Ma, 2023. "Multiphoton non-local quantum interference controlled by an undetected photon," Nature Communications, Nature, vol. 14(1), pages 1-7, December.
    3. Enrico Maria Fenoaltea & Izat B. Baybusinov & Jianyang Zhao & Lei Zhou & Yi-Cheng Zhang, 2021. "The Stable Marriage Problem: an Interdisciplinary Review from the Physicist's Perspective," Papers 2103.11458, arXiv.org.
    4. Michael Kues & Christian Reimer & Piotr Roztocki & Luis Romero Cortés & Stefania Sciara & Benjamin Wetzel & Yanbing Zhang & Alfonso Cino & Sai T. Chu & Brent E. Little & David J. Moss & Lucia Caspani , 2017. "On-chip generation of high-dimensional entangled quantum states and their coherent control," Nature, Nature, vol. 546(7660), pages 622-626, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Marco LiCalzi, 2022. "Bipartite choices," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 45(2), pages 551-568, December.
    2. Izat B. Baybusinov & Enrico Maria Fenoaltea & Yi-Cheng Zhang, 2022. "Negotiation problem," Papers 2201.12619, arXiv.org.
    3. Hsuan-Hao Lu & Karthik V. Myilswamy & Ryan S. Bennink & Suparna Seshadri & Mohammed S. Alshaykh & Junqiu Liu & Tobias J. Kippenberg & Daniel E. Leaird & Andrew M. Weiner & Joseph M. Lukens, 2022. "Bayesian tomography of high-dimensional on-chip biphoton frequency combs with randomized measurements," Nature Communications, Nature, vol. 13(1), pages 1-12, December.
    4. Hao Yu & Stefania Sciara & Mario Chemnitz & Nicola Montaut & Benjamin Crockett & Bennet Fischer & Robin Helsten & Benjamin Wetzel & Thorsten A. Goebel & Ria G. Krämer & Brent E. Little & Sai T. Chu & , 2025. "Quantum key distribution implemented with d-level time-bin entangled photons," Nature Communications, Nature, vol. 16(1), pages 1-10, December.
    5. Mehran Farzadmehr & Valentin Carlan & Thierry Vanelslander, 2023. "Contemporary challenges and AI solutions in port operations: applying Gale–Shapley algorithm to find best matches," Journal of Shipping and Trade, Springer, vol. 8(1), pages 1-44, December.
    6. H. H. Zhu & J. Zou & H. Zhang & Y. Z. Shi & S. B. Luo & N. Wang & H. Cai & L. X. Wan & B. Wang & X. D. Jiang & J. Thompson & X. S. Luo & X. H. Zhou & L. M. Xiao & W. Huang & L. Patrick & M. Gu & L. C., 2022. "Space-efficient optical computing with an integrated chip diffractive neural network," Nature Communications, Nature, vol. 13(1), pages 1-9, December.
    7. Gao, Fujuan & Fenoaltea, Enrico Maria & Zhang, Yi-Cheng, 2023. "Market failure in a new model of platform design with partially informed consumers," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 619(C).
    8. Saket Kaushal & A. Aadhi & Anthony Roberge & Roberto Morandotti & Raman Kashyap & José Azaña, 2023. "All-fibre phase filters with 1-GHz resolution for high-speed passive optical logic processing," Nature Communications, Nature, vol. 14(1), pages 1-10, December.
    9. Jiyuan Zheng & Xingjun Xue & Cheng Ji & Yuan Yuan & Keye Sun & Daniel Rosenmann & Lai Wang & Jiamin Wu & Joe C. Campbell & Supratik Guha, 2022. "Dynamic-quenching of a single-photon avalanche photodetector using an adaptive resistive switch," Nature Communications, Nature, vol. 13(1), pages 1-12, December.
    10. Mujtaba Zahidy & Domenico Ribezzo & Claudia Lazzari & Ilaria Vagniluca & Nicola Biagi & Ronny Müller & Tommaso Occhipinti & Leif K. Oxenløwe & Michael Galili & Tetsuya Hayashi & Dajana Cassioli & Anto, 2024. "Practical high-dimensional quantum key distribution protocol over deployed multicore fiber," Nature Communications, Nature, vol. 15(1), pages 1-6, December.
    11. Han Zhao & Bingzhao Li & Huan Li & Mo Li, 2022. "Enabling scalable optical computing in synthetic frequency dimension using integrated cavity acousto-optics," Nature Communications, Nature, vol. 13(1), pages 1-7, December.
    12. Gheorghe Taran & Eufemio Moreno-Pineda & Michael Schulze & Edgar Bonet & Mario Ruben & Wolfgang Wernsdorfer, 2023. "Direct determination of high-order transverse ligand field parameters via µSQUID-EPR in a Et4N[160GdPc2] SMM," Nature Communications, Nature, vol. 14(1), pages 1-9, December.
    13. Meng, Fanyuan & Zhu, Jiadong & Yao, Yuheng & Fenoaltea, Enrico Maria & Xie, Yubo & Yang, Pingle & Liu, Run-Ran & Zhang, Jianlin, 2023. "Disagreement and fragmentation in growing groups," Chaos, Solitons & Fractals, Elsevier, vol. 167(C).
    14. Peng, Wenxiang & Chen, Xiangsheng & Xue, Zhaojie & Liao, Yubin & You, Jintao, 2024. "Platform-based stable truck matching problem with trailer-swapping mode," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 188(C).
    15. Fenoaltea, Enrico Maria & Baybusinov, Izat B. & Na, Xu & Zhang, Yi-Cheng, 2022. "A local interaction dynamic for the matching problem," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 604(C).
    16. Ling-Jun Kong & Weixuan Zhang & Peng Li & Xuyue Guo & Jingfeng Zhang & Furong Zhang & Jianlin Zhao & Xiangdong Zhang, 2022. "High capacity topological coding based on nested vortex knots and links," Nature Communications, Nature, vol. 13(1), pages 1-8, December.
    17. Bereneice Sephton & Adam Vallés & Isaac Nape & Mitchell A. Cox & Fabian Steinlechner & Thomas Konrad & Juan P. Torres & Filippus S. Roux & Andrew Forbes, 2023. "Quantum transport of high-dimensional spatial information with a nonlinear detector," Nature Communications, Nature, vol. 14(1), pages 1-9, December.
    18. Baybusinov, Izat B. & Fenoaltea, Enrico Maria & Zhang, Yi-Cheng, 2022. "Negotiation problem," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 592(C).
    19. Marco Clementi & Federico Andrea Sabattoli & Massimo Borghi & Linda Gianini & Noemi Tagliavacche & Houssein El Dirani & Laurene Youssef & Nicola Bergamasco & Camille Petit-Etienne & Erwine Pargon & J., 2023. "Programmable frequency-bin quantum states in a nano-engineered silicon device," Nature Communications, Nature, vol. 14(1), pages 1-10, December.
    20. Sebastian Philipp Neumann & Alexander Buchner & Lukas Bulla & Martin Bohmann & Rupert Ursin, 2022. "Continuous entanglement distribution over a transnational 248 km fiber link," Nature Communications, Nature, vol. 13(1), pages 1-8, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:nat:natcom:v:16:y:2025:i:1:d:10.1038_s41467-025-58711-8. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.nature.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.