Hybrid Quantum-Classical Algorithms for Solving the Weighted CSP

Authors

Hong Xu, Kexuan Sun, Sven Koenig, Itay Hen, T. K. Satish Kumar

Abstract

Many kinds of algorithms have been developed for solving the weighted constraint satisfaction problem (WCSP), a combinatorial optimization problem that frequently appears in AI.Unfortunately, its NP-hardness prohibits the existence of an algorithm for solving it that is universally efficient on classical computers. Therefore, a peek into quantum computers may be imperative for solving the WCSP efficiently. In this paper, we focus on a specific type of quantum computer, called the quantum annealer, which approximately solves quadratic unconstrained binary optimization (QUBO) problems. We propose the first three hybrid quantum-classical algorithms (HQCAs) for the WCSP: one specifically for the binary Boolean WCSP and the other two for the general WCSP. We experimentally show that the HQCA based on simple polynomial reformulation works well on the binary Boolean WCSP, but the HQCA based on the constraint composite graph works best on the general WCSP.