# Quantum-Inspired Perfect Matching under Vertex-Color Constraints

arXiv: https://arxiv.org/abs/2209.13063 · HTML: https://mlsanity.com/paper/2209.13063/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2022.

## Built on by (most cited first, 2 of 2)

- [Solving Quantum-Inspired Perfect Matching Problems via Tutte's Theorem-Based Hybrid Boolean Constraints](https://mlsanity.com/paper/2301.09833/) (2023)
- [FourierCSP: Differentiable Constraint Satisfaction Problem Solving by Walsh-Fourier Expansion](https://mlsanity.com/paper/2510.04480/) (2025)

## Abstract (arXiv)

We propose and study the graph-theoretical problem EXISTS-PMVC: the existence of perfect matching under vertex-color constraints on graphs with bi-colored edges. EXISTS-PMVC is of special interest because of its motivation from quantum-state identification and quantum-experiment design, as well as its rich expressiveness, i.e., EXISTS-PMVC naturally subsumes important constrained matching problems, such as exact perfect matching. We give complexity and algorithmic results for EXISTS-PMVC under two types of vertex color constraints: (1) decision-diagram constraints (EXISTS-PMVC-DD) and (2) symmetric constraints (EXISTS-PMVC-Sym). For EXISTS-PMVC-DD, we reveal its NP-hardness by a graph-gadget technique. We prove that EXISTS-PMVC-Sym with a bounded number of colors (EXISTS-PMVC-Sym-Bounded) is polynomially equivalent with Exact Perfect Matching (XPM), which implies that EXISTS-PMVC-Sym-Bounded is in RNC on general graphs and PTIME on planar graphs. Directly applying algorithms for XPM to solve EXISTS-PMVC-Sym-Bounded is, however, impractical. We propose algorithms that natively handle EXISTS-PMVC-Sym-Bounded with considerably better complexity. Our novel results for EXISTS-PMVC provide insights into both constrained matching and scalable quantum experiment design.