制約をもつ組合せ最適化問題をイジング計算機で効率的かつ高精度に解くための新たな手法を開発
2023年1月26日
早稲田大学
科学技術振興機構(JST)
詳細は、早稲田大学WEBサイトをご覧ください⇒
【発表のポイント】
● イジング計算機で現実世界の組合せ最適化問題を解くためには、最適化問題に含まれる多くの制約群を効率的に取り扱う必要がある。
● 本研究では、線形制約をイジング計算機で取り扱うための新しい手法として、組合せ最適化問題の記述に必要な変数の個数を削減し、イジング計算機の性能を改善する手法を構築した。
● 本手法を取り込んだイジング計算機ソフトウェアの開発により、高精度に現実世界の組合せ最適化問題を解くことが期待できる。
量子アニーリング計算機※1 をはじめとするイジング計算機※2 を現実世界の組合せ最適化問題※3 に活用するためには、組合せ最適化問題がもつ制約を効率的に取り扱うことが重要となります。この問題に対して、早稲田大学理工学術院講師の白井達彦(しらい たつひこ)氏、同大学理工学術院教授の戸川望(とがわ のぞむ)氏らの研究グループは、線形制約※4 をもつ組合せ最適化問題を、イジング計算機で効率的に解くための新しい手法を開発しました(図1)。この手法は、制約を用いて束縛スピンを自由スピンで表現することにより、自由スピンのみで組合せ最適化問題を記述するもので、本研究グループは、本手法を量子アニーリング計算機等のイジング計算機に適用し、既存イジング計算機でその有効性を確認しました。
【画像: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
カンニング竹山がキダ・タローさん追悼「VTRを注意してくれた最高顧問」
何があった!?「エアコン」が想定外の壊れ具合!投稿者に話を聞いた
【ヤクルト】松本健吾偉業に亜大先輩・高津監督「『亜細亜魂です』って訳分からないこと言ってた」
キダ・タロー氏死去
FinalSpark、バイオコンピューティングのためのヒト神経細胞を用いた初の遠隔研究プラットフォームを発表
大手建設企業が不変データ・コアの構築にBoomiを導入
【柏】今季加入の島村拓弥「お寿司ごちそうしてもらおうかな」細谷真大の今季初得点をアシスト
小関裕太と吉柳咲良でミュージカル「ロミオ&ジュリエット」21年以来3年ぶり6度目の上演
エクソーラ、ゲームとゲーム開発の未来に関する四半期インサイト・レポートをリリース。2024年春季のメトリックと今後のトレンドに対する予備分析
あのちゃんが合わない男性芸人の名前を実名告白、上田晋也も「合うわけない」と大納得
何があった!?「エアコン」が想定外の壊れ具合!投稿者に話を聞いた
ヒカル、浮気相手とのLINE流出にドン引きの声「キモすぎる」「吐きそう」
時代劇の常識を覆す!仇討ち・無礼討ちの厳格なルール
岡本夏生(56)、1600日ぶりにブログを更新した現在が衝撃
玉置浩二の妻、青田典子(53)の現在がとんでもない事になっていると話題に
3度逮捕の38歳小向美奈子「今はやってないですよね?」の直撃質問に”回答”
ちとせよしの、美バストあらわな大胆コスチュームで観客を魅了 浜松オートレースヴィーナス就任
ユーチューバーもこう氏、元彼女・成海瑠奈について赤裸々告白
坂上忍、連ドラ撮影初日”5時間大遅刻”俳優の名明かす「総スカンくらっちゃって」
「東京ラブストーリー」出演55歳女優が黒髪ショートで久々TV「誰か分からん」「スタイル健在」
何があった!?「エアコン」が想定外の壊れ具合!投稿者に話を聞いた
岡本夏生(56)、1600日ぶりにブログを更新した現在が衝撃
ユーチューバーもこう氏、元彼女・成海瑠奈について赤裸々告白
玉置浩二の妻、青田典子(53)の現在がとんでもない事になっていると話題に
ヒカル、浮気相手とのLINE流出にドン引きの声「キモすぎる」「吐きそう」
ガーシー、またも綾野剛の暴露写真でネット歓喜「この写真見て笑っちゃう」
完全にダマされた! 『ラヴィット!』あのちゃん“事故レベル”大暴走は『水ダウ』遠隔操作のしわざだった ネットも納得
73歳神田正輝「旅サラダ」生放送で“12歳下俳優”から呼び捨てされ激論
42歳ママタレ20年ぶり水着披露「レベチ」「マジ天使」「最高」55歳夫のピン芸人と2児
ガーシー、佐野ひなこの暴露を示唆でネット騒然「ファンだったのに」
カンニング竹山がキダ・タローさん追悼「VTRを注意してくれた最高顧問」
NY外為:ドル安値圏でもみ合い、カシュカリ米MN連銀総裁は依然高金利据え置きを支持
【ヤクルト】松本健吾偉業に亜大先輩・高津監督「『亜細亜魂です』って訳分からないこと言ってた」
FinalSpark、バイオコンピューティングのためのヒト神経細胞を用いた初の遠隔研究プラットフォームを発表
キダ・タロー氏死去
大手建設企業が不変データ・コアの構築にBoomiを導入
BTC急伸、6.5万ドル台回復、米金利先安観が支援【フィスコ・暗号資産速報】
【柏】今季加入の島村拓弥「お寿司ごちそうしてもらおうかな」細谷真大の今季初得点をアシスト
小関裕太と吉柳咲良でミュージカル「ロミオ&ジュリエット」21年以来3年ぶり6度目の上演
エクソーラ、ゲームとゲーム開発の未来に関する四半期インサイト・レポートをリリース。2024年春季のメトリックと今後のトレンドに対する予備分析