制約をもつ組合せ最適化問題をイジング計算機で効率的かつ高精度に解くための新たな手法を開発

変数の個数を削減し性能向上、ソフトウェアへの応用に期待

発表のポイント

イジング計算機で現実世界の組合せ最適化問題を解くためには、最適化問題に含まれる多くの制約群を効率的に取り扱う必要がある。

本研究では、線形制約をイジング計算機で取り扱うための新しい手法として、組合せ最適化問題の記述に必要な変数の個数を削減し、イジング計算機の性能を改善する手法を構築した。

本手法を取り込んだイジング計算機ソフトウェアの開発により、高精度に現実世界の組合せ最適化問題を解くことが期待できる。

量子アニーリング計算機^※1をはじめとするイジング計算機^※2を現実世界の組合せ最適化問題^※3に活用するためには、組合せ最適化問題がもつ制約を効率的に取り扱うことが重要となります。この問題に対して、早稲田大学理工学術院講師の白井達彦（しらい たつひこ）氏、同大学理工学術院教授の戸川望（とがわ のぞむ）氏らの研究グループは、線形制約^※4をもつ組合せ最適化問題を、イジング計算機で効率的に解くための新しい手法（以下、本手法とする）を開発しました（図１）。この手法は、制約を用いて束縛スピンを自由スピンで表現することにより、自由スピンのみで組合せ最適化問題を記述するもので、本研究グループは、本手法を量子アニーリング計算機等のイジング計算機に適用し、既存イジング計算機でその有効性を確認しました。

本研究成果は、米国の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あるいは-1の二値をとる。）を変数にもつイジングモデルに変換する必要があります。ハードウェア制約により、現状のイジング計算機に入力可能なスピンの個数が制限されるため、組合せ最適化問題を少ないスピンの個数で効率的にイジングモデルに定式化することが重要となります。制約をもつ組合せ最適化問題をイジングモデルに定式化する手法として、これまでペナルティ法^※6が用いられていました。しかし、ペナルティ法では十分なスピン数の削減を達成できてはいませんでした。

（２）今回の研究で新たに実現しようとしたこと、明らかになったこと

今回の研究では、連立一次方程式を解く一般的な手法である変数消去法のアイデアに基づいて、制約をもつ組合せ最適化問題をより少ない変数で記述する手法を構築しました。

まず、線形制約を利用することで、自由スピンと束縛スピンとに分離することを考えます。束縛スピンは、自由スピンの線形関数によって与えられます。たとえば、図1は、4個の頂点をもつグラフを2個の頂点をもつ2個のグラフに分割する問題です。各頂点について1個のスピンを対応させます。すると4個のスピンが必要となります。4個のスピンのうち、2個は赤丸（+1）、2個は青丸（-1）とする必要があります。これが制約です。ところが4個のスピンすべてを必ずしも独立に扱う必要はありません。4個のスピンのうち、任意の3個を自由スピン、1個を束縛スピンとします。すると、３個の自由スピンのうち１個が赤丸（+1）のとき束縛スピンは赤丸（+1）、一方で２個が赤丸（+1）のとき束縛スピンは青丸（-1）となることがわかります。自由スピンの値から自動的に束縛スピンの値が決まることになります。つまり、1個の束縛スピンを用いずに3個の自由スピンだけを用いて「3個の自由スピンのうち１個か２個を赤丸（+1）にせよ」という問題に置き換えることができます。本来4個のスピンが必要であった問題を、3個のスピンで記述できたことになります。

この考えを使い、我々は束縛スピンを用いずに、自由スピンのみを用いてもともとの組合せ最適化問題を記述できることを明らかにしました。上記のように組合せ最適化問題を自由スピンのみを用いて記述しているため、従来手法であるペナルティ法と比較して、必要なスピンの個数を削減することができます。自由スピンを変数とするイジングモデルを与えることによって、既存のイジング計算機に本手法を導入することができます。

 （３）そのために新しく開発した手法

本手法を用いて線形制約をもつ組合せ最適化問題をイジング計算機で解法することを考えます。さきほどの例では、4個のスピンのうち任意の1個を束縛スピンとしましたが、実際の線形制約の場合には、束縛スピンを任意に選択することはできません。つまり、どのスピンを束縛スピンあるいは自由スピンとして選択するかがポイントとなります。

そこで、束縛スピンを選択するための条件を理論的に明らかにしました。この条件が満たされるとき、本手法によって組合せ最適化問題の解の最適性が保たれることを理論的に証明しました。さらに本研究では、多数の線形制約をもつ組合せ最適化問題を、本手法で記述するためのアルゴリズムを提案しました。このアルゴリズムを用いることで、現実世界に現れるほぼすべての線形制約つき組合せ最適化問題に対して、本手法を適用することができます。とくに典型的な制約をもつ組合せ最適化問題に対して、具体的なイジングモデルの一般形を与えました。

（４）従来手法との比較

工場と地点が同じ個数与えられたとき、各工場を各地点に割り当てたときの地点間の輸送コストの合計を最小化する組合せ最適化問題である「二次割当問題」は、これまでイジング計算機で解法することが困難とされてきました。この二次割当問題に対して、本手法を組み込んだ場合と組み込まなかった場合（ペナルティ法）とを比較しました。その結果、必要なスピン数を削減しつつ、平均して残留エネルギー^※7を19%削減し、本手法の有効性が確認できました（図2）。

（５）研究の波及効果や社会的影響

本手法を使うことによって、必要最小限の変数の個数で組合せ最適化問題を解くことが可能になるため、イジング計算機を実利用する際に、変数の個数を削減し、また制約をもつ組合せ最適化問題を解法しやすい形式で解くことができます。本手法は既存のイジング計算機に簡単に導入することができることから、本手法を組み込んだソフトウェアの開発によって、イジング計算機で線形制約を取り扱う手法のスタンダードとなることが期待されます。

（６）今後の課題

イジング計算機は現在活発にハードウェアの性能向上が図られています。しかし、現状では利用可能なスピン数が限られているために、扱うことのできる組合せ最適化問題のサイズが限定されています。本研究は、イジング計算機が扱う問題のサイズを拡大するための有力な手法の一つですが、今後はさらに、実世界に見られる様々な問題に対し適用し、本手法の有効性を検証していく必要があります。

（７）研究者のコメント

本研究で開発した手法を使うことで、今後イジング計算機の性能がさらに改善し、新たにイジング計算機を活用できる事例が増えることを期待します。

 （８）用語解説

※1　量子アニーリング計算機

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

※2　イジング計算機

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

※3　組合せ最適化問題

膨大な選択肢の中から､与えられた制約を満たしつつ、関数の最小値（または最大値）をとる選択肢を求める問題の総称。制約とは守らなければならないルールをさす。

※4　線形制約

※5　グラフ分割問題

与えられたグラフの頂点集合を２個の部分集合に分割する問題。それぞれの部分集合に含まれる頂点の個数を等しくするという制約の下、異なる部分集合の間を繋ぐ辺の数を最小にする組合せ最適化問題。

※6　ペナルティ法

制約つき最適化問題を制約なし最適化問題に変換する一つの方法。

※7　残留エネルギー

イジング計算機で組合せ最適化問題を解いた際に得られた解の精度を評価する指標の一つ。得られた解の目的関数の値と真の最適解の目的関数の値の差で与えられ、値が小さいほど解の精度が良いことを表す。

 （９）論文情報

雑誌名：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

（10）研究助成（外部資金による助成を受けた研究実施の場合）

研究費名・研究課題名：科学技術振興機構（ＪＳＴ） 戦略的創造研究推進事業 ＣＲＥＳＴ「地理空間情報を自在に操るイジング計算機の新展開」（JPMJCR19K4）
研究代表者名：戸川望（早稲田大学・教授）
早稲田大学における研究代表者名：理工学術院　教授　戸川望

研究費名・研究課題名：基盤研究(C)「量子古典ハイブリッド計算技術による物質シミュレーション高速化手法の研究」
研究代表者名：田中宗（慶應義塾大学・准教授）
早稲田大学における研究代表者名：理工学術院　講師　白井達彦