Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Global Journal of Pure and Applied Sciences

Quantum algorithm for perfect matching problem by numbering method

Toru Fujimura

Published Jan 1, 2013• 0 citations
OpenAlex

Related papers

Quantum-Cooperative Method for Maximum Weight Perfect Matching Problem of Bipartite Graph

Guisheng Yin, Xiaohui Cui, Hongbin Dong +2 more

Journal of Computer Research and Development•Nov 1, 2014•1 citation

Finding a Perfect Matching of a Balanced Bipartite Graph by Quantum Search Algorithm

Hideaki Otsuki

•Mar 25, 2021•0 citations

Quantum Algorithms for Matching Problems

Sebastian Dörn

Theory of Computing Systems•May 29, 2008•20 citations

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

Pingyu Zhu, Qilin Zheng, Kun Wang +6 more

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. Perfect matching counting is a famously hard problem. Here, the authors propose a photonic perfect matching solver by multi-photon coincidence of grouped broadband frequency-correlated photon pairs. The samples from the solver can also be used to enhance searching algorithms for NP problems such as SAT and densest subgraph.

Nature Communications•Apr 22, 2025•3 citations

A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs

Kourosh Mirsohi, Sandy Irani, Michael T. Goodrich

Quantum speed-ups have been obtained for many fundamental graph problems, including most variants of matching. A notable exception, however, is the maximum-weight perfect matching (MWPM) problem in general graphs with integer edge weights, which is arguably the most challenging variant of matching. We present a quantum algorithm for MWPM in general graphs that runs in $\widetilde{O}(n m^{2/3}\log W)$ time, where $W$ is an upper bound on the magnitude of the edge weights. This is an improvement over the best known classical combinatorial bound of $\widetilde{O}(m\sqrt n \log W)$ in the dense regime, where $m\ge n^{3/2}$. To the best of our knowledge, this is the first quantum algorithm to obtain an asymptotic improvement over the best classical combinatorial algorithm for the MWPM problem in general graphs. The running time of our method accounts for QRAM initialization and access overheads up to polylogarithmic factors, as well as all classical updates to the data structures. At a high level, our algorithm is based on a classical framework due to Duan, Pettie, and Su, but our algorithm requires replacing certain classical tasks with quantum methods, alternative analysis of classical procedures, and the use of alternative data structures that can be implemented effectively in the QRAM model.

cs.DSCross-listedarXiv:2609.39457•Oct 1, 2026•0 citations

Gaussian boson sampling for perfect matchings of arbitrary graphs

Kamil Brádler, Pierre-Luc Dallaire-Demers, Patrick Rebentrost +2 more

A famously hard graph problem with a broad range of applications is computing the number of perfect matchings, that is, the number of unique and complete pairings of the vertices of a graph. We propose a method to estimate the number of perfect matchings of undirected graphs based on the relation between Gaussian boson sampling and graph theory. The probability of measuring zero or one photons in each output mode is directly related to the hafnian of the adjacency matrix, and thus to the number of perfect matchings of a graph. We present encodings of the adjacency matrix of a graph into a Gaussian state and show strategies to boost the sampling success probability for the studied graphs. With our method, a Gaussian boson sampling device can be used to estimate the number of perfect matchings significantly faster and with lower-energy consumption compared to a classical computer.

arXiv:1712.06729•Physical Review A•Sep 10, 2018•105 citations
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. Perfect matching counting is a famously hard problem. Here, the authors propose a photonic perfect matching solver by multi-photon coincidence of grouped broadband frequency-correlated photon pairs. The samples from the solver can also be used to enhance searching algorithms for NP problems such as SAT and densest subgraph.
Quantum speed-ups have been obtained for many fundamental graph problems, including most variants of matching. A notable exception, however, is the maximum-weight perfect matching (MWPM) problem in general graphs with integer edge weights, which is arguably the most challenging variant of matching. We present a quantum algorithm for MWPM in general graphs that runs in O~(nm2/3log⁡W)\widetilde{O}(n m^{2/3}\log W)O(nm2/3logW) time, where WWW is an upper bound on the magnitude of the edge weights. This is an improvement over the best known classical combinatorial bound of O~(mnlog⁡W)\widetilde{O}(m\sqrt n \log W)O(mn​logW) in the dense regime, where m≥n3/2m\ge n^{3/2}m≥n3/2. To the best of our knowledge, this is the first quantum algorithm to obtain an asymptotic improvement over the best classical combinatorial algorithm for the MWPM problem in general graphs. The running time of our method accounts for QRAM initialization and access overheads up to polylogarithmic factors, as well as all classical updates to the data structures. At a high level, our algorithm is based on a classical framework due to Duan, Pettie, and Su, but our algorithm requires replacing certain classical tasks with quantum methods, alternative analysis of classical procedures, and the use of alternative data structures that can be implemented effectively in the QRAM model.
A famously hard graph problem with a broad range of applications is computing the number of perfect matchings, that is, the number of unique and complete pairings of the vertices of a graph. We propose a method to estimate the number of perfect matchings of undirected graphs based on the relation between Gaussian boson sampling and graph theory. The probability of measuring zero or one photons in each output mode is directly related to the hafnian of the adjacency matrix, and thus to the number of perfect matchings of a graph. We present encodings of the adjacency matrix of a graph into a Gaussian state and show strategies to boost the sampling success probability for the studied graphs. With our method, a Gaussian boson sampling device can be used to estimate the number of perfect matchings significantly faster and with lower-energy consumption compared to a classical computer.