次世代計算機講座＜実践編＞ ～アニーリングマシンプログラミング～ 参加記

# はじめに
2018年10月12日（金）に開催された次世代計算機講座＜実践編＞～アニーリングマシンプログラミング～に参加してきました。

↓「次世代計算機講座」開催案内ページ
https://www.ipa.go.jp/jinzai/mitou/event/next-computer-seminar.html

# プログラム
前日までに公開されていた講座のプログラムは下記のとおりです。
当日のプログラムのタイトルは若干異なりましたが、ほぼ同じテーマで実施しました。

- 講座内容
-　アニーリングマシンによる計算の概要
    - 通常の計算との違い
    - 最適化問題の具体例
    - マシンへの埋込に関する一般論
- プログラミング実習
    - D-Wave
    - Digital Annealer（富士通）
    - CMOSアニーリングマシン（日立製作所）
- アプリケーションデモ
    - サンプルプログラムの紹介

講座の解説者は株式会社フィックスターズの松田佳希さんです。
それぞれ簡単にどんな内容だったか説明します。

### アニーリングマシンによる計算の概要
スライドを使用した座学を実施しました。アニーリングマシンとは何かということから始まり、組み合わせ問題・充足可能性問題がどのようにイジングモデルで表現されるのかといった解説が中心でした。

すべての組み合わせ最適化問題はイジングモデルで表現可能であることがわかっており、アニーリングマシンの汎用性を担保しているとのことです。

Q. すべての最適化問題は無限個のスピンの問題を含みますか
A. 古典コンピュータと同じで有限個のスピンの問題のみになります

量子コンピュータと（シミュレーテッド）アニーリングマシンの比較は下記のとおりです。
講座の情報を掲載したいところですが、公開情報からわかるものとさせていただきます。（引用元：[アニーリングマシンのプログラミング](https://quantum.fixstars.com/introduction_to_quantum_computer/quantum_annealing/programming/)、結合定数は[こちら](https://www.ipa.go.jp/files/000067333.pdf)から引用、ただしD-Waveのみ[こちら](https://docs.dwavesys.com/docs/latest/_downloads/09-1109A-M_Technical_Description_of_DW_QPU.pdf)）

||D-Wave2000Q |日立CMOS|富士通デジタルアニーラ|
|:-----------------|------------------:|:------------------:|:------------------:|
|ビット数|2048|20480|1024|
|結合グラフ|キメラ|キング|全結合|
|全結合換算|64|128以上|1024|
|結合定数|アナログ(float double)|3ビット(符号付整数: -3～+3)|16ビット(符号付き整数：-32768～+32767)|

日立のCMOSアニーリングは[ASIC版](https://annealing-cloud.com/about/cmos-annealing-machine.html)であれば、1回のアニーリングで61,952スピン(352×176のKing's Graphに相当)を処理可能なようです。

単純な量子ビット（この記事ではアニーリングマシンでも量子ビットと呼ばせてもらいます）の数ではなく、全結合換算した数が計算できる量の目安になります。
したがって現時点では富士通のマシンが一番計算できそうです。
日立は、全結合換算はD-Waveより多いものの、結合定数が3ビットしかありません。これだと結合定数が計算したい量に本質的に効いてくる計算はできないような気がします。。。
D-Waveは量子コンピュータなので、一番ベターな解を計算できると考えられます。ハンズオンで富士通のマシンと比較した際には、D-Waveのほうがベターな解を見つけられていたような気がします（時間がなくきちんとした比較はできませんでした）。


次に、後の実装のために最適化問題のコスト関数をイジング・QUBO変数でどのように表すのかについて、1~4bit程度の簡単な例について紙で計算して理解を深めました。

計算した内容が正しいか、[Annealing Cloud Web](https://annealing-cloud.com/index.html)を使用して確かめました。

[Annealing Cloud Web](https://annealing-cloud.com/index.html)は日立製作所、産業技術総合研究所、理化学研究所、情報・システム研究機構、早稲田大学の共同で行っているNEDOプロジェクトの成果物です（運用は株式会社フィックスターズ）。

このサイトでは[イジングエディタ](https://annealing-cloud.com/play/ising-editor.html)というGUIを通して、日立のCMOSアニーリングマシンでアニーリング実験をすることができます。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/211712/d14991ca-2d5d-6a9c-8403-628720efda59.png)

このサイトはソフトウェアのシミュレータではなく、CMOSの実機(シミュレーティッドアニーリング)です。Webアプリは株式会社フィックスターズ製です。
アニーリング回数は1シミュレーションの繰り返し回数で、温度は無次元化されたパラメータです。

グラフ上の各ノードがスピンを表しており、リンク部分が相互作用を表しています。各ノードにかかる外部磁場の強さをノードに、各スピン間の相互作用の強さをリンクに設定します。実行ボタンを押すと計算結果が表示されます。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/211712/e750c65b-be1e-304e-32ee-75761f024141.png)
![image.png](https://qiita-image-store.s3.amazonaws.com/0/211712/851e9592-d445-641b-66ee-7bfeaac58d5f.png)

↓現在、こちらのアプリはAPIも用意されているようです。
https://annealing-cloud.com/web-api/reference.html


### プログラミング実習
ハンズオンはjupyter notebookを使用して実施し、言語はpythonです。

量子コンピュータで計算を実現するには次のような手順を踏みます。（[詳細はこちら](https://quantum.fixstars.com/introduction_to_quantum_computer/quantum_annealing/programming/)）

1. 最適化問題など解きたい問題をイジングモデルに変換する
2. イジングモデルをマシン上に実装されているグラフのイジングモデルに変換する（[詳細はこちら](https://quantum.fixstars.com/introduction_to_quantum_computer/quantum_annealing/programming/graph_mapping/)）
3. マシンで計算を実行する
4. 結果を解釈する

このうち、2の変換部分はフィックスターズさんのミドルウェアによって自動で行われるため、1のみが実習対象でした。

1の部分では最適化問題をイジングモデルに変換するための変数の使い方や制約式の実現方法などを学びました。
3の部分はD-VAVEの量子コンピュータを使用しました。


Q. パラメータ最適化までミドルウェアで自動化されますか。
A. 日立はパラメータ最適化まで作り込まれておりません。富士通は今回は全自動モードを使用します。


### アプリケーションデモ
スケジューリング問題と巡回セールス問題についてD-Wave 2000Qと富士通のFujitsu DAを用いて計算しました。

巡回セールスマン問題は下記のように解かれます。（画像は参加当時のものではなく、[フィックスターズさんのサイト](https://quantum.fixstars.com/introduction_to_quantum_computer/applications/tsp/)から引用）

![image.png](https://qiita-image-store.s3.amazonaws.com/0/211712/0b5eaf99-2d92-33e1-1f9e-138f59c93fe8.png)

# おわりに
このような貴重な講座に参加する機会をいただき、関係者皆様には御礼申し上げます。
抽選で落ちてしまった方々や、今後量子コンピュータの理解を深めたい方々のためにも、このような機会が増えると嬉しいですね。

### その他アニーリングマシンの参考になるページ

- [株式会社フィックスターズ, 『Quantum Computer Information Site』](https://quantum.fixstars.com/)
- [NEDO, 『交通や物流の経路を最適に︕　組合せ最適化問題を高速に解くコンピュータ』](https://www.nedo.go.jp/content/100869664.pdf)
- [富士通, 『Digital Annealer』](http://www.fujitsu.com/jp/digitalannealer/)
- [富士通, 『デジタルアニーラご紹介資料』](http://www.fujitsu.com/jp/documents/digitalannealer/services/da-shoukai_06212018.pdf)
- [infocomsニューズレター, 量子コンピュータとその周辺～いつ使えるのか？どう使えば良いのか？](https://www.icr.co.jp/newsletter/wtr349-20180427-onodera.html)
- [『イジングモデル』](http://theochem.chem.okayama-u.ac.jp/wiki/wiki.cgi/exp11?page=%A5%A4%A5%B8%A5%F3%A5%B0%A5%E2%A5%C7%A5%EB)