可能な限り簡単にPythonベースで量子アニーリングで最適化問題をとく

## なに？

量子コンピュータとかヨクワカラナイし、イジングモデルとかよくわからない、数式もΣとか苦手、でもPythonなら読める。

数式よりもソースコードの方が直感的で何といっても動かして理解できるので「量子コンピュータ」の１方式である「量子アニーリング」のお勉強をPythonでしてみるのもいいかな、と、メモとしてまとめました。

## 量子コンピュータと量子アニーリング

「量子コンピュータ」と言うとそこそこ広い範囲の言葉で色々なものをさします。

そんな「量子コンピュータ」と呼ばれるものの１つに「量子アニーリング」と言われる方式があります。

ざっくり言うと「量子アニーリング」は「組み合わせ問題」を解くものです。今のパソコンに取って代わるようなものではなくシンプルに組み合わせ問題を解けるだけのものです。

組み合わせ問題といってもパッとこないかもしれませんが、たくさんの物の中からBetterな組み合わせを選ぶタイプの問題です。世の中意外とそういう問題は多くて、、、お洋服を選んだり、最適な交通経路を選んだり、300円で駄菓子を選んだり、意外とよくあるタイプの問題です。

今のコンピュータも十分に高速とは言え、数が多い組み合わせの問題を解くのには時間がかかってしまいます。「量子アニーリング」はその組み合わせ問題をより効率的に解ける可能性がある技術です。

・・・ということで前置き長くなりましたがさっそくソースコードでいきます。

## 環境準備

まずPythonが動く環境を用意してください。
pip で必要なライブラリをインストールします。

```bash
pip install pyqubo
```

さくっと簡単なサンプルを作ってみます。

```python
from pyqubo import Binary, solve_qubo

# 今あるスキマ時間
sukima_jikan = 45

a = Binary("アニメ")          # 30分
b = Binary("おもしろ動画 A")   # 5分
c = Binary("おもしろ動画 B")   # 4分
d = Binary("おもしろ動画 C")   # 3分
e = Binary("ドラマ")          # 60分

H = (sukima_jikan - a*30 - b*5 - c*4 - d*3 - e*60)**2

qubo, offset = H.compile().to_qubo()
solution = solve_qubo(qubo)
print(solution)

# 実行結果：
# {'おもしろ動画 A': 1, 'おもしろ動画 B': 1, 'おもしろ動画 C': 1, 'アニメ': 1, 'ドラマ': 0}
```


今回の例題は、「**表のような5つの動画**」があって、今スキマ時間としてぽっかり「**45分**」時間があいたとします。その時にどういう組み合わせの動画を見ればスキマ時間を過ごせるか？という問題です。

| 変数 | 動画   | 時間 |
|---|-------|------|
| a | アニメ | 30分 |
| b | おもしろ動画 A | 5分 |
| c | おもしろ動画 B | 4分 |
| d | おもしろ動画 C | 3分 |
| e | ドラマ | 60分 |

それでは順番にコードを説明していきます。

まず各動画を表す変数を準備します。
`Binary` とは `0` または `1` になってくれる型です。

```python
a = Binary("アニメ")
b = Binary("おもしろ動画 A")
c = Binary("おもしろ動画 B")
d = Binary("おもしろ動画 C")
e = Binary("ドラマ")
```

そして次に、いわゆる評価関数みたいなものを作ります。

```python
H = (sukima_jikan - a*30 - b*5 - c*4 - d*3 - e*60)**2
```

この評価関数 `H` の値が**最小**になるように `a` `b` `c` `d` `e` の組み合わせをイイ感じに考えようと思います。

式 `H` の意味について説明します。

- `a` `b` `c` `d` `e` は `Binary` で `0` または `1` の値になってくれる。 
- その `Binary` の意味を 「**1は動画を見る**」「**0は動画は見ない**」とする。
- 「『**スキマ時間**』から『**見る動画の時間**』を引いた数」が小さくなるほど高評価とします（つまりヒマな時間つぶせる方を良しとする）
- 小さい方がいいとはいえマイナス、つまり、スキマ時間以上に動画を見られた場合に高評価になっても困るので**二乗**することでマイナスをかき消す

では実際の例を見てみます。

例えば、「スキマ時間 45分」で「変数 a のアニメ」だけを見る場合、変数 `a` が `1` になって他は `0` になるので、`H=225` になります。

```python
H = (sukima_jikan - a*30 - b*5 - c*4 - d*3 - e*60)**2
  ↓
H = ( 45 - 1*30 - 0*5 - 0*4 - 0*3 - 0*60 )**2
  = ( 45 - 30 - 0 - 0 - 0 - 0 )**2
  = ( 15 )**2
  = 225
```

別のパターンで、「変数 b のおもしろ動画」と「変数 c のおもしろ動画」を見る場合、変数 `b` `c` が `1` になって他は `0` なるので、`H=1296` になります。

```python
H = (sukima_jikan - a*30 - b*5 - c*4 - d*3 - e*60)**2
  ↓
H = ( 45 - 0*30 - 1*5 - 1*4 - 0*3 - 0*60 )**2
  = ( 45 - 0 - 5 - 4 - 0 - 0)**2
  = ( 36 )**2
  = 1296
```

つまり、「変数 b のおもしろ動画 ＋ 変数 c のおもしろ動画」の `H=1296` より「変数 a のアニメ」の `H=225` の方が `H` が小さいので高い評価＝時間をつぶせた、と言えます。

という感じで、`a` `b` `c` `d` `e` の組み合わせと `H` の値を見ていくとこんな感じになります。

| a | b | c | d | e | H    |
|---|---|---|---|---|-----:|
| 0 | 0 | 0 | 0 | 0 | 2025 |
| 1 | 0 | 0 | 0 | 0 |  225 |
| 0 | 1 | 0 | 0 | 0 | 1600 |
| 0 | 0 | 1 | 0 | 0 | 1681 |
| 0 | 0 | 0 | 1 | 0 | 1764 |
| 0 | 0 | 0 | 0 | 1 |  225 |
| 1 | 1 | 0 | 0 | 0 |  100 |
| 1 | 0 | 1 | 0 | 0 |  121 |
| 1 | 0 | 0 | 1 | 0 |  144 |
| : | : | : | : | : |  :   |
| 1 | 1 | 1 | 1 | 0 |   9  |
| : | : | : | : | : |  :   |
| 1 | 1 | 1 | 1 | 1 | 3249 |
| : | : | : | : | : |  :   |


という感じでこの中から一番 `H` が小さい組み合わせを選びたいのですが、普通なら１つ１つ解いていくしかありません。

これをなんとなくイイ感じに解いてくれている部分がここです。

```python
H = (sukima_jikan - a*30 - b*5 - c*4 - d*3 - e*60)**2
qubo, offset = H.compile().to_qubo()
solution = solve_qubo(qubo)
print(solution)
```

評価式 `H` （本当は評価式ではなくハミルトニアンと呼びます）を作って、それを元に QUBO というものを作って（`to_qubo()`）、それを解く（`solve_qubo()`）ことで解を得ています。 このハミルトニアン（≒評価式）から解となる組み合わせを「量子」の特性を借りて選び出すのが「量子アニーリング」と言われるものです。

ということで実行して見ると答えとして以下が得られます。

```python
{'おもしろ動画 A': 1, 'おもしろ動画 B': 1, 'おもしろ動画 C': 1, 'アニメ': 1, 'ドラマ': 0}
```

つまり、45分のスキマ時間があったら、

| 変数 | 動画   | 時間 | 視聴 |
|---|-------|------|----|
| a | アニメ | 30分 | 見る |
| b | おもしろ動画 A | 5分 | 見る |
| c | おもしろ動画 B | 4分 | 見る |
| d | おもしろ動画 C | 3分 | 見る |
| e | ドラマ | 60分 | 見ない |

**30分 + 5分 + 4分 + 3分** の **合計42分** 見ると良いという組み合わせが得られます。

めでたしめでたし

まとめると、細かいことは抜きにして解きたい問題に対して `H` の式を作れるかが大事ってことです。

### この後にやること

例えば、スキマ時間を変えてみる、動画の数を増やしてみる、とかして色々試すと面白いです。 他にも、動画に★の数とかつけてなるべくたくさん★の高い動画を見れるようにする（そんな H の評価式を作る）とかもおススメです。


## まとめ

あれ？ 自分のパソコンは「量子コンピュータ」だっけ？ なんでこのコード動いたの？ と思ったかもしれませんが、今回使わせていただいた `PyQUBO` はシミュレータが入っているので普通のPCでも動いてくれます（感謝！）。もしD-WAVEやなんとかアニーラみたいな本物の量子アニーリングマシン（とか量子ではないけど高速なアニーリングマシン）を使える方がいたら上のコードの `solve_qubo` あたりを差し替えることで実際の量子アニーリングも実行できます。

本来はイジングモデルやQUBOとかハミルトンとかきちんと説明しないといけないのでしょうが、、、私のようなプログラマ/エンジニアのとっかかりとしては「プログラム」で理解できる方が早いのでPythonベースでまとめてみました。

識者からのツッコミ大歓迎ですのでコメント欄でぜひ何卒です。