制約をもつ組合せ最適化問題をイジング計算機で効率的かつ高精度に解くための新たな手法を開発

変数の個数を削減し性能向上、ソフトウェアへの応用に期待

2023年1月26日
早稲田大学
科学技術振興機構（JST）

詳細は、早稲田大学ＷＥＢサイトをご覧ください⇒

【発表のポイント】
● イジング計算機で現実世界の組合せ最適化問題を解くためには、最適化問題に含まれる多くの制約群を効率的に取り扱う必要がある。 
● 本研究では、線形制約をイジング計算機で取り扱うための新しい手法として、組合せ最適化問題の記述に必要な変数の個数を削減し、イジング計算機の性能を改善する手法を構築した。 
● 本手法を取り込んだイジング計算機ソフトウェアの開発により、高精度に現実世界の組合せ最適化問題を解くことが期待できる。 

量子アニーリング計算機※1 をはじめとするイジング計算機※2 を現実世界の組合せ最適化問題※3 に活用するためには、組合せ最適化問題がもつ制約を効率的に取り扱うことが重要となります。この問題に対して、早稲田大学理工学術院講師の白井達彦（しらい たつひこ）氏、同大学理工学術院教授の戸川望（とがわ のぞむ）氏らの研究グループは、線形制約※4 をもつ組合せ最適化問題を、イジング計算機で効率的に解くための新しい手法を開発しました（図１）。この手法は、制約を用いて束縛スピンを自由スピンで表現することにより、自由スピンのみで組合せ最適化問題を記述するもので、本研究グループは、本手法を量子アニーリング計算機等のイジング計算機に適用し、既存イジング計算機でその有効性を確認しました。

【画像：https://kyodonewsprwire.jp/img/202301262408-O1-Y4Gw5WZU】

本研究成果は、米国のIEEE Computer Societyが発行する『IEEE Transactions on Computers』online版にEarly Access Articlesとして2023年1月24日（火）（現地時間）に掲載されました。
論文名：Spin-variable reduction method for handling linear equality constraints in Ising machines

【 用語解説 】
※1　量子アニーリング計算機
組合せ最適化問題を高速に解決すると期待される計算機。量子効果により量子重ね合わせ状態を実現させ、それを初期状態として用意し、徐々に量子効果を弱める。同時に組合せ最適化問題を表現するイジングモデルの効果を強めることにより、イジングモデルの安定状態を実現させるという機構で動作する。
※2　イジング計算機
組合せ最適化問題をイジングモデルで表現し、組合せ最適化問題を解決するマシンの総称。上記、量子アニーリング計算機はイジング計算機の一種である。
※3　組合せ最適化問題
膨大な選択肢の中から､与えられた制約を満たしつつ、関数の最小値（または最大値）をとる選択肢を求める問題の総称。制約とは守らなければならないルールをさす。
※4　線形制約
【画像：https://kyodonewsprwire.jp/img/202301262408-O2-8zSSYx7q】

【論文情報】
雑誌名：IEEE Transactions on Computers
論文名：Spin-variable reduction method for handling linear equality constraints in Ising machines
執筆者名（所属機関名）：Tatsuhiko Shirai（早稲田大学）, Nozomu Togawa（早稲田大学）
※　所属は論文投稿時
掲載日（現地時間）：2023年1月24日
掲載URL：https://ieeexplore.ieee.org/document/10025381
DOI：https://doi.org/10.1109/TC.2023.3239539