疎結合と全結合（後編）
概要
疎結合と全結合（前編）では、イジングモデルのネットワークが概念的な事象の結合と物理的な事象の結合のいずれを表現するかによってその構造が選択されることを取り上げました。後編では、実際にイジングモデルの基底状態を導き出してくれるアニーリングマシンの構造的な仕様や技術上の課題について解説します。
なぜ疎結合のアニーリングマシンがあるのか
Annealing Cloud Webで動いているCMOSアニーリングマシンは疎結合です。また、D-Waveの量子アニーリングマシンも疎結合です。なぜこれらは全結合ではなく疎結合の構造を取っているのでしょうか。前編でも説明したように、数分割問題や時間割問題のような、変数の概念的な結合が生じるために全結合イジングモデルが選択される組合せ最適化問題は、無数に存在します。そのため、アニーリングマシンのすべてのスピン間が結合しているならそのほうがいいに決まっているという声が聞こえてきそうです。
それは入力データ作成でも解説した通り、全結合の相互作用は$O(N^2)$を要求するため、物理的に実装することが困難だからです。もし10個のスピンで全結合の問題を解きたいのであれば、相互作用は1スピンに対して9本、すべて合わせて45本あれば足りますが、アニーリングマシンで解きたいのは大きな問題なのですから10スピンではあまり意味がありません。100個のスピンを全結合にしたい時には、1つのスピンに99本の相互作用を繋げる必要があります。
全結合のアニーリングマシンはどのようにして実現されているのか
全結合のアニーリングマシンも存在しています。NTTとNIIのコヒーレントイジングマシン(CIM)、富士通のデジタルアニーラ(DA)、東芝のSQBM+、Fixstars Amplify Annealing Engine (AE) 、そして日立が2019年に発表したMomentum Annealing (MA)版CMOSアニーリングが全結合です。
全結合のマシンはどうやって実現できるのでしょうか。全結合のマシンの多くはソフトウェアで実装されています。ASICなどの疎結合マシンのように相互作用をハードウェアで物理的に接続するのではなく、仮想的につながっているスピン間の相互作用を再現しています。一般的に、ソフトウェアによるアプローチはハードウェアを使うより計算時間がかかりますが、複雑なつながりを実装することが可能です。日立のMA版CMOSアニーリングでは、計算の並列度を上げることによって、極力速く処理可能となるアルゴリズムを採用しています。
2種類のCMOSアニーリングの特徴
Annealing Cloud Webで実行できるASIC版CMOSアニーリングマシンと、前述のMA版CMOSアニーリングの利用上の特徴を見てみましょう。
ASIC版は半導体CMOS上にKing's graphのイジングモデルを実装した疎結合のマシンです。最新型のマシンは、はがきより少し大きなサイズのASICボードを縦・横にケーブルで接続するだけで大きく拡張できるようになっています。拡張しやすく低電力で動作すること、最適解導出までの処理時間の速さに特長があります。
現在、2.25Mビットを入力できる大規模ハードを日立製作所研究開発グループの協創の森に設置し、信号制御最適化による渋滞解消システムのデモを公開し64本×64本の格子状の道路からなる交差点全体をその場で最適化することができます。この大規模ハードでは全結合が必要な問題はこのまま解くことができませんが、信号制御のように疎結合のイジングモデルで表現できる問題であれば入力できるスピン数に制限は無いと考えられます。実際には、この2.25Mビット大規模ハードのフルスペックで実行すれば1500本×1500本の道路網で信号最適化処理が可能です。
一方、MA版CMOSアニーリングでは、先に述べたように全結合問題を解けることが最大の強みであり、勤務シフト最適化や金融ポートフォリオ最適化に適用され、ASIC版よりも先に実用化に至っています。※1, ※2
グラフ埋め込みアルゴリズム
疎結合のアニーリングマシンで、全結合の問題を解こうとする取り組みも存在します。その1つが「グラフ埋め込みアルゴリズム」※3です。
グラフ理論では、イジングモデルのスピンを「頂点」、また相互作用を「辺」と表現します。
グラフ埋め込みを説明した下の図を見てください。左側が、全結合のイジングモデルですね。これをグラフ埋め込みした結果が右側の図です。
スピン番号①は、全結合のイジングモデルでは1つですが、他の全てのスピンと結合するために、右図のように8個に分割（複製）しています。これにより、他の全てのスピンとの結合を疎結合のグラフで表現できるというわけです。
このように、頂点を分割することで、複雑な形のグラフ構造を疎結合のグラフ構造に置き換えることをグラフ埋め込みと呼びます。グラフ埋め込みをすることで、ハード上で隣り合わせにできなかった頂点同士をつなげ、疎結合の構造を持ったマシンでも、全結合の構造を持った問題を扱うことができるようになるのです。
埋め込みを有効に活用するには、まだまだ問題点がいくつか残されています。1つ目の問題は、分割する頂点の数を極力抑える必要がある点です。これは、分割によって多くの頂点を使ってしまうと、有限であるアニーリングマシンのスピンを消費してしまうため、埋め込み前の実際に解ける問題の規模を小さくせざるを得なくなるためです。2つ目の問題は、埋め込みアルゴリズムを用いた場合、どの頂点を分割するかという計算や、増えた頂点に関連する入力データを作るための計算の量が増えてしまうことです。アニーリングマシンを用いることにより最適解を求める時間そのものは極めて短くなりますが、以上に挙げた理由によって前処理に時間がかかってしまうため、合計の処理時間としては長くなってしまう可能性があります。
こういった課題を解決するために、研究者や技術者によって、グラフ理論を駆使してハードウェアの制約を突破しようという様々なアイディアや手法が検討されています。次の一手を打つのは、あなたかもしれません。
まとめ
- ASIC版CMOSアニーリングマシンでは物理的な接続で相互作用を実装しており、接続する数に限りがあるが、計算速度が高速である。
- 全結合イジングモデルを解くアニーリングマシンの多くは、ソフトウェアにより仮想的に相互作用を実装している。
- 疎結合のマシンに全結合のイジングモデルを入力するために考案された埋め込みアルゴリズムには、いくつかの課題があり、それらを突破する発想や手法が求められる。
