Solving Quantum-Inspired Perfect Matching Problems via Tutte-Theorem-Based Hybrid Boolean Constraints

Moshe Y. Vardi, Zhiwei ZhangIJCAI 2023 · DOI

Introduction

The design of large-scale quantum computers is increasingly becoming a challenge of combinatorial optimization. A recent study presented at IJCAI-23 by Moshe Y. Vardi and Zhiwei Zhang addresses a critical bottleneck in quantum optical circuit design. By applying classical graph theory—specifically Tutte’s Theorem—to quantum circuit verification, the authors have developed a method that significantly outperforms existing quantum-inspired algorithms.

The FORALL-PMVC Problem

In quantum optics, circuits are often modeled as bicolored graphs. In these models, vertices represent optical paths, and edges represent non-linear crystals that emit entangled photons. A physical "coincidence" in the circuit corresponds to a perfect matching in the graph.

The primary challenge is the FORALL-PMVC (Perfect Matchings exist for all legal Vertex Colorings) problem. This problem asks whether every "legal" quantum state, represented as a vertex coloring, has at least one valid physical realization, represented as a perfect matching. While manageable for simple states like GHZ or W states, this problem becomes computationally explosive for Dicke states, where the number of legal colorings grows exponentially with the number of vertices.

Mapping between quantum circuits, bicolored graphs, and perfect matchings.

Methodology: Tutte’s Theorem and Boolean Encoding

The authors' breakthrough involves a shift in perspective. Instead of attempting to prove that a matching exists for every possible coloring (a $\forall \exists$ problem), they search for a "witness" that a matching does not exist for at least one coloring.

Tutte’s Theorem Encoding

They utilize Tutte’s Theorem, which provides a necessary and sufficient condition for the existence of a perfect matching. According to the theorem, a graph lacks a perfect matching if and only if there exists a subset of vertices (a "Tutte set") whose removal results in more odd connected components than the number of vertices in the set itself.

By encoding this theorem into Boolean constraints, the authors created the TutteEncoding. This allows a SAT solver to simultaneously search for a legal vertex coloring and a corresponding Tutte set that proves the absence of a perfect matching.

A bicolored graph and its corresponding perfect matchings for different colorings.

Hybrid Constraints and Optimization

The encoding utilizes hybrid constraints to manage the complexity:

  • Cardinality Constraints: Used to count the size of the Tutte set and the number of odd components.
  • XOR Constraints: Employed for efficient parity checking to determine if a component has an odd number of vertices.

To further enhance performance, the authors introduced symmetry-breaking techniques to prune the search space, preventing the solver from exploring redundant permutations of the same graph structure.

Experimental Results

The Tutte-based approach was evaluated using synthetic benchmarks inspired by quantum states, including complete bipartite graphs and Dicke states. The results demonstrated a massive performance leap:

  • Exponential Speedup: On the $Dicke(10, 5)$ benchmark, the optimized Tutte-CNF encoding was 1,200 times faster than the unoptimized version.
  • Scalability: The method successfully verified $Dicke(40, 20)$ instances within 1,000 seconds. In comparison, the previous state-of-the-art (Enum-Blossom) failed at $n=26$, and general-purpose QBF solvers failed at $n=8$.

Conclusion

By "teaching" graph theory to SAT solvers through Tutte’s Theorem, Vardi and Zhang have provided a robust tool for the verification of quantum circuits. This approach demonstrates the power of combining classical mathematical theorems with modern automated reasoning to solve complex problems in emerging technologies. Future work will look to extend this model to handle complex amplitudes and address the inverse problem of circuit synthesis.

Summary updated

BibTeX
@inproceedings{vardi2023solving,
  author = {Moshe Y. Vardi and Zhiwei Zhang},
  title = {{Solving Quantum-Inspired Perfect Matching Problems via Tutte-Theorem-Based Hybrid Boolean Constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/227},
}
Figure