NECは量子アニーリングマシンを追求

NECは2018年1月に、量子状態を長く保つための新量子素子、新量子素子間を密に結合し、スケーラブルに拡張可能な量子素子間ネットワークの2つの技術の基本動作の検証に成功したと発表した。

この技術を2023年までに実用化するため、研究員を増員して研究開発を大幅に加速するとのことである。

本質的に量子素子を使うアニーリングの方が最適点を見つける能力が高く、それに加えて高い安定度や結合度が得られれば、先行するD-Waveのものを超えられる可能性がある。しかし、まだ、実用的なチップができていないので、先行きを見守る必要がある。

東芝のシミュレ―テッド分岐アルゴリズム

2019年の4月20日に東芝は、Simulated Bifurcationという新しいアルゴリズムに基づく組み合わせ最適化法を発表した。通常のシミュレーテッドアニーリングでは、強磁性体のスピンのモデルが使われるが、東芝は、最近提案されたKarr-nonlinear parametric oscillatorを使うモデルに基づいている。この非線形発振器を使う場合は、系のエネルギーを表すハミルトニアンの形が違い、近似を使うと計算が簡単で、かつ、安全に並列アップデートができる形に変形できるという。

次の図のA列とB列がペアでA列の一番上がアニーリングの逆温度のようなもので、最初は温度が高く逆数は小さい値からスタートし、徐々に冷却していく様子を示している。B列の図は、上から順に(0,40)、(40,60)、(60,200)の軌跡を示している。B列の一番上の図では初期値である0,0付近にいるが、2番目の図では右上と左下に分岐が生じ、軌跡が左下に来る方が頻繁に起こっている。そして、一番下の図では左下の最適点に落ち込んでいる。

C列とD列ははじめは中程度の温度で、時間100までは一定で、それ以降は温度が下がるという環境での軌跡で、最初の図では4つのミニマムのどれにも近寄る軌跡を描いているが、2番目の図では下の2つの最低点にはほとんど近づかず、右上の最低点にもっとも頻繁に近づいている。そして、下の図では右上の最適点に落ち込んで行っている。

A列とC列の2番目と3番目の図は非線形発振器の複素振幅の実数部と虚数部を示している。

  • アニーリング

    左のA列、B列は逆温度を0からリニアに上げた場合。A列の2番目、3番目が非線形発振器の波形。B列は、x,yの軌跡。中央から始まって、右上と左下の2か所の別れ、右下に収束している。C列、D列は、逆温度が1の状態が時間100まで続き、そこから、上昇する場合。軌跡は、最初は4か所を通るが、2番目では上の2か所になり、最終的には右上に収束している

東芝は、このSBアルゴリズムで2000スピンの最適化を行うチップをFPGAで作り、実際に動作させて他のシステムとの性能の比較を行っている。

次の図の左の図は、2000スピンのMax-Cut問題の最適化でのIsingエネルギーの変化を示す図である。Max-Cut問題は、多数の頂点とそれをつなぐ辺からなるグラフを1本の線で2分した場合に、2分線をまたぐ辺の重みの合計が最大になる分岐を見つける問題である。道路網の通過車両数を最大化するような問題に利用できる。

左から、東芝のSimulated Bifurcation(SB)、国立情報学研究所などが推進するCoherent Ising Machine、高性能なSimulated Annealingのエネルギーの推移を示すグラフであり、太い線が平均値である。そして、右側の3つのヒストグラムは最適化で得られた値の分布を示す。

なお、CIMはこれまでに発表された論文の中では一番速いマシンであり、ここでデータを使っているSAは論文発表されたものの中では速い結果であるが、東芝のSBはそれらより速い結果となっている。

右側の3つのヒストグラムの横軸はMax-Cut値であるので、CIMの答えが32,459、SAの答えが32,314であるのに対して、SBの答えは32,768である。つまり、SBは計算時間が短いだけでなく、より大きなCut値となる分岐を見つけているという優れモノである。

  • アニーリング

    SB、CIM、SAのMax-Cut問題のエネルギーの推移(左上)と解のMax-Cut値のヒストグラム(右の3つの図)。東芝のSBは計算時間が短いだけでなく、他の方法より大きなCut値の解を見つけている

また、東芝は100,000スピンのMAX-Cut問題も解いている。100Kスピンの場合はFPGAではメモリが足りないので、Xeon CPUを使ったクラスタと8GPUのクラスタシステムを使っている。

次の図の上の図は100Kスピンの最適化問題の計算時間をプロットしたもので、赤はSB、青はSAも結果である。そして、〇はPCクラスタのCPUと処理時間、破線は8GPUクラスタの処理時間を示している。下の図は、計算時間に対するIsingエネルギーの変化を示すものである。

CPUのコア数の増加に対する処理時間の減少はSBもSAもその傾向には大きな違いはなく、100コアにして10倍程度の性能向上である。一方、GPUクラスタの場合は、SBの場合は1秒で計算が終わるが、SAでは1000秒掛っており、CPUとGPUでの処理時間の違いが非常に大きい。SBアルゴリズムは並列アップデートが可能であるので、GPUの超多数の並列スレッド処理が有効に働いていることが原因であろうと思われる。

  • アニーリング

    東芝のSBアルゴリズムと従来のSAアルゴリズムの比較。CPUクラスタでの処理ではSBとSAの処理時間はほとんど同じであるが、GPUクラスタの場合は、SBはSAより1000倍速い。複数の線は時間間隔の取り方の違いによる

東芝のSBアルゴリズムは非常に高性能で期待が持てるが、まだ、論文が発表されたばかりであり、どのようなビジネス展開になるのかは、まだ、発表されていない。

ここまでに見てきたように、組み合わせ最適化問題を解くCMOSアニーラは、常温で動作するCMOS回路で実現できる。そして、最適解ではないとしても、実用性の高い精度の解が実用的な計算時間で得られているという点で、実用性が高いと言える。

日本では、コンピュータメーカー各社が実用化に向けてしのぎを削っているが、海外では、D-Wave社が量子アニーラでビジネスを行っており、CMOSアニーラの学術論文もあるものの、CMOSアニーラを手掛けるメーカーの話は聞かない。この違いがどこから来るのか分からないが、CMOSアニーラが日本の強みに育っていけば良いと思う。