爆弾検査問題をもっとやってみた

以前書いた[Blueqatで爆弾検査問題やってみる](https://qiita.com/gyu-don/items/1203c6b784182b69e61c)の続きです。

# 爆弾検査問題とは?

とても敏感な爆弾がある「かもしれない」とします。たった1つの光子でも、当たると爆発する爆弾です。
そんなもん、外乱で既に爆発してるだろうと思うのですが、そういう細かいことは無視します。

たった1つの光子でも爆発する爆弾を、爆発させずにあるかどうかを判定することは非常に難しいです。
何らかの形で光を使って検査することは不可能でしょう。

**そう、古典物理ならね。**

# 前回やったこと

このどうしようもない状況を、量子力学の力を借りて、もしも爆弾があっても

- 50%の確率で、爆弾は爆発してしまう
- 25%の確率で、爆弾があるのかないのか分からない
- 25%の確率で、爆弾を爆発させることなく、爆弾があることが分かる

というところまで、持っていくことができました。

## 詳しい人からの反響も大きかった

爆弾検査問題は量子力学の人たちには大変よく知られている興味深い話なので、詳しい人からの反響も大きく、このように煽られちゃいました。
「あれ? 爆弾検査問題って、実はもっと正解率上げる方法なかったっけ?」

というわけで、今回は、爆弾検査問題の正解率を上げてみます。


# 方法1: Amplitude Amplificationを試す

**この方法は爆弾検査問題には不適です。読み飛ばして[方法2](#%E6%96%B9%E6%B3%952-%E5%85%89%E3%81%AE%E5%81%8F%E5%85%89%E3%82%92%E5%B0%91%E3%81%97%E3%81%A0%E3%81%91%E5%9B%9E%E8%BB%A2%E3%81%95%E3%81%9B%E3%82%8B%E6%96%B9%E6%B3%95%E3%82%92%E3%81%A8%E3%82%8B)からでも読めます**

量子コンピュータで、欲しい状態を効率よく取り出すと言えば、Amplitude Amplificationですよね。
ちょうど最近、[Amplitude Amplificationを解説する分かりやすい記事](https://qiita.com/koke-saka/items/16b20edfeca49e1049cd)も出たことなので、早速やってみます。

前回同様、

- 0量子ビット目: 爆弾検査の結果(1: 爆弾あり, 0: 爆弾なし、または不明)
- 1量子ビット目: 爆弾が爆発したかどうか(1: 爆発した, 0: 爆発しなかった)

とします。

$\mathcal{Q} = -\mathcal{A}S_0\mathcal{A}^{-1}S_\chi$
の、$\mathcal{A}$, $S_0$, $S_\chi$をまず作ります。

$\mathcal{A}$は、爆弾検査そのものです。前回のものを流用しましょう。
$S_0$は|0>にマーキングする回路、$S_\chi$は、欲しい状態、つまり「爆弾は見つかったけど、爆発していない状態」にマーキングする回路です。

$\mathcal{A}$を`a()`, $S_\chi$を`b()`, $S_0$を`s0()`として実装すると、次のようになります。

```py
from blueqat import Circuit, BlueqatGlobalSetting

def a(c, bomb):
  if bomb:
    return c.h[0].cx[0, 1].h[0]
  else:
    return c

def b(c):
  # |10>状態のとき、マーキングしたい。
  # CZは|11>状態のときマーキングするゲートなので、Xゲートで挟むことで実現する
  return c.x[1].cz[0, 1].x[1]

def s0(c):
  # |00>状態のとき、マーキングしたい。
  # CZは|11>状態のときマーキングするゲートなので、Xゲートで挟むことで実現する
  return c.x[0, 1].cz[0, 1].x[0, 1]

BlueqatGlobalSetting.register_macro('a', a)
BlueqatGlobalSetting.register_macro('b', b)
BlueqatGlobalSetting.register_macro('s0', s0)

bomb = False
print('No bomb (Desired: 00)')
print(Circuit().a(bomb).b().a(bomb).s0().a(bomb).m[:].run(shots=100))

bomb = True
print('With bomb (Desired: 10)')
print(Circuit().a(bomb).b().a(bomb).s0().a(bomb).m[:].run(shots=100))
```

これを動かすと:

```
No bomb (Desired: 00)
Counter({'00': 100})
With bomb (Desired: 10)
Counter({'10': 100})
```

元々、爆弾の検出確率が1/2だったので、$1/2 = \sin^2(\theta_a)$の形で書くと、$\theta_a = 30^\circ$です。
m回、$\mathcal{Q}$をかけると、欲しい状態が得られる確率が$\sin^2((2m + 1)\theta_a)$に増幅されるのでした。
今回、$\mathcal{Q}$を1回だけかけたので、m=1で、$\sin^2((2m + 1)\theta_a) = \sin^2((2 + 1)\times 30^\circ) = \sin^2(90^\circ) = 1$となり、確実な結果が得られました。

**Amplitude Amplificationすごい。万歳！**

## ちょっと待て、元の問題を思い出せ

結果自体は完璧です。けれど、これ、爆弾検査問題でした。

$\mathcal{A}$をかけると、光が爆弾に通るので、その時点で爆発している可能性があります。爆発したものを元に戻すような操作はありません。
$S_\chi$や$S_0$で、「爆弾があること」と「爆発したかどうか」との間でCZゲートを使っています。そんな操作、存在するんでしょうか。

Amplitude Amplificationは欲しい状態を高確率で取り出せる強力なアルゴリズムですが、
残念ながら、爆弾検査問題では、Amplitude Amplificationを使うことは難しいでしょう。

# 方法2: 光の偏光を少しだけ回転させる方法をとる

Amplitude Amplificationは使えなかったものの、他にも方法があります。
[こちらのサイト](http://www005.upp.so-net.ne.jp/yoshida_n/qa_a97.htm)で解説されている、光の偏光を少しだけ回転させる方法を、シミュレータに実装していきます。

この実験系では、光の持つ「偏光」という物理量を量子ビットとして使っています。
偏光は「水平」と「垂直」とその重ね合わせからなり、「水平」を|0>, 「垂直」を|1>と置きます。

偏光は回転することができ、水平を垂直に近づけることができます。量子ゲートでいうと、RYゲートに対応します。

ここでも、

- 0量子ビット目: 爆弾検査の結果(1: 爆弾あり, 0: 爆弾なし、または不明)
- 1量子ビット目: 爆弾が爆発したかどうか(1: 爆発した, 0: 爆発しなかった)

とします。

また、偏光は水平と垂直で分けて、異なる光路を通すことができます。
この実験系には、検査に使う0量子ビット目の光が垂直の場合だけ、爆弾の方に光が行く部分があります。
これは、0量子ビット目が|1>のときだけ、爆弾が爆発し1量子ビット目が|1>になるので、CNOTゲートに対応します。

## 実験系
実験系の全容は次のようになります。

![Screenshot_20200303_133323.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88256/274fbc77-eb51-c12d-db67-2678cd1e872a.png)


1. 水平偏光(|0>)の量子ビット0をまず用意します
2. 以下をN回繰り返します
  1. 量子ビット0の偏光をπ/N rad、回転します(RYゲート)
  2. 量子ビット0の垂直成分は、爆弾のある方に行きます。爆弾に当たると爆弾が爆発し、量子ビット1が|1>になります。水平成分は、そのまま何もない方へ行くので、何も起こりません(CNOTゲート)
  3. もし爆発した場合は、その時点で実験終了(失敗)です
3. 量子ビット0を測定し、爆弾検査の結果とします

なぜ、これでいけるのでしょうか。少し考えてみましょう。

### 爆弾がない場合
爆弾がない場合、RY(π/N)ゲートをN回繰り返しているだけです。
結果、|0>だった量子ビット0は|1>になります。

### 爆弾がある場合
爆弾がある場合、RY(π/N)ゲートを通ると回転はするのですが、
もし爆弾のある方の道を通ると、爆発して、その場で実験終了となります。
つまり、爆弾のある方の道を通っていない、ということになりますので、|0>状態だった、ということになります。
爆弾が量子ビット検出器のような役割をしており、実質、測定が行われたと考えた方が分かりやすいかもしれません。

|0>状態にRY(π/N)ゲートをかけて、それを測定して|0>であることを確認する、という操作をN回行っているものと考えられます。

# Blueqatでの実装
これをBlueqatで実装していきます。

しかし、残念ながら、今のBlueqatでは「測定をして、その結果を見て、続きから回路を動かす」ということがデフォルトではできません。
バックエンドを改造して、爆弾をチェックするためのゲートを付け加えます。

## ゲートの追加とバックエンドの改造
各ゲートをどのように解釈するかはバックエンドに依ります。
ゲートの追加自体は簡単ですが、そのゲートをどう動かせばいいか、バックエンドには分かりません。

なので、ゲートの追加に加えて、バックエンドへの実装の追加も行います。

```py:ゲートと実装を追加
from blueqat import Circuit, BlueqatGlobalSetting
from blueqat.backends.numpy_backend import NumPyBackend
from blueqat.gate import Measurement

class BombCheckGate(Measurement):
    lowername = 'bombcheck'

def gate_bombcheck(self, gate, ctx):
    ctx = self.gate_measure(gate, ctx)
    ctx.save_cache=True
    if ctx.cregs[next(gate.target_iter(ctx.n_qubits))] == 1:
        raise ValueError('爆発したよ')
    return ctx

BlueqatGlobalSetting.register_gate('bombcheck', BombCheckGate, allow_overwrite=True)
NumPyBackend.gate_bombcheck = gate_bombcheck
```

実装自体は

1. まず測定
2. 通常は測定後は状態ベクトルをキャッシュしないが、キャッシュするように変更
3. もし測定結果が1だったら、その時点で実験終了(例外を出す)

というものです。

## bombcheckゲートを試してみる

```py
try:
    Circuit().bombcheck[0].run()
except ValueError:
    print('爆発')
else:
    print('セーフ')
```

結果: セーフ

```py
try:
    Circuit().x[0].bombcheck[0].run()
except ValueError:
    print('爆発')
else:
    print('セーフ')
```

結果: 爆発

よさそうですね。

## 実験系を作る

まず、爆弾があるかないかで挙動が変わる部分は、マクロを作ってしまいましょう。

```py:爆弾検査マクロ
def examine(c, bomb):
    if bomb:
        c.cx[0, 1]
    return c.bombcheck[1]

BlueqatGlobalSetting.register_macro('examine', examine, allow_overwrite=True)
```

実験系全体を作っていきます

```py:実験系
from math import pi
from collections import Counter

def experimental(bomb, trial, n):
    """実験を行う
    
    bomb: 爆弾を置くか置かないか
    trial: 実験回数
    n: 各実験ごとに何度か測定を行うが、その測定回数
    """
    delta = pi / n
    result = Counter()
    for i in range(trial):
        c = Circuit()
        for j in range(n):
            c.ry(delta)[0].examine(bomb)
        try:
            result += c.x[0].m[0].run(shots=1)
        except ValueError:
            result['爆発'] += 1
    return result
```

量子ビット0が、爆弾があったら1, なかったら0となるように実験系を組みました。

## 実験結果
さて、結果を見ていきます。

```py:爆弾なしの場合(00が出てほしい)
experimental(False, 100, 50)
```

結果: Counter({'00': 100})
よさそうです。

```py:爆弾ありの場合(10が出てほしい)
experimental(True, 100, 50)
```

結果: Counter({'10': 98, '爆発': 2})
ランダムに変わります。もう一度やってみると
結果: Counter({'10': 97, '爆発': 3})
まずまずな確率。

Nが50だと、高確率でこうなりましたが、Nを小さくすると、爆発確率が上がります。

```py:N=10
experimental(True, 100, 10)
```

結果: Counter({'爆発': 23, '10': 77})
悪くなった!

```py:N=20
experimental(True, 100, 20)
```

結果: Counter({'10': 87, '爆発': 13})
N=10よりはいいが、N=50よりは悪い!

### Nを1〜100までやってみた
```py:1から100までplot
import matplotlib.pyplot as plt

x = list(range(1, 101))
y = [experimental(True, 100, t)['10'] for t in x]

plt.plot(x, y)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88256/d83c8aed-b569-e82e-57a1-0d0a7b02cbdb.png)

このようになりました。

## 理論的には、確率いくつ?

RY(θ)を適用して、|1>が観測される(つまり実験が失敗する)確率は$\sin^2(\theta/2)$です。
$\theta=\pi/N$のとき、この観測をN回行うので、実験失敗となる確率は、ざっくりは、$N\sin^2(\theta/2)$です。(厳密には違いますが、θが小さければ、近似は成り立ちます)

これをプロットすると

```py:理論上の実験成功確率
import numpy as np
x = np.arange(1, 101)
y = 1 - np.sin(np.pi * 0.5 / x) ** 2 * x
plt.plot(x, y)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/88256/d214bc83-d2d1-2f3f-87f9-645a42df931f.png)

となって、先ほどのグラフと概ね一致します。

# まとめ
爆弾検査問題で、爆弾が見つかる確率をもっと高くなるよう頑張ってみました。

最初にやった、Amplitude Amplificationを使った方法は、確かに欲しい状態が増幅され、欲しい結果が得られたのですが、爆弾検査問題という問題設定に合った方法なのか疑問が残りました。

次にやった、少しだけY軸回転をしながら量子ビットを繰り返し観測していく方式でも、欲しい結果を高い確率で得ることができました。
こちらの方法は、爆弾検査問題のための実験系と量子回路とがちゃんと対応しており、先ほどのものよりも実現できる可能性が高いと言えそうです。
また、理論上、どれくらいの確率で爆弾検査に成功するのか検討しました。

今回の「方法2」については、[gist](https://gist.github.com/gyu-don/bd36533d71163a7f155cd4b99c08bb5b)にJupyter Notebookを置いています。