Scholarlink

<p>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>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年4月22日

查看全文
  • Pingyu Zhu,
  • Qilin Zheng,
  • Kun Wang,
  • Miaomiao Yu,
  • Gongyu Xia,
  • Jiacheng Liu,
  • Yong Liu,
  • Zhihong Zhu,
  • Ping Xu

摘要

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.