組合せ最適化問題における制約条件を考慮したQUBOソルバ

摘要

制約なし二値変数二次計画問題（QUBO）にマッピングされた組合せ最適化問題は、量子コンピュータを用いて高速に求解できるとして注目されている。一方で、量子コンピュータよりも大規模な問題を解くために、QUBOをデジタルコンピュータを用いて解く手法の研究開発も盛んである。本稿では、組合せ最適化問題の制約条件情報を求解時に用いることにより、デジタルコンピュータでQUBOを高速に求解する手法を提案する。巡回セールスマン問題を対象に評価した結果、提案手法は従来手法と50倍以上高速に同等以上精度の解を得ることができた。