2017年末

NTTは、量子ニューラルネットワークという名のコヒーレントイジングマシンを発表した。
光を使った、量子アニーリングマシンの一種で、D-Waveとは違い、絶対零度近くまで冷やす必要もなければ、結合の数に悩む必要もない。

Max-Cut問題だけだが、クラウドで利用することもできて、利用する方法はこちらの記事に詳しい。
https://qiita.com/___monta___/items/9920845d7741e54d2e90

一方で、「これは本当に量子コンピュータなのか?」より具体的には、量子力学の原理を利用して、計算を加速させているのか、という議論も生まれた。
https://togetter.com/li/1173509

2018年6月

衝撃的な論文がarXivに発表された。
https://arxiv.org/abs/1806.08422

量子アニーリングマシンの先駆者であるD-Wave社が、コヒーレントイジングマシンをGPUでシミュレーションできるアルゴリズムを見つけたという。
それも、NVIDIA GeForce GTX 1080 Tiで動かしたところ、NTTの量子ニューラルネットワークよりも30倍高速だったと主張するものであった。
ご存知のとおり、GeForce GTX 1080 Tiは、大規模計算用ではなく、一般用のグラフィックボードだ。ヨドバシカメラでも買えるし、ハイエンドなゲーミングPCに搭載されている。

これをもって「コヒーレントイジングマシンは完全に古典コンピュータだった」といえるのかは、専門家ではない私には分からない。
古典のアニーリングアルゴリズムが存在しているのは周知の事実だし、古典アルゴリズムで解ける問題を古典アルゴリズムで解いたところで、「コヒーレントイジングマシンは量子ではありませんでした」という結論にはならない。ていうか、それを言い出せば、D-Waveのマシンで解ける問題だって、ほとんどは、古典アルゴリズムでも同じくらい効率的に解けるのではないだろうか。
それでも、D-Waveからこのような論文が出てきたのは、注目に値する。

なんと、ソース付き

この論文のarXivの右の方に注目。

なんと、ソースがついてる。arXivにこんな機能あったのか。知らなかった。
ダウンロードしてみると、readmeまで丁寧についてて

The shared library provides a single function with the signature
float gpu_nmfa(int N, float* J,
        std::vector<float> betas,
        int num_samples, int* samples, 
        float noise, float recombination,
        uint32_t seed);
N: problem size

J: pointer to N*N length array, where J[i*N + j] is the weight on the edge between spins i and j. Note that J[i*N + j] should equal J[j*N + i].

betas: std::vector of betas. Two sweeps will be performed at each beta, making the number of sweeps equal to 2*betas.size().

num_samples: the desired number of output samples

noise: the amount of noise (sigma)

recombination: fraction of spin update used to calculate new spin (alpha)

seed: seed for the RNG

とある。あとは、gpu_nmfaを呼び出すラッパーを書けば、使える、ということになる。
(ただし、Attribution-NonCommercial-ShareAlike 4.0 Internationalライセンスのため、商用利用はできないことに注意が必要だ)

また、やってみて分かったんだが。N: problem sizeは、Makefileに書かれている数値と一致していなければならず、コンパイル時に決定される。問題サイズを変えるたびにコンパイルしなおしが必要で、地味にめんどくさい。

やってみよう

https://github.com/gyu-don/cuda_nmfa_release に、コンパイル時のNを取れるようコードを改造したものと、ソルバーとを用意した。

GTX 1080を積んだLinux環境で動作を確認している。CUDAは必須。WindowsやMacで動かせるかどうかはよく知らない。
ソルバーにパラメータを直接埋め込んでいるが、調整しながら試したので、もしかしたら結果は同一にはならないかもしれない。

QNNCloudから問題を拾う

QNNCloudの画面の下の方にある Jij をクリックすると、アニーリングのJijがjsonで手に入る。また、Raw Resultをクリックすると、QNNでの実行結果がjsonで手に入る。
なぜかFirefoxではクリックしても何も起こらない。Chromeならいけるっぽい。

今回、この問題をGPUで解いてみることにする。

問題サイズが100のものと、1000のもの、それぞれ試すことにした。
問題サイズに合わせてMakefileをかえるのを忘れてはいけない。

入力のjsonは、jsonのままC++で読むのがめんどくさかったので、Pythonで、競技プログラミングの入力にありがちな、ベタな出力に変換して使った。
出力はがんばってcout << "["とかなんとかやって、jsonにした。

答えの比較はJupyter Notebookで適当にがんばった。
答えから一番いいカットを選ぶ方法についてはこちらを参考にした。
一番最初に出てくる式を、出てきた答えに当てはめて、最大になっているものが、見つけた中で最もいいカットである。

サイズ100で解いてみたら、パラメータ調整の末、NMFA (GPUで解くアルゴリズム)とCIM (QNNCloudの結果)で答えが一致した。

サイズ1000で解いてみたら、さらなるパラメータ調整の末、NMFAで、CIMより若干よいカットが得られた。(この数値が大きくなるような答えを見つける、という問題なので、数字が大きいほどいい。)
そんなには変わらないので、多分偶然だと思うが、こういうこともある。
1秒程度で終わった。QNNでどれくらい時間かかってるのかは、一般には公開されてないのか、見つけられなかった。

1000だと、答え合わせするのも大変だったので、numpy使ってみた。同じように書く方法が分からなかったので、無駄な計算してるはずなんだけど、それでもやっぱ速い、numpy。

やってみて分かったこと

パラメータ調整がやっぱり大変だったが、手元のGPUで手軽に高速にアニーリングできるのは嬉しい。

$J_{ij}$ の他に、$h_i$ もアニーリングには必要なはずで、そっちは実装されてないっぽい。なんとなく付け足すべきところは想像付くので、気が向いたら追加する。
また、論文中では $\Phi_i$ を正規化するとき、L2ノルムで正規化してるのに、実装はL1ノルムで正規化している。なんで違うのかよく分からない。気が向いたら両方試したいけど、面倒くさい。

ご家庭のゲーミングPCで、コヒーレントイジングマシンより高速なアニーリングを。