量子アニーリングマシンで大規模な問題を解法するための技術を開発

本発表の詳細は、早稲田大学のホームページをご覧ください。
(リンク »)

発表のポイント
●現状のイジングマシンは、ハードウエアの制約により、入力可能な問題規模が制限されていた。
●本研究では、最適性を失わずに大規模な組み合わせ最適化問題を小さな問題に分割する条件を解明し、さらに、解法可能な問題規模に小さくし繰り返し解法するアルゴリズムを開発した。
●本技術により、イジングマシンを使った現実世界の組み合わせ最適化問題の活用事例や活用範囲を広げることが期待できる。

量子アニーリングマシン※1（イジングマシン※2）は、ハードウエア上の制約により、入力可能な問題規模が制限されていました。これを解消するため、早稲田大学グリーン・コンピューティング・システム研究機構（東京都新宿区、機構長　木村啓二） (リンク ») の跡部悠太（あとべ ゆうた）氏、多和田雅師（たわだ まさし）研究院講師 (リンク ») 、同大学理工学術院の戸川望（とがわ のぞむ）教授 (リンク ») らの研究グループは、最適性を失わずに大規模な問題を小さな問題に分割する条件をこのたび解明しました。さらにこれにもとづき、本研究グループは、小さな問題を繰り返し解法することで、量子アニーリングマシンやイジングマシンで大規模な問題を解法する技術を開発しました。

【画像： (リンク ») 】

本研究成果は、米国のIEEE Computer Societyが発行する『IEEE Transactions on Computers (リンク ») 』online版（Early Access）にPreprintとして2021年12月28日（火）（現地時間）に掲載されました。
論文名：Hybrid Annealing Method based on subQUBO Model Extraction with Multiple Solution Instances

※1　量子アニーリングマシン
●組合せ最適化問題を高速に解決すると期待されるマシン。量子効果により量子重ね合わせ状態を実現させ、それを初期状態として用意し、徐々に量子効果を弱める。同時に組合せ最適化問題を表現するイジングモデルの効果を強めることにより、イジングモデルの安定状態を実現させるという機構で動作する。

※2　イジングマシン
●組合せ最適化問題をイジングモデルで表現し、組合せ最適化問題を解決するマシンの総称。上記、量子アニーリングマシンはイジングマシンの一種である。