制約をもつ組合せ最適化問題をイジング計算機で効率的かつ高精度に解くための新たな手法を開発
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
miwa「34歳に見えない!かわいい!」最新ショット 15日が誕生日
女子プロレスラー井上貴子、元櫻坂46の1期生が親戚だと明かす「似てる」「姉妹みたい」
カブス今永昇太が7勝目 7回4安打1失点好投 鈴木誠也は3打数2安打
浅田舞「知的でセクシー」メガネ姿の鏡越し自撮りショット&「見返り美人」な振り返る姿披露
元櫻坂のフジ原田葵アナが同局アナ5人で制服ショット 元日向坂齊藤京子との1枚も公開
高橋克典、型破りなサラリーマンから特命係長経て「大岡越前」 時代劇と向き合い新しい発見も
大谷翔平「2番DH」で今季9勝右腕ルーゴと対戦 山本由伸は7勝目を目指し先発
川島海荷「ママになってもパワフル」 第1子出産の團遥香と2ショット
モデルmegbaby「気付いたらお尻出てたり」初写真集に笑顔「美しく見えればなんでもOK」
AI、人気歌姫とのコラボに「まさかこんな日が来るなんて…」感激 「最高ー」「奇跡」フォロワーも反応
何があった!?「エアコン」が想定外の壊れ具合!投稿者に話を聞いた
玉置浩二の妻、青田典子(53)の現在がとんでもない事になっていると話題に
三上悠亜、整形したことを事後報告でネット騒然「素っぴんが美しすぎる」「大半を既にいじっておいて今更」
柏原崇(45)現在を調べてみた結果、相変わらずかっこよすぎた!
「愛が生まれた日」藤谷美和子(56)の現在がヤバい!?徘徊生活を送っていた過去も明らかに。
ユーチューバーもこう氏、元彼女・成海瑠奈について赤裸々告白
ガーシーが綾野剛のLINE公開でネット騒然「ショック」「すごいエンタメ」
オードリー若林結婚で嫁の名前がソッコーで特定する動き始まる
矢口真里、中学時代の写真公開「やっぱアイドルな人は、違うわ」ネット騒然
【ネタバレ?】史実で見るキングダムの今後の展開まとめ〜中華統一までの全体像
何があった!?「エアコン」が想定外の壊れ具合!投稿者に話を聞いた
玉置浩二の妻、青田典子(53)の現在がとんでもない事になっていると話題に
柏原崇(45)現在を調べてみた結果、相変わらずかっこよすぎた!
三上悠亜、整形したことを事後報告でネット騒然「素っぴんが美しすぎる」「大半を既にいじっておいて今更」
ユーチューバーもこう氏、元彼女・成海瑠奈について赤裸々告白
YouTuberジュキヤの動画企画が大炎上「普通に痴漢」「気持ち悪すぎ」
「愛が生まれた日」藤谷美和子(56)の現在がヤバい!?徘徊生活を送っていた過去も明らかに。
ガーシーが綾野剛のLINE公開でネット騒然「ショック」「すごいエンタメ」
オードリー若林結婚で嫁の名前がソッコーで特定する動き始まる
岡本夏生(56)、1600日ぶりにブログを更新した現在が衝撃
miwa「34歳に見えない!かわいい!」最新ショット 15日が誕生日
女子プロレスラー井上貴子、元櫻坂46の1期生が親戚だと明かす「似てる」「姉妹みたい」
カブス今永昇太が7勝目 7回4安打1失点好投 鈴木誠也は3打数2安打
浅田舞「知的でセクシー」メガネ姿の鏡越し自撮りショット&「見返り美人」な振り返る姿披露
元櫻坂のフジ原田葵アナが同局アナ5人で制服ショット 元日向坂齊藤京子との1枚も公開
高橋克典、型破りなサラリーマンから特命係長経て「大岡越前」 時代劇と向き合い新しい発見も
大谷翔平「2番DH」で今季9勝右腕ルーゴと対戦 山本由伸は7勝目を目指し先発
川島海荷「ママになってもパワフル」 第1子出産の團遥香と2ショット
モデルmegbaby「気付いたらお尻出てたり」初写真集に笑顔「美しく見えればなんでもOK」
AI、人気歌姫とのコラボに「まさかこんな日が来るなんて…」感激 「最高ー」「奇跡」フォロワーも反応