「いい塩梅」が重要なGrover Search

# この記事について
Grover Searchのアルゴリズムでは、、
Grover Operatorを、データ数Nに対して$\sqrt{N}$回適用することで所望の状態を得てデータ検索が実現できる事がわかっています。この背景で、

* データ数Nに対して、$O(\sqrt{N})$のオペレータ適用でデータ検索ができる！
* 古典の線形サーチ$O(N)$よりも効率的な探索ができる！

といった説明となるのですが、、
Grover Operatorの適用回数が$\sqrt{N}$回よりも、**大きく**ても**小さく**ても、所望の状態を得られない。が実際であり事実であると理解しています。

つまり、**いい塩梅**が重要となります。

このいい**塩梅がデータ数Nに対し$\sqrt{N}$回**という点がわかりやすいように、実験的な記事を作ってみました。

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

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

```math
\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{\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}}
```

# QuirkでGrover Search
## 起動してみる
本稿では、量子計算のシミュレータとして[Quirk](https://algassert.com/quirk#circuit={%22cols%22:[]})を利用します。
Qurikを起動すると、標準サンプルとしてGrover Searchがあるのでこれを利用します。

<img width="600px" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/c2f0169a-ecdc-04fd-7b31-14b9b492c61d.png">

Grover Searchを選択すると、回路が表示されます。

<img width="600px" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/ccd6b314-c3d8-ef96-52c5-4260b0496ab2.png">

# Grover Operatorを適正回数適用する
上述のOracleとIAMを適正回数（$\sqrt{N}$回）適用したいので、下記のような回路となります。

* [QuirkでのGrover Search（適正回数）](https://algassert.com/quirk#circuit={%22cols%22:[[%22X%22,%22X%22,%22X%22,%22X%22,%22X%22],[%22H%22,%22H%22,%22H%22,%22H%22,%22H%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22]],%22gates%22:[{%22id%22:%22~vn6c%22,%22name%22:%22Oracle%22,%22circuit%22:{%22cols%22:[[%22Z%22,%22%E2%80%A2%22,%22%E2%97%A6%22,%22%E2%80%A2%22,%22%E2%80%A2%22]]}}]})

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/d9f12328-5b53-6ab3-2644-e368f83dab86.png)

$\sqrt{N}$回以前で観測したら、どうでしょうか？
検索対象データに対応する確率（確率振幅）は下記の通りでやはり４回目でピークを迎えます。

|1回目|2回目|3回目|4回目|
|:-:|:-:|:-:|:-:|
|25%|60%|89%|99%|
|<img width=150 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/344f57d7-0ae1-a28d-f8a5-5621281eb6d2.png">|<img width=150 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/2020dcba-066c-2206-3739-a91f4df03a5a.png">|<img width=150 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/feb3a5b8-735f-e853-7d68-d7d351b77389.png">|<img width=150 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/2f20bf0e-7c3c-9699-5958-eb2367b57f67.png">|

# 素朴な疑問
上記結果だけでは、Grover Operatorを適用すれば適用するほどに検索対象データに対応する確率が100%に近い状態で結果を取り出せるように見えます。
では、5回目以降はどのような確率（確率振幅）になるかが気になります。
そこで、実験的に、適正回数以上に過剰にGrover Operatorを適用してみたいと思います。

# Grover Operatorを過剰に適用する
適正が４回だったのでその倍の８回、オペレータを適用してみましょう。

* [QuirkでのGrover Search（過剰にオペレータを適用）](https://algassert.com/quirk#circuit={%22cols%22:[[%22X%22,%22X%22,%22X%22,%22X%22,%22X%22],[%22H%22,%22H%22,%22H%22,%22H%22,%22H%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22],[%22~vn6c%22],[%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22%E2%8A%96%22,%22X%22],[%22Chance5%22]],%22gates%22:[{%22id%22:%22~vn6c%22,%22name%22:%22Oracle%22,%22circuit%22:{%22cols%22:[[%22Z%22,%22%E2%80%A2%22,%22%E2%97%A6%22,%22%E2%80%A2%22,%22%E2%80%A2%22]]}}]}) 

<img width=800 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/7d9bacef-dad2-956d-0071-2d963b9a3b41.png">

1回目～4回目は上記と変わらないので5~8回目について確認します。下記に示しますが、
**適正回数以上にオペレータを適用すると検索対象の確率（確率振幅）は、なんと減衰します。。**

|5回目|6回目|7回目|8回目|
|:-:|:-:|:-:|:-:|
|85%|54%|21%|1.4%|
|<img width=150 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/c8e73d0e-bb6f-d3bd-1a5a-eaeaf20f1044.png">|<img width=150 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/c1e9e7dd-7199-f208-5377-a0666acf0aaf.png">|<img width=150 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/4936e7ca-872d-7c42-4aa6-c1681d08077b.png">|<img width=150 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/5afdf518-20bd-1b56-0a1c-a1a99dba9274.png">|

# 最適なオペレータの適用回数について
[Quantum Native dojo 8.2](https://dojo.qulacs.org/ja/latest/notebooks/8.2_Grovers_algorithm.html)にも解説があるとおり、所望の$\ket{\beta}$に対して、$\ket{s}$が最も近づくタイミングが、計算により求められ、それが$\sqrt{N}$となります。詳細は[Quantum Native dojo 8.2](https://dojo.qulacs.org/ja/latest/notebooks/8.2_Grovers_algorithm.html)を参照いただければと思います。
恐縮ですが、リンクさせていただきます。

<img width=400 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/300e1dc6-ab10-3a52-6d40-c6d009eb0d78.png>

# まとめ
Grover Searchの特徴ですが、下記は事実です。

* データ数Nに対して、$O(\sqrt{N})$のオペレータ適用でデータ検索ができる！

ただし、$\sqrt{N}$で効率的にデータ探索ができるとう言葉を正しく解釈すると、所望の結果が得られるオペレータ適用回数が$\sqrt{N}$回であって、**Grover Searchはいい塩梅が重要**というのが本質な気がします。
中を覗き見したくても、測定したら量子状態は破壊されるので、いい塩梅まで我慢して、待って待って良いタイミングで測定する。そんな、Grover Searchのご紹介でした。

# (補足）サンプルのGrover Operatorについて
Grover Searchは下記の２つの操作から構成されるGrover Operatorをデータ数Nに対して、$\sqrt{N}$回適用し解を得るアルゴリズムです。

* データをマーキングずるためのOracle
* マーキングしたデータに対応する振幅を増幅するためのIAM（Inversion About Mean)

これらが、Quirkのサンプル上では、下記の様の実装されています。

## Oracle
Toolbox2のOracleにマウスオーバすると表示されるのですが、事前定義の回路として下記のようにOracleが定義されています。これにより検索対象に対してマーキングを行います。

<img width="300px" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/b3025890-889e-e078-5212-5d7cb091d43b.png">

## Inversion About Mean（IAM）
Oracleでマーキングした検索対象に対応する確率振幅を増幅するためのIAMが必要ですが、一般的には検索対象ビットに対する$H^{\otimes N}$と位相シフトの$Controlled-Z$で構成されます。

<img width="600px" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/54e1cf07-736e-7672-0ebf-00dbeb51fd1a.png">

一方で、サンプルの量子回路上でのIAM相当の部分は、下記のようになっています。

<img width="40px" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/4f087f90-ba24-3af2-6e45-3783ebf8841a.png">

このゲートについては、https://algassert.com/post/1706 に解説があるのですが、$H$で挟まれる$Controlled-U$相当の操作が行われるゲートの様で、このゲートでIAM相当の振幅増幅ができるようです