全3055文字

東芝はシミュレーテッドアニーリング(SA)を独自のアプローチで解く「シミュレーテッド分岐(SB)」アルゴリズムを開発。それまで難しいと考えられていた演算の全並列化を初めて実現した。最近では解をデジタルの値にする制約や量子力学的な効果も導入し、求解の速度と精度を大幅に向上させた。

 日本のメーカーの間で巻き起こったイジングマシン開発競争にやや遅れて参戦したのが東芝だ。ただ、同社の求解手法である「シミュレーテッド分岐(SB)」は、それまでのSAとはやや異なっている。運動方程式を解くのである。

 イジングモデルで使われる目的関数であるハミルトニアンHには時間のパラメーターが陽には(目に見える形では)入っていないことが多い。ただ、イジングモデルは本来、物理学のモデルで、そのHには2つの解き方が以前から知られている。1つは、時間のパラメーターを使わず、エネルギーEの値を決めてHx)=Eを満たす変数xを求める解き方。Eが基底状態E0であるとき、その解は組合せ最適化問題の解にもなる。

 もう1つは、Hを基に時間のパラメーターを導入し、微分方程式(運動方程式)に書き換えて仮想的な“粒子”の軌道を追う解き方だ。これはちょうど、地球など星の周囲を回る人工衛星の軌道を予測するのに似ている。

 それまでのSAのほとんどがHのままで求解していたのに対し、東芝はSBで運動方程式を解く手法を選んだ。理由の1つは、運動方程式にすることで全結合でも全並列化処理ができるようになるからだ。

 詳細は不明だが、現在と一歩先の未来のスピンの関係を使うことで全結合モデルかつ全並列化処理を実現した東京工業大学 本村研究室のSCAと共通する背景があるかもしれない。

最適解の近くに“解”が集まる

 この手法を採用する理由はまだある。運動方程式を解くことで、多数の仮想粒子の軌道を並列的に求めると、大域最適解の近くに粒子が見つかる確率が高くなるのである(図13)。これは、「エルゴード仮説」と呼ばれているもので、厳密な証明こそされていないが、力学系と呼ばれる物理学の分野では非常によく知られており、実験的にはそれが正しいことが確認されている注4)

図13 東芝は運動方程式を解いて求解
図13 東芝は運動方程式を解いて求解
東芝のシミュレーテッド分岐(SB)技術の概要。東芝は目的関数Hを基に、そのポテンシャルの中を運動する“粒子”の運動方程式を解くことで、大域最適解を見つけるアプローチを採った。メリットの1つは、従来のSAでは原理的に難しかった全並列化が可能になる点。さらに、エネルギーを下げるタイミングを調整することで、局所解に捕まりにくくなるメリットもあるとする(a、b)。(図:日経クロステック)
[画像のクリックで拡大表示]
注4)これは直感的には、ジェットコースターの車両のスピードの変化に近い。ジェットコースターの線路の高い部分では車両のスピードは非常に遅いが、低い部分では車両が位置エネルギーを運動エネルギーに変換することで走行速度が速くなる。仮に、線路上に多数の車両があるとして、互いに衝突もしないと仮定すると、車両の密度は線路の最も高い部分が高くなり、スピードの速い最も低い部分は密度が低くなる。

 東芝はこの性質を利用することで、エネルギーを大きくは下げずに、つまり基底状態を敢えて探しに行かずに高いエネルギーのままで大域最適解がある領域に当たりをつける方法を採る。これによって、他のイジングマシンの多くで使う乱数を使わずに、局所解に捕まる可能性を減らすわけだ。

 ただし、求解の最後の段階ではエネルギーを比較的速く下げ、大域最適解を高い確率で“収穫”する。

4方向で大幅な性能向上を実現

 もっとも、東芝はこの技術で満足せず、その後も技術革新を進めている。最近になってやや細かくみると4方向、大きくみると3つの方向性で大幅な改善を実現した。具体的には、(1a)FPGAと専用入出力インターフェースを使って超低遅延の実装を実現、(1b)そのFPGAボードを多数接続して大規模な全結合問題を解かせても求解速度が飽和しないスケールアウト技術を開発、(2)アナログマシンだった当初のSBマシン(断熱的SBMまたはaSBM)に、デジタル的な解が得られる制約を加えることで収束を大幅に早めた、(3)ポテンシャルの壁を電子などが透過する量子力学の「トンネル効果」を模した効果を導入して、解の精度を大幅に高めた、の4方向(または3方向)である。