── 組合せ最適化問題は、どのようにして解を求めていくのでしょうか。

この組合せ最適化問題では、パラメータがn個あれば、2のn乗個の解が存在します。どのパラメータの組合せが最適解なのか、システムの最適な数値を縦軸に取ると図2のようになります。巡回セールスマン問題では巡回経路の距離が縦軸に、組合せのパターンの種類が横軸になります。この中の最小値が最適パラメータとなります。もしパラメータの数が100個あれば2の100乗もの組合せが存在することになります。大変な数です。

[図2] 組合せ最適化問題は与えられた条件で最適解を求める問題
提供：株式会社日立製作所研究開発グループ

この問題の答えを求めるために量子アニーリングマシンをカナダのD-Wave Systems社が開発しました。これは超電導素子を使って量子状態を実現するわけですが、絶対零度近くまで冷やす必要があります。計算速度は最も速いと言われていますが、冷却による使いづらさなどの課題が残ります。また、スケーラビリティという点では、超電導素子の規模を大きくしていくことはまだ難しいと思います。

そこで、当社が提案しているのはCMOSアニーリングマシンと言いまして、従来のCMOS半導体技術を使ってデジタル的に計算することで量子アニーリングマシンと似たような演算をすることを考えました。この方法だと計算時間に関しては、量子アニーリングマシンよりは遅くなりますが、冷却する必要はありません。また拡張性もあります。使いやすさという点では有利です。つまり規模の大きな計算に有利なので、拡張性のあるような用途を狙っていこうと思います。

── アニーリングマシンの原理を教えてください。

その原理は、ドイツの物理学者エルンスト・イジング（Ernst Ising）の名前に由来しており、「イジングモデル」と言います。図3のように磁性体のスピンを用いて説明されます。上向きのスピンを赤で、下向きのスピンを青で表示しています。磁性体が持つそれぞれのスピンの分布の状態を表しており、イジングモデル自体が持つエネルギーが最小になる点を安定な最適状態とみなします。イジングモデルでは、エネルギーが最小になるように収束していくと考えています。その状態を表すと右側のグラフになります。

[図3] イジングモデルとは
提供：株式会社日立製作所研究開発グループ

組合せ最適化問題では、このイジングモデルにマッピングして、最小点がわかったら、それを元の最適化問題に戻すことで、解を求めます。ただ、当社はイジングモデルを磁石で表現するのではなく、CMOS半導体で再現しました。スピンの上向き、下向きをSRAMメモリ^*4の1、0に対応させました。これがCMOSアニーリングです。

── CMOSを使ったのはなぜですか。

将来的に性能を上げること考えると、おそらく量子コンピュータになるのでしょうが、今すぐに使うのであればCMOSの方が有利になります。また、携帯電話への搭載など、いろいろな応用で使えることもCMOSを選んだ理由です。使いやすさを考えると、やはり半導体で実現するのがよいと思います。半導体には、これまで積み重ねてきた実績と経験があるからです。

── CMOSでは具体的にどのように実行するのですか。

エネルギーが低い状態へ遷移する様子をデジタル回路で表現しています。図4の系のエネルギーが最も大きな状態では、右上の図のようにすべてのスピンが同じ向きに向いているとします。そのエネルギーの高い状態から低い状態へと値を徐々に更新していくわけですが、途中で局所最適値に落ち込まないように、ランダムに全く異なる値になるように揺さぶってまたエネルギーの低い方向に向かうように計算します。そして最終的になるべくエネルギーの小さな点に来ると、そこが実用解^*5となるわけです。

[図4] CMOSアニーリング技術とは
提供：株式会社日立製作所研究開発グループ

ここで、実用解と言っているのは、ランダム性を使っているので、必ずしも最小値に収束するとは限らないためです。だから実用解と呼んでいます。

これまでに20,480個のスピンに対応したCMOSコンピュータチップを試作しています。そして、これを使って同じ組合せ最適化問題を解く時間を比較してみました。すると、最適化問題を解いた時のエネルギー効率は、従来のCPUを使って解いた場合と比べて1800倍高かったのです。特に、問題の規模が小さい――例えば8個のスピンしかない場合は、せいぜい4倍程度にしか効率は上がらなかったのですが、規模が大きくなるにつれてエネルギー効率は高くなり、スピンの数が20,480個だと1800倍まで高まりました。

── ここでのエネルギー効率とは何を定義していますか。

この定義は、同じ精度の解が求められるまでに消費した電力の比較です。比較対象のCPUは、パソコンに入っている代表的なCPUとしてCore i5を1.87GHzで動作させ、10W/コアでプログラムを実行しました。このCPUのエネルギー効率を1としています。