Grover Search③：3-bit Grover Search（補足記事）

# はじめに
複数の選択肢の中から、所望の状態を見つけ出すGroverのアルゴリズム。
下記では、簡単のために2-bitのGrover Searchをあつかってきましたが、
最後に、**3-bitバージョン**もやってみたいと思います。

https://qiita.com/shnchr/items/1bb02f3572eb6854daca

https://qiita.com/shnchr/items/5fa468f1957cc9de4085

また、他の量子コンピュータ関係の他の記事は、下記で紹介しています。

https://qiita.com/shnchr/items/41fa7fd1284d74007a7c

$$
% basic braket 
\newcommand{\bra}[1]{\left\langle #1 \right|}
\newcommand{\ket}[1]{\left| #1 \right\rangle}
\newcommand{\bracket}[2]{\left\langle #1 \middle| #2 \right\rangle}
\newcommand{\ketbra}[2]{\left| #1 \right\rangle \left\langle #2 \right|}
\newcommand{\ketbraket}[3]{\left| #1 \right\rangle \left\langle #2 \middle| #3 \right\rangle}
% small-size
\newcommand{\bras}[1]{\left\langle {\scriptsize #1}  \right|}
\newcommand{\kets}[1]{\left| {\scriptsize #1}  \right\rangle}
\newcommand{\brackets}[2]{\left\langle {\scriptsize #1} \middle| {\scriptsize #2} \right\rangle}
\newcommand{\ketbras}[2]{\left| {\scriptsize #1} \right\rangle \left\langle {\scriptsize #2} \right|}
\newcommand{\ketbrakets}[3]{\left| {\scriptsize #1} \right\rangle \left\langle {\scriptsize #2} \middle| {\scriptsize #3} \right\rangle}
% Matrix
\newcommand{\tate}[2]{\begin{bmatrix} #1 \\ #2 \end{bmatrix}}
\newcommand{\yoko}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}}
\newcommand{\mtrx}[4]{\begin{bmatrix} #1 & #2 \\ #3 & #4 \end{bmatrix}}
$$

# 2bit Groverの構成部品
[2bit Grover Search@Quirk](https://algassert.com/quirk#circuit=%7B%22cols%22:%5B%5B%22H%22,%22H%22%5D,%5B%22Chance2%22%5D,%5B%22%E2%80%A6%22,%22%E2%80%A6%22%5D,%5B%22%E2%80%A2%22,%22Z%22%5D,%5B%22Chance2%22%5D,%5B%22%E2%80%A6%22,%22%E2%80%A6%22%5D,%5B%22H%22,%22H%22%5D,%5B%22X%22,%22X%22%5D,%5B%22%E2%80%A2%22,%22Z%22%5D,%5B%22X%22,%22X%22%5D,%5B%22H%22,%22H%22%5D,%5B%22Chance2%22%5D%5D%7D)は下記のような回路で構成でき、

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/e3e0f755-cb5e-1fad-8f18-531d1b5d124e.png)

構成部品としては、

|Oracle|IAM(Inversion About Mean)|
|:--:|:--:|
|![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/707ffbf4-98c0-3b40-8f20-728ee7a90357.png)|![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/2377a0c1-8c34-f5e5-739a-64366c1f4aef.png)|

でした、では3bitのときは、どう構成すれば良いでしょうか？

# Oracle
要領は2ビットのときと同様です。探索対象の相対位相をマイナスにマーキングすればよいので、
$\ket{111}$が探索対象であれば、下記の様に指定します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/533e61d9-356d-15d1-cb9a-0900fec61e24.png)

# IAM(Inversion About Mean)
こちらも、2bitの時は、

```math
IAM_{2bit} = H^{\otimes{2}}(2\ket{00}\bra{00}-I)H^{\otimes{2}}
```

で、回路としては下記でした。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/2377a0c1-8c34-f5e5-739a-64366c1f4aef.png)

3bitになると同様の要領で、

```math
IAM_{3bit} = H^{\otimes{3}}(2\ket{000}\bra{000}-I)H^{\otimes{3}}
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/cd56106b-dada-1cd1-271c-301876204cc3.png)

となります。

# 動かしてみる
## Grover Operatorを１回適用
上記で構成した、Grover Operatorを１回適用してみます。


* [Grover operatorを１回適用@Quirk](https://algassert.com/quirk#circuit={%22cols%22:[[%22H%22,%22H%22,%22H%22],[%22%E2%80%A6%22,%22%E2%80%A6%22,%22%E2%80%A6%22],[%22Chance3%22],[%22%E2%80%A2%22,%22%E2%80%A2%22,%22Z%22],[%22Chance3%22],[%22H%22,%22H%22,%22H%22],[%22X%22,%22X%22,%22X%22],[%22%E2%80%A2%22,%22%E2%80%A2%22,%22Z%22],[%22X%22,%22X%22,%22X%22],[%22H%22,%22H%22,%22H%22],[%22Chance3%22]],%22init%22:[0,0,0,1,1]})
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/3615017c-c560-d1cb-9498-f8fcefdb0e13.png)

上記ですと、探索の対象である、$\ket{111}$が測定により観測できる確率は、78%です。
ちょっと、物足りないです。
そうです。Grover Operatorの適用回数はデータ数によって変わるので、Operatorの適用回数が足りていません。
なので、足しましょう。

## Grover Operatorを２回適用
Grover Operatorを２回適用してみます。

* [Grover Operatorを２回適用](https://algassert.com/quirk#circuit={%22cols%22:[[%22H%22,%22H%22,%22H%22],[%22%E2%80%A6%22,%22%E2%80%A6%22,%22%E2%80%A6%22],[%22%E2%80%A2%22,%22%E2%80%A2%22,%22Z%22],[%22Chance3%22],[%22H%22,%22H%22,%22H%22],[%22X%22,%22X%22,%22X%22],[%22%E2%80%A2%22,%22%E2%80%A2%22,%22Z%22],[%22X%22,%22X%22,%22X%22],[%22H%22,%22H%22,%22H%22],[%22Chance3%22],[%22%E2%80%A6%22,%22%E2%80%A6%22,%22%E2%80%A6%22],[%22%E2%80%A2%22,%22%E2%80%A2%22,%22Z%22],[%22Chance3%22],[%22H%22,%22H%22,%22H%22],[%22X%22,%22X%22,%22X%22],[%22%E2%80%A2%22,%22%E2%80%A2%22,%22Z%22],[%22X%22,%22X%22,%22X%22],[%22H%22,%22H%22,%22H%22],[%22Chance3%22]],%22init%22:[0,0,0,1,1]})
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/f52aff7a-3ef8-025f-178b-2637b81e12d3.png)

これで、探索の対象である、$\ket{111}$が測定により観測できる確率は、94.5%です。
無事に所望の結果が得られそうです。

で、実を言うと、３回適用する（適用回数過多）だと所望の状態は観測できないのです。
詳細は、下記参照頂きたいですが**いい塩梅が重要**とおぼえておいていただければ幸いです。

https://qiita.com/shnchr/items/ff5d490afb36a64b4967

# まとめ
補足記事として、3-bitのときのGrover Searchを確認しておきました。
これ以上はビット数が増えても同一のやり方を繰返すだけです。
若干、冗長な感じになりましたが、どなたかのお役に立てばと。
何かありましたら、コメント。よろしければ**LTGM**いただけると嬉しいです。

# 関連記事
https://qiita.com/shnchr/items/1bb02f3572eb6854daca

https://qiita.com/shnchr/items/5fa468f1957cc9de4085