3. CIMの実力
CIMの実力を示した2つの論文は、共にScienceの同じ号に掲載されて世界にアピールされました。論文のタイトルは「A fully-programmable 100-spin coherent Ising machine with all-to-all connections（完全にプログラム可能な100スピン全結合のコヒーレントイジングマシン）」と「A coherent Ising machine for 2000-node optimization problems（2000ノード最適化問題に対するコヒーレントイジングマシン）」で、1つ目はNIIとStanford大のグループから、2つ目はNTTのグループが中心となって開発したCIMについての内容です。ここでは1つ目の論文を「100spin」論文、2つ目の論文を「2000spin」論文と呼んで区別します。
100spin論文の結論
本論文では、光ファイバー測定型CIMの比較的規模の小さい問題に対する性能評価が行われています。330mの光ファイバーループに160パルスを生成して、そのうち100パルスを使って計算を行います。解くべき問題は、Cubicグラフと呼ばれるすべての頂点が3つの結合を持っているグラフにおけるMAX-CUT問題[2]です。MAX-CUT問題はイジングモデルの基底状態を求める問題と等価であることが知られており、規模の小さい問題については厳密解が知られているため、これを用いてCIMの性能を評価しています。得られた結果の概要は以下の通り。
- 実験的に、光パルスが60周する100usほどで問題が解けることが分かった。
- 16スピンのCubicグラフの問題では、20％以上の確率で厳密解が得られることが分かった。
- 問題サイズ（スピン数）が増加すると解の精度（厳密解が得られる確率）は低下し、100スピンのメビウスラダーと呼ばれる問題では、20％の確率で厳密解を得た。
2000spin論文の結論
本論文は、実用をめざし、古典コンピュータでの計算が困難な2000スピンの問題に対する性能評価を行っています。厳密解が知られていない問題であるため、解の精度保証がされているアルゴリズム（GW-SDP）およびシミュレーテッドアニーリング（SA）と比較されています。光ファイバーループの長さは1kmで、5082パルスを発生させて、そのうち2000パルスを使用して計算を行っています。得られた結果の概要は以下の通り。
- 厳密解が知られていない2000スピン問題で、ランダムグラフ、スケールフリーグラフ、完全グラフの3種のグラフに対し、5msの時間内にGW-SDPの解精度を上回る良い近似解を得ることを確認。
- ただし、ランダムグラフ、スケールフリーグラフでは、SAの方が高精度な解が得られており、完全グラフでのみCIMの方がSAよりも高精度な解が得られた。約20～50倍の高速化を確認。
以上2つの論文の結果から、CIMの実力を考察します。まず、この方式で実用的な時間でちゃんと問題が解けることは確かのようです。そして、「古典コンピュータと比較して優位か」については、まだまだ原理検証の段階のようです。問題サイズの増加に伴って解精度が低下するという結果から、古典コンピュータでは解けないサイズの問題の厳密解を求めることはまだまだ難しそうです。しかし、厳密解でなく近似解であれば、古典コンピュータよりも精度の高い解が得られる場合があるため、実用上有用であると言えそうです。
ただし、アプリケーションに依るため、CIMの能力を発揮できるアプリケーションを探すことが重要です。特に、完全グラフのような結合が密な問題に強いということが分かります。また、計算時間が5ms程度であるため、何度もトライして一番良い解を取り出すという使い方をすることにより、解精度を高めることができます。
今回の論文ではMAX-CUT問題を解いていますが、ほかにも適用可能な問題が数多くあると思われます。今後は、さまざまな問題を解くことによって、CIMのアプリケーションを探索していくことが重要でしょう。
[2] MAX-CUT問題（最大カット問題）
重み付きグラフのノードを2つのグループに分割するとき、グループ分けをした際にカットされるエッジの重みWの総和を最大化する組み合わせを求める問題（Wikipedia「カット（グラフ理論）」）。
上図では、ノードをS1とS2に2つのグループに分割するとき、カットされるエッジの重みの総和をカットバリューC(σ)として表している。このカットバリューを最大にするエッジの組み合わせを求める問題がMAX-CUT問題である。カットバリューの式を変形するとイジングハミルトニアンが出てくる。カットバリューを最大にするためには、イジングハミルトニアンを最小にすればよいので、イジングモデルの基底状態を求める問題と等価である。このとき、ノードはスピンに、エッジは相互作用に対応する。
