前ページでは、一般的なアニーリングマシンがイジング模型のパラメータを入力として受け付けていることを説明しました。ここでは最適化したい問題の定式化が出来た後で、どのようにしてアニーリングマシンに注入するのか概要を説明します。
各アニーリングマシンの比較 #
2022年5月現在、使用可能または開発が進められているアニーリングマシンを下記にまとめます。
|
Fixstars Amplify AE |
D-Wave 2000Q/ Advantage |
日立 CMOS Annealing |
富士通 Digital Annealer |
東芝 SQBM+ |
|
|---|---|---|---|---|---|
| 装置型式 | GPU | 量子回路 | デジタル回路 | デジタル回路 | GPU |
| 最大ビット数 | 262,144以上 |
2,048 (16x16x8)/ 5,760 (16x15x24) |
61,952 (352x176) |
8,192 (DA2)/ 100,000 (DA3) |
100,000 (SQBM+)/ 10,000 (SBM PoC版) |
| 係数パラメータ |
デジタル (32/64bit) |
アナログ (5bit程度) |
デジタル (3bit) |
デジタル (16/64 bit) |
デジタル (32bit) |
| 結合グラフ | 全結合 |
キメラグラフ/ ペガサスグラフ |
キンググラフ | 全結合 | 全結合 |
| 全結合換算ビット数 | 131,072 | 64/124 | 176 |
8,192 (DA2)/ 100,000 (DA3) |
31,000程度(SQBM+)(*1)/ 1,000 (SBM PoC版) |
| APIエンドポイント | Fixstars Amplify | D-Wave Leap |
Annealing Cloud Web |
DA Cloud | AWS |
※ 東芝SQBM+製品版の仕様については東芝シミュレーテッド分岐マシン(SQBM+)公式サイトまでお問い合わせをお願いいたします。
(*1) SQBM+の公式サイトにある記述 (相互作用を表す非ゼロ係数は10億個まで) より試算したもの
アニーリングマシンのプログラミング #
最適化問題を定式化し、それをアニーリングマシン上で実行するには、幾つかの作業が必要になります。これがアニーリングマシンに対するプログラミングになります。これは、マシンがイジング模型を動作モデルとしていることや、ハードウェアの規模に対する制約、結合グラフに対する制約などがあるためです。必要なプログラミング作業の概要を下記にステップごとに説明します。詳細は各リンク先のページで説明します。
株式会社フィックスターズでは、アニーリングマシンに共通する下記ステップの処理の自動化を行っており、様々なマシンで使用可能な共通ライブラリを開発しています。
イジング模型への変換 #
アニーリングマシンで解きたい組合せ最適化問題がある時、ダイレクトにイジング模型に変換できるような課題であれば良いのですが、一般には最初のステップとして何らかの数式や論理式で表現し、その後イジング模型に変換することになります。つまり、下記のような変換を考えなくてはなりません。
\[ \begin{aligned} E\left( \mathbf{X} \right) = \sum_{i}{C_i \left( \mathbf{X} \right)} \quad & \rightarrow & \quad H \left( \mathbf{\sigma} \right) = \sum_{ i \ne j}{J_{ij}\sigma_i \sigma_j} + \sum_i{h_i \sigma_i}\\ \mathbf{X} = \left( x_0, x_1, \cdots , x_n \right) \quad & \rightarrow & \quad \mathbf{\sigma} = \left( \sigma_0, \sigma_1, \cdots , \sigma_{n'} \right) \end{aligned} \]詳細ページではどのような指針でこの変換を行うかについて解説を行います。
グラフマッピング #
アニーリングマシンによっては、必ずしもイジング変数間の結合が完全グラフで表現されているわけではありません。つまり、イジング模型の相互作用パラメータ \(J_{ij} \ne 0\) となる頂点 \(i,j\) の間がハードウェア的に結合していない場合があるということです。この時、解きたい問題の論理グラフを物理グラフにマッピングする必要があります。上のアニーリングマシン比較表において、結合グラフが「完全グラフ」となっていないマシンが該当します。
詳細ページではこのグラフマッピングの指針について解説します。
必ずしも完全グラフのマシンがアーキテクチャとして優れているというわけではありません。ビット数と結合数はどちらもマシンの規模に寄与するためトレード・オフの関係にあります。解きたい問題によっては完全グラフはオーバースペックということもあります。その場合はビット数が多いマシンのほうが適している可能性が十分にあります。
アニーリングマシンの実行 #
イジング模型のパラメータリストをマシンに注入し実行します。この部分はベンダー提供のAPIを使用することになります。
結果の解釈 #
マシンの返してきた答えは通常そのままの形で使用することは出来ません。上記の問題変換とグラフマッピングにおいて、
- 追加された制約条件を満たしていない解の識別
- 物理ビットと論理ビットの対応関係を参照
等を確認し、結果を元々の解きたい最適化問題に照らし合わせて適切に解釈します。