制約をもつ組合せ最適化問題をイジング計算機で効率的かつ高精度に解くための新たな手法を開発
変数の個数を削減し性能向上、ソフトウェアへの応用に期待
2023年1月26日
早稲田大学
科学技術振興機構(JST)
【発表のポイント】
● イジング計算機で現実世界の組合せ最適化問題を解くためには、最適化問題に含まれる多くの制約群を効率的に取り扱う必要がある。
● 本研究では、線形制約をイジング計算機で取り扱うための新しい手法として、組合せ最適化問題の記述に必要な変数の個数を削減し、イジング計算機の性能を改善する手法を構築した。
● 本手法を取り込んだイジング計算機ソフトウェアの開発により、高精度に現実世界の組合せ最適化問題を解くことが期待できる。
量子アニーリング計算機※1 をはじめとするイジング計算機※2 を現実世界の組合せ最適化問題※3 に活用するためには、組合せ最適化問題がもつ制約を効率的に取り扱うことが重要となります。この問題に対して、早稲田大学理工学術院講師の白井達彦(しらい たつひこ)氏、同大学理工学術院教授の戸川望(とがわ のぞむ)氏らの研究グループは、線形制約※4 をもつ組合せ最適化問題を、イジング計算機で効率的に解くための新しい手法を開発しました(図1)。この手法は、制約を用いて束縛スピンを自由スピンで表現することにより、自由スピンのみで組合せ最適化問題を記述するもので、本研究グループは、本手法を量子アニーリング計算機等のイジング計算機に適用し、既存イジング計算機でその有効性を確認しました。
本研究成果は、米国の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 線形制約
【論文情報】
雑誌名: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://www.waseda.jp/top/
過去に配信したプレスリリース
スキルミオンスピン波リザバーの高度な文字認識機能を実証
11/29 14:25
第23回「石橋湛山記念 早稲田ジャーナリズム大賞」発表
11/14 10:30
異なる戦略で形成した大脳オルガノイド血管系の特徴を明らかに
11/9 11:42
動的条件下でのX線CT撮影技術を開発
11/7 17:32
筋線維伸長の抑制機構を解明
10/24 14:00
ロボットアーム運動生成 旧来比4倍を超える高速計算手法を開発
10/16 11:56
早稲田大学庭球部主催の国際トーナメント「早稲田オープン」開催に向けてスポンサーを募集
10/13 14:00
プリン代謝を介した脳発生制御機構を発見
10/13 12:00
【開催中止】イスラエル経済産業大臣(ニール・バルカット氏)講演のご案内
10/5 14:15
早稲田大学歴史館 秋季企画展「学徒出陣80年 学徒たちの証言を後世に」のご案内
10/5 11:00
【早稲田大学】ゴルフ部 ユニフォームスポンサーに「メルセデス・ベンツ日本」
9/29 17:12