量子アニーリングって何？

社内勉強会で発表した資料です。

---

# おわび

- 量子コンピュータについては素人です
- 業務では扱っておりません
- 正確な情報は末尾の参考文献をご覧ください
- 教えて！詳しい人！

---

# 最近の量子コンピュータ

- 商用量子コンピュータD-Wave
- 無料体験サービズが続々
  - IBMが量子コンピュータの無料体験を提供
  - Microsoftがシミュレータと言語（Q#）を提供
  - 日本発の量子コンピュータも最近発表

ちょっと調べてみました。

---

# 量子コンピュータって何？

- 「5量子ビットが限界」
- 「『15=3×5』 を解くのがやっと」
- D-Waveは128量子ビット（！）
- D-Waveは本当に量子コンピュータ？

---

# そもそも、コンピュータは２種類ある

- **アナログコンピュータ**
  - 物理現象をそのまま利用
  - 特定の問題だけを解ける
  - 日時計や計算尺
- **デジタルコンピュータ**
  - 物理現象を抽象化して利用
  - あらゆる問題を解ける

歴史的には、アナログ → デジタルの順に発展

---

- 量子アナログコンピュータ
  - 量子アニーリング（D-Wave）
  - QNN
- 量子デジタルコンピュータ
  - 量子ゲート

量子コンピュータも、アナログ → デジタルの順に発展？

---

# 量子ゲート方式

すみません。勉強できていません。

キーワード:

- 重ね合わせ
- 複素ベクトル空間
- ユニタリ行列
- ショアのアルゴリズム

---

# D-Wave と量子アニーリング

---

# D-Wave と「量子アニーリング」の関係

- 「量子アニーリング」は元々はアルゴリズム名
  - 組み合わせ最適化問題を解く
  - 「焼きなまし法」などの仲間
  - 古典コンピュータで実行可能
- D-Wave は「量子アニーリング」を実機で実行
  - 「磁場内における平面的スピングラス問題」を解く

---

# 磁場内における平面的スピングラス問題

> `G = (V,E)` を平面的グラフ（辺が交差しないグラフ）とする。
>
> 各頂点 `v` には スピン `S_v = -1 or 1` を割り当てられる。
> 
> この時、エネルギー Hが最小になるような、`S_v` の割り当て方を求めよ（Hの最小値を求めよ）。
> 
```math
H = \Sigma_{(u, v) \in E} S_u S_v + \Sigma_{v \in V} S_v
```

---

![スピングラスのイメージ.png](https://qiita-image-store.s3.amazonaws.com/0/179154/8a6ae0a8-0c50-6013-68aa-d70bf314ce65.png)

---

スピングラス問題はNP困難
→ 多くの現実の問題が、スピングラス問題に翻訳できる。

```
解きたいNP問題
 ↓
 ↓　古典コンピュータで問題を翻訳（多項式時間）
 ↓
スピングラス問題
 ↓
 ↓ D-Waveで解）
 ↓
スピングラス問題の解答
 ↓
 ↓  古典コンピュータで解答を翻訳（多項式時間）
 ↓
解きたいNO問題の解答
```

---

# 現実の問題を解くには、ノウハウが必要

* 「翻訳」に時間がかかるかも
* 「翻訳」ると、ビット数が大きくなりすぎるかも
* キメラグラフ問題
  * ハードウェア上では、全ビット同士がつながっているわけではない
  * D-Waveは一部のスピングラス問題しか解けない

---

# 無料体験サービスが続々

---

# IBM

- 「The IBM Quantum Experience」
  - 無料
  - 量子ゲート方式のシミュレータ
  - 量子コンピュータの実物をクラウドで利用（5量子ビット）
- なお、IBMは数年以内に商用利用可能な汎用量子コンピューティング・システムを構築する計画

---

![Screenshot-2017-12-10 IBM Q experience(3).png](https://qiita-image-store.s3.amazonaws.com/0/179154/e09eda4a-2499-6efe-e76d-4e2f79d6ce4a.png)

回路にゲートを配置

---

![Screenshot-2017-12-10 IBM Q experience(4).png](https://qiita-image-store.s3.amazonaws.com/0/179154/822f4119-4953-701c-3792-06eed8e17c8f.png)

DSLでも入力可能（左側の黒い部分）

---

![Screenshot-2017-12-10 IBM Q experience(2).png](https://qiita-image-store.s3.amazonaws.com/0/179154/2ca5645b-25a4-8a99-43e4-da73e10217ec.png)

実行結果を表示

---

# Microsoft

- https://www.microsoft.com/en-us/quantum/development-kit
- 「トポロジカル量子コンピュータ」という量子ゲート方式を開発中

---

# 量子ニューラルネットワーク計算機 (QNN)

組み合わせ最適化問題の一種「最大カット問題」（NP完全）を解ける。らしい

![image.png](https://qiita-image-store.s3.amazonaws.com/0/179154/6f6e3b62-15ed-91c0-f04f-f1c5446a6760.png)

---

https://qnncloud.com/index-jp.html

> 量子ニューラルネットワーク(QNN)の研究・開発は、山本喜久ImPACTプログラムマネージャーが率いてきたNII・Stanford大学の研究チームを中心に、 最先端研究開発支援プログラム(FIRST)やImPACTの国家プロジェクトの支援を受け、日本電信電話会社(NTT)、NII、東京大学、大阪大学、東北大学、東京理科大学が行っています。

---

![image.png](https://qiita-image-store.s3.amazonaws.com/0/179154/af7028dc-a8b7-b5ab-d5a1-9f7d5c003005.png)

---

![image.png](https://qiita-image-store.s3.amazonaws.com/0/179154/2b199663-c20a-7335-11a8-5dd8cc680ec9.png)

---

# 読んだ本

(2016)量子コンピュータが人工知能を加速する 西森秀稔、大関真之

一般向け。D-Waveなどを解説。

<!--
![image.png](https://qiita-image-store.s3.amazonaws.com/0/179154/ed55ad6b-9832-be58-90ee-3cb0e87374c9.png)
-->

<img src=https://qiita-image-store.s3.amazonaws.com/0/179154/ed55ad6b-9832-be58-90ee-3cb0e87374c9.png height=300 />

---

(2015)量子計算 (ナチュラルコンピューティング・シリーズ) 西野 哲朗,‎ 三原 孝志,‎ 岡本 龍明

量子ゲート・量子アニーリングを解説

<!--
![image.png](https://qiita-image-store.s3.amazonaws.com/0/179154/94201b50-f8dc-4452-eefc-8a66c52cea45.png)
-->

<img src=https://qiita-image-store.s3.amazonaws.com/0/179154/94201b50-f8dc-4452-eefc-8a66c52cea45.png height=300px/>

---

(2009) マーミン 量子コンピュータ科学の基礎 N. David Mermin,‎ 木村 元 (翻訳) 

量子ゲートを解説

<!--
![image.png](https://qiita-image-store.s3.amazonaws.com/0/179154/e65dbf20-169b-ad09-8fd9-9684f23295c6.png)
-->

<img src=https://qiita-image-store.s3.amazonaws.com/0/179154/e65dbf20-169b-ad09-8fd9-9684f23295c6.png height=300px />

---

# 各種無料体験サービス

- IBM
  - https://www.ibm.com/developerworks/jp/cloud/library/cl-quantum-computing/index.html
- MS
  - https://www.microsoft.com/en-us/quantum/development-kit
- QNN
  - https://qnncloud.com/index-jp.html