IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum
A Constraint-Handling Capability Selection Method for Quantum-Inspired Annealers
Kotaro Bannai, Kazuhiko Komatsu, Takamasa Nakasone, Shintaro Momose, Hiroaki Kobayashi
Abstract
Quantum-inspired annealers implemented on digital platforms have attracted attention as fast solvers for combinatorial optimization problems. To address the difficulty of handling constraints with penalty functions in the standard QUBO formulation, recent annealers are equipped with specialized constraint-handling capabilities. However, due to the diversity of these capabilities, the method for selecting the appropriate capabilities based on the problem structure has not been thoroughly clarified. In this paper, we propose a selection method for constraint-handling capabilities based on problem characteristics such as the nature of objective functions and constraints, and QUBO coupling density. We verify the validity of the method by evaluating search performance on problems involving one-hot, inequality, and prohibited-pair constraints. The evaluation results confirm that applying the proposed method maximizes the search performance of quantum-inspired annealers.