制約を持つ組み合わせ最適化問題をイジング計算機で効率的かつ高精度に解くための新たな手法を開発
～変数の個数を削減し性能向上、ソフトウェアへの応用に期待～
更新日：2023.01.26
ポイント
- イジング計算機で現実世界の組み合わせ最適化問題を解くためには、最適化問題に含まれる多くの制約群を効率的に取り扱う必要がある。
- 本研究では、線形制約をイジング計算機で取り扱うための新しい手法として、組み合わせ最適化問題の記述に必要な変数の個数を削減し、イジング計算機の性能を改善する手法を構築した。
- 本手法を取り込んだイジング計算機ソフトウェアの開発により、高精度に現実世界の組み合わせ最適化問題を解くことが期待できる。
概要
量子アニーリング計算機を始めとするイジング計算機を現実世界の組み合わせ最適化問題に活用するためには、組み合わせ最適化問題が持つ制約を効率的に取り扱うことが重要となります。この問題に対して、早稲田大学 理工学術院 講師の白井 達彦 氏、同大学 理工学術院 教授の戸川 望 氏らの研究グループは、線形制約を持つ組み合わせ最適化問題を、イジング計算機で効率的に解くための新しい手法を開発しました。この手法は、制約を用いて束縛スピンを自由スピンで表現することにより、自由スピンのみで組み合わせ最適化問題を記述するもので、本研究グループは、本手法を量子アニーリング計算機などのイジング計算機に適用し、既存イジング計算機でその有効性を確認しました。
本研究成果は、米国のＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙが発行する「ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ」ｏｎｌｉｎｅ版にＥａｒｌｙ Ａｃｃｅｓｓ Ａｒｔｉｃｌｅｓとして２０２３年１月２４日（火）（現地時間）に掲載されました。