アニーリングマシンのプログラミング

前ページでは、一般的なアニーリングマシンがイジング模型のパラメータを入力として受け付けていることを説明しました。ここでは最適化したい問題の定式化が出来た後で、どのようにしてアニーリングマシンに注入するのか概要を説明します。

各アニーリングマシンの比較

2017年11月現在、使用可能または開発が進められているアニーリングマシンを下記にまとめます。

D-Wave
2000Q
日立
CMOSアニーリングマシン
富士通
デジタルアニーラ
NII
コヒーレントイジングマシン
計算方式 量子アニーリング デジタル回路 デジタル回路 レーザネットワーク
ビット数 2048 20480 1024 2048
結合グラフ キメラグラフ キンググラフ(?) 完全グラフ 完全グラフ
全結合換算
ビット数
64 128~(?) 1024 2048

アニーリングマシンのプログラミング

最適化問題を定式化し、それをアニーリングマシン上で実行するには、幾つかの作業が必要になります。これがアニーリングマシンに対するプログラミングになります。これは、マシンがイジング模型を動作モデルとしていることや、ハードウェアの規模に対する制約、結合グラフに対する制約などがあるためです。必要なプログラミング作業の概要を下記にステップごとに説明します。詳細は各リンク先のページで説明します。

株式会社フィックスターズでは、アニーリングマシンに共通する下記ステップの処理の自動化を行っており、様々なマシンで使用可能な共通ライブラリを開発しています。

イジング模型への変換

アニーリングマシンで解きたい組合せ最適化問題がある時、ダイレクトにイジング模型に変換できるような課題であれば良いのですが、一般には最初のステップとして何らかの数式や論理式で表現し、その後イジング模型に変換することになります。つまり、下記のような変換を考えなくてはなりません。
$$
\begin{eqnarray}
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{eqnarray}
$$

詳細ページではどのような指針でこの変換を行うかについて解説を行います。

グラフマッピング

アニーリングマシンによっては、必ずしもイジング変数間の結合が完全グラフで表現されているわけではありません。つまり、イジング模型の相互作用パラメータ \(J_{ij} \ne 0\) となる頂点 \(i,j\) の間がハードウェア的に結合していない場合があるということです。この時、解きたい問題の論理グラフを物理グラフにマッピングする必要があります。上のアニーリングマシン比較表において、結合グラフが「完全グラフ」となっていないマシンが該当します。

詳細ページではこのグラフマッピングの指針について解説します。

必ずしも完全グラフのマシンがアーキテクチャとして優れているというわけではありません。ビット数と結合数はどちらもマシンの規模に寄与するためトレード・オフの関係にあります。解きたい問題によっては完全グラフはオーバースペックということもあります。その場合はビット数が多いマシンのほうが適している可能性が十分にあります。

アニーリングマシンの実行

イジング模型のパラメータリストをマシンに注入し実行します。この部分はベンダー提供のAPIを使用することになります。

結果の解釈

マシンの返してきた答えは通常そのままの形で使用することは出来ません。上記の問題変換とグラフマッピングにおいて、

  • 追加された制約条件を満たしていない解の識別
  • 物理ビットと論理ビットの対応関係を参照

等を確認し、結果を元々の解きたい最適化問題に照らし合わせて適切に解釈します。