ログイン
量子アニーリングマシン 新技術を開発
量子アニーリングマシンで大規模な問題を解法するための技術を開発
発表のポイント
現状のイジングマシンは、ハードウエアの制約により、入力可能な問題規模が制限されていた
本研究では、最適性を失わずに大規模な組み合わせ最適化問題を小さな問題に分割する条件を解明し、さらに、解法可能な問題規模に小さくし繰り返し解法するアルゴリズムを開発した
本技術により、イジングマシンを使った現実世界の組み合わせ最適化問題の活用事例や活用範囲を広げることが期待できる
量子アニーリングマシン※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
（１） これまでの研究で分かっていたこと（科学史的・歴史的な背景など）
現実世界のあらゆるところに存在する組合せ最適化問題※3は大規模になるほど、従来型のコンピュータで最適解を得ることが困難になるため、様々な解法が研究されています。中でも近年、量子アニーリングマシンをはじめとしたイジングマシンと呼ばれる新しいタイプの計算機が注目されています。イジングマシンは組合せ最適化問題の答えを得るのに特化した計算機です。イジングマシンは国内外で研究開発され、一般のユーザーもクラウド上で使用できる段階になっています（図1）。
しかし、イジングマシンを活用するにはまだ課題が多くあります。特に、イジングマシンはハードウエア上の制約で、入力可能な問題規模制限されており、現状のイジングマシンでは大規模な問題を直接解法することは非常に困難でした。既存研究では、発見的な手法※4によって、大規模な問題を小さな問題に分割してイジングマシンで解法していましたが、分割された問題の答えが、元の大規模な問題の答えと一致しているか理論的な条件は未解明のままでした。
（２） 今回の研究で新たに実現しようとしたこと、明らかになったこと
今回の研究では、量子アニーリングマシンをはじめとするイジングマシンに入力可能な問題規模の制限を解決するために、まず、最適性を失わずに大規模な組合せ最適化問題を小さな問題に分割する条件を解明しました。これにより、イジングマシンによって、条件を満足した小さな問題を解法すれば、元の大規模な問題の答えと一致することを証明しました。また、大規模な問題からうまくこのような条件を抽出し、元の大規模な問題を、イジングマシンで解法可能な問題規模まで小さくして、繰り返し解法する新たなアルゴリズムを提案しました。提案したアルゴリズムは、理論的な裏付けのもとに、大規模な問題を小さな問題に分割して解法するため、従来技術に比較して、精度よく元の大規模な問題を解法することが可能となります。
（３） そのために新しく開発した手法
大規模な組合せ最適化問題の一部を抽出して、イジングマシンに入力可能な規模の小さな問題を作り、イジングマシンで解法することを考えます。この際、どのように小さな問題を作るかがポイントとなります。大規模な組合せ最適化問題の答えは複数のビットの集まりによって構成されます。ビットの集まりのうち「解として正しくないビット列」をすべて含むように規模の小さな問題を作り、イジングマシンで解法すれば、「解として正しくないビット列」はすべて「解として正しいビット列」に正しく修正されることが理論的に分かりました。このとき、規模の小さな問題が「正しくないビット列」をすべて含んでいれば、「正しいビット列」が含まれていても構いません。
つまり、ある程度大雑把にすべての「正しくないビット列」を含むように小さな問題を作り、これを繰り返しイジングマシンで解法すれば良いわけです。
そこで、従来の古典計算機を使って、問題の答えの候補を複数個準備します。これら候補は必ずしも正しい答えではありませんが、複数の答えのビット列を見比べて、多くの候補でビット列が一致しているものは「正しいビット列」であり、答えが一致しておらずばらついているものは「正しくないビット列」だと考えることができます。「正しくないビット列」だけを抽出して、実イジングマシンで解法することで、最終的に全体として正しい答えを得ることができます。
実際に、実イジングマシンで解法することができる問題規模に対して、8倍～32倍の大きな問題について、提案手法と従来手法（ランダム手法※5とqbsolv手法※6）とを比較した結果、本手法で得られる答えの精度が高いことが分かりました（図2）。
（４） 研究の波及効果や社会的影響
従来イジングマシンではハードウエア制約によって利用可能なビット数が制限されていたために規模の大きな問題は解くことが困難でしたが、本手法を使うことによってイジングマシンで計算することができます。そのため、量子アニーリングマシンを含むイジングマシンを使った、現実世界の組合せ最適化問題への活用事例を広げることができると考えられます。また、本研究は古典計算機とイジングマシンとを併用して問題を解法する取り組みでもあり、イジングマシンの活用範囲が大幅に広がります。
（５） 今後の課題
本研究では、イジングマシンに入力可能な問題規模の制限を解消することに成功しています。今後は、さらに実世界に見られるさまざまな問題に本手法を適用し、有効性を検証していく必要があります。
（６） 研究者のコメント
本研究ではイジングマシンを活用するために重要なハードウェアの制限を解決する手法を開発しました。イジングマシンを活用した事例は増えつつありますが、本研究で開発した手法を使って、今まで活用できなかった事例が増えることを期待します。
（７） 用語解説
※1 量子アニーリングマシン
組合せ最適化問題を高速に解決すると期待されるマシン。量子効果により量子重ね合わせ状態を実現させ、それを初期状態として用意し、徐々に量子効果を弱める。同時に組合せ最適化問題を表現するイジングモデルの効果を強めることにより、イジングモデルの安定状態を実現させるという機構で動作する。
※2 イジングマシン
組合せ最適化問題をイジングモデルで表現し、組合せ最適化問題を解決するマシンの総称。上記、量子アニーリングマシンはイジングマシンの一種である。
※3 組合せ最適化問題
膨大な選択肢の中から､与えられた制約を満たしつつ、関数の最小値（または最大値）をとる選択肢を求める問題の総称。
※4 発見的な手法
ある問題を解法する手法は、問題の最適解を厳密に算出する手法や、おそらく良さそうと考えられる手続きを組み合わせる手法がある。発見的な手法とは後者の手法を表し、必ずしも元の問題の最適化が得られるとは限らない。
※5 ランダム手法
大規模な問題から、ランダムに小規模の問題を繰り返し抽出し、イジングマシンで解法する手法。
※6 qbsolv手法
D-Wave System社が提供するソフトウェア開発キットに含まれる手法で、発見的な手法に基づき、大規模な問題から小規模の問題を繰り返し抽出し、イジングマシンで解法する手法。
（８） 論文情報
雑誌名：IEEE Transactions on Computers
論文名：Hybrid Annealing Method based on subQUBO Model Extraction with Multiple Solution Instances
執筆者名（所属機関名）：Yuta Atobe（早稲田大学）, Masashi Tawada（早稲田大学）, Nozomu Togawa（早稲田大学） ※ 所属は論文投稿時
掲載日（現地時間）：2021年12月28日
掲載URL：https://ieeexplore.ieee.org/document/9664360
DOI：10.1109/TC.2021.3138629
（９） 研究助成（外部資金による助成を受けた研究実施の場合）
研究費名・研究課題名：国立研究開発法人新エネルギー・産業技術総合開発機構（NEDO）「高効率・高速処理を可能とするＡＩチップ・次世代コンピューティングの技術開発／次世代コンピューティング技術の開発／量子計算及びイジング計算システムの総合型研究開発」
研究代表者名：川畑史郎（産業技術総合研究所新原理コンピューティング研究センター・副研究センター長）
早稲田大学における研究代表者名：理工学術院 教授 戸川望
