100,000スピン コヒーレントイジングマシン について

# NTTの発表

先日 2021年9月30日にNTTからプレス発表がありました。
とっくに切り捨てたのかと思っていたCIM（旧QNN）が10万ビットになって帰ってきた！

https://group.ntt/jp/newsrelease/2021/09/30/210930a.html

すごい。

以前は上記プレスの図中にある「高速行列演算回路」がFPGAだけどかなり苦しいのではないかという話がありましたが、よりビット数を増やして実現してきたということですね。

# 評価内容の確認

図２に計算時間の評価があります。

10万ノード全結合グラフの最大カット問題の解探索におけるカット値の時間変化を見ており
基準値となる貪欲法の値に到達するまでの時間を「CPU上で実装したSAでは0.7秒であったのに対し、CIMでは600 マイクロ秒」であり1000倍速いとしています。

すごい。

# 疑問点

「図3．解精度の評価。」をみると、 SA 0.5秒、SA 1.0秒と比較しているが、SAの処理時間が短すぎませんか？

また、「SAでは得ることが困難な特徴的な解分布を得た」としていますが、10万ビット級では個人マシンで確認できませんが、ヒストグラム幅のカット数でも異なる解が大量にありそうなので、ここはSAのほうが明らかに良さそうです。
SAで1秒処理した際は1,100周辺に解が集まっていますが、おそらく様々な解が出ていることでしょう。

質が悪い解がたくさん出て幅広い解が求められているという説明はあまり誠実な説明に感じません。


# 疑問点の検証

## Greedyアルゴリズム実装

Greedyなアルゴリズムというのがどのような実装かわかりませんが、最初に思いついた簡単な実装で試しています。
なお、マシンのスペックと実装の手軽さから2000Bitで試しています。

問題作成時間：6.2秒
Greedy処理時間：8.4秒
カット数：-46170


```python:Greedyアルゴリズム
import networkx as nx
import numpy as np
import random
from itertools import combinations,product

#Create Problem
n = 2000
m = n*n
g = nx.gnm_random_graph(n,m)
for u,v in combinations(g.nodes(),2):
    g.edges[(v,u)]['J'] = g.edges[(u,v)]['J'] = 1 - random.randint(0,1)*2

#Solve by Greedy Algorithm
for v in g.nodes():
    tmp = 0
    for i in range(v):
        tmp += g.nodes[i]['val'] * g.edges[(i,v)]['J']
        tmp += g.nodes[i]['val'] * g.edges[(v,i)]['J']
    
    if tmp > 0:
        g.nodes[v]['val'] = -1
    else:
        g.nodes[v]['val'] = 1

#show result
greedy_result = 0
for u,v in combinations(g.nodes(),2):
    greedy_result += g.edges[(v,u)]['J'] * g.nodes[u]['val'] * g.nodes[v]['val']

print(greedy_result)
```

## SA実装

Cなどで独自実装しないと全然速度でないんでしょうけど、手抜きのためにD-Wave OceanSDKのnealでやります。

前処理：32秒
サンプリング(SA処理100回)：19秒 *1回あたり0.2秒
カット数：-46006.0


```python:SAアルゴリズム
import neal
from pyqubo import Array

#前処理
x_sa = Array.create('x',shape=(n),vartype='SPIN')

H = sum(x_sa[u] * x_sa[v]* g.edges[(u,v)]['J'] for u,v in combinations(g.nodes(),2))
model = H.compile()
h,J,offset = model.to_ising()
sampler = neal.SimulatedAnnealingSampler()

#サンプリング
sampleset = sampler.sample_ising(h,J,num_sweeps=2,num_reads=100)

#結果出力
sa_result = 0
sample_dict = sampleset.first.sample
for u,v in combinations(g.nodes(),2):
    u_val = sample_dict[f"x[{u}]"]
    v_val = sample_dict[f"x[{v}]"]
    sa_result += g.edges[(u,v)]['J'] * u_val * v_val

print(sa_result+offset)
```

ちなみに、解のレベルを基準に似せるためにSweepを2としていますが、Sweepを増やすことで解の質を上げることができます。
なお、SweepとはSAを実行する際の内部でのループ回数で、デフォルトは1000です。（なので、かなりレベルを落としている）

```python:変更例
sampleset = sampler.sample_ising(h,J,num_sweeps=10,num_reads=100)

```

Sweep数とCut数の変化

|  | 2 | 10 | 100 |
|:-:|:-:|:-:|:-:|
|処理時間 |  0.19秒 | 0.20秒  |  0.57秒 |
|CUT数| -46006 | -43600  |  -66600  |
|解の多様性*1| 100 | -100 |  -100 |

*1 解の多様性=100は100回実施して100回とも異なる解が出ていることを示します。

最後のSweep数100の際のヒストグラムは以下になります。

![SnapCrab_NoName_2021-10-4_0-28-32_No-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/121950/c838604a-4a53-b580-854e-6baeabe7a61d.png)


# 比較結果
良い点からいうとCIMはかなり早いことがわかります。SAはCPU処理である以上、サブセカンド以上に時間を短くすることは難しいので、超高速な処理を求められる場合はアドバンテージがありそうです。

逆に言うと、そうでない場合は解の質があまりよくないことが欠点のようです。SAは時間を延ばすことで解の質を上げることができます。CIMが時間を延ばすことで解の質を上げることができるか不明です（おそらく無理でしょう）。

興味深い技術であり、非常に短時間でソコソコの解が求められるような状況においては、他にない特徴と入れると思われます。