Grover Search①：Oracleを丁寧に説明してみる

# はじめに
複数の選択肢の中から、所望の状態を見つけ出すGroverのアルゴリズム。
所望の状態とは、**データ**そのもの、**パターンや条件**でも良いです。

* 100個のデータ"77"というデータを見つけたい　→　**"77"というデータ**そのもの
* 選択肢の中からルールや条件に適合するものを見つけたい　→　**その条件やパターン**

探索アルゴリズムであるGroverについて丁寧に書いてみたいと思います。
なお、誤り等あれば、ぜひコメント頂ければ幸いです。

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

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}}
$$

# Groverのアルゴリズム
まずは、Groverのアルゴリズムの概略を説明します。[^abe]

<img width=600 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/97e7eaf6-3ea0-4937-21f9-7b59f51006a5.png>

|#|手順|図との対応|
|:--:|:--|:--:|
|①|全ビットを$H$ゲートにより均等な重ね合わせ状態にする。|<img width=100 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/b5113255-2c94-b6b5-3ede-b9650770cae2.png>|
|②|OracleとIAMで構成するGrover Operatorを、√N回適用する。|<img width=150 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/e6a4a81d-7781-36ea-b118-cffe365151d1.png>|
||②-1 Oracle：探索対象の確率振幅だけを、マイナスにする|<img width=50 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/ba9eb1b6-5090-5c05-91fc-c1caa7678604.png>|
||②-1 IAM   ：マイナスの確率振幅を増幅し、見つけやすくする|<img width=150 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/e086e944-1470-f8e3-b951-22531874ad94.png>|
|③|繰り返し後に量子ビットを測定すると、探索対象が現れる|<img width=80 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/4ceb96ab-70f0-d31e-cdb9-3f191ea4b229.png>|

# 2bit Grover
よりシンプルに説明するために、2ビットのGrover Searchを考えます。
今回は、下記の回路を作成していきたいと思います

* [2bit GroverをQuirkで開く](https://algassert.com/quirk#circuit={%22cols%22:[[%22H%22,%22H%22],[%22Chance2%22],[%22%E2%80%A6%22,%22%E2%80%A6%22],[%22%E2%80%A2%22,%22Z%22],[%22Chance2%22],[%22%E2%80%A6%22,%22%E2%80%A6%22],[%22H%22,%22H%22],[%22X%22,%22X%22],[%22%E2%80%A2%22,%22Z%22],[%22X%22,%22X%22],[%22H%22,%22H%22],[%22Chance2%22]]})

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/7c70d1f9-d2e6-1814-ef91-5bbe3b3c22e2.png)


# ①：Hゲートで均等重ね合わせ
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/319b0854-f3f2-e047-fb86-0031908c0a9d.png)


２ビットの均等な重ね合わせを作ります。
確率振幅の２乗が、そのビットパターンの観測確率だったので、下記は$1/4$の均等な確率で、00,01,10,11を観測します。

```math
\ket{00} \xrightarrow{H_1,H_2} 
\frac{1}{2}
\left(
\ket{00}+\ket{01}+\ket{10}+\ket{11}
\right)
```
# ②：Grover Operatorを√N回繰返す
今回は、適用回数１回ですが、、

* データ数Nに対して√Nのペースで Operatorの適用回数が増えます。
* データ数の増分に対して、このGrover Operatorの適用回数に√が掛かる。

これが、古典での探索と比較した場合に、Grover Searchが高速であると言われる所以です。
では、Grover Operatorの中身を見ていきましょう。

## ②-1：Oracleを適用する
### Oracleとはなにか
Oracleとは何でしょうか？Wikipediaによると、「神託（神のお告げ）」ですね。
何をするかというと、**神のように正解を言い当てる機能**を担います。

https://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%A9%E3%82%AF%E3%83%AB

冒頭で説明したとおり、Oracleに探索対象データを与えると**正解を言い当てます**
そして、その正解に対応する、量子状態の**確率振幅にマイナスを付与します**

* 「これが正解」とい言い当てる機能が実装出来れば、それはOracleとして機能できます
*  データの検索で0～100に対して、**"77"**が正解であれば、その時にだけ**マイナス**を付与する

ここで、出てくる疑問として、**"77"という正解を知っている必要**がある。
これって、「答えをカンニングしてるやん」
そうです。「神様、答えをカンニングしている疑惑」ですｗ

ですが、、

### 正解を知らなくてもOracleは実装できる

（誤解を恐れずにいうと）**「正解そのものを知らなくても良いのです」**
**※これからはたとえ話になりますが、例えば**

* 子供に人気の食べ物で、黄色くて、ケチャップをかけて、スプーンで食べる。
* 原材料は、卵、鶏肉、たまねぎ、ご飯、しお、胡椒、サラダ油
* ご飯の上に、卵を加熱したものをかけた食べ物
* **上記条件を満たすものが正解なので、符号をマイナスにします**

上記のように、**「正解を言い当て」**そのときに**「マイナスを付与する」**機能を**量子回路上で実装**できるのであれば、それはOracleになります。[^2]

つまり、正解が「オムライス」であることを知らずとも、
**その特徴や条件を書き下すこと**ができればOracleを実装することができます。（と理解しています）

![internet_god_kamieshi.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/366fd989-b048-9ebf-2fee-f5b9a30f9cfa.png)&nbsp;&nbsp;&nbsp;&nbsp;![omuraisu_heart.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/f3efe25c-5023-1332-1b80-768ee0b5cdf6.png)

### 具体例
こちらの記事では、最適な出店パターンの探索にGrover Searchを使っています。
データ検索ではなく、**出店に求められる条件や特性**をOracleとして実装します。

https://qiita.com/quaeva/items/147731026fce60da970b

### ただ、今回は簡単のために数字を探します
今回の問題設定では、探索の分母の数は４となります。0～3の中から3を探します。

|探索対象|量子ビット上での状態表現|Oracleが正解とするもの|
|:--:|:--:|:--:|
|0|$\ket{00}$||
|1|$\ket{01}$||
|2|$\ket{10}$||
|3|$\ket{11}$|★対象★<br/>この確率振幅をマイナスに|

### Oracleの構成方法
一般的には、**Oracle Work bit (Work Space)**というマーキング用の補助ビットを用いるのですが、今回は簡単にするために、$CtrlZ$ゲートを使います。
Oracleでは、均等な重ね合わせに対して、$\ket{11}$の位相（符号）をマイナスに反転したい
つまり、

```math
\frac{1}{2}
\left(
\ket{00}+\ket{01}+\ket{10}+\ket{11}
\right)
\xrightarrow{\color{red}{Oracle}} 
\frac{1}{2}
\left(
\ket{00}+\ket{01}+\ket{10}\color{red}{-1}\ket{11}
\right)
```

これをどう構成すれば良いでしょうか？
Zゲートは

```math
\displaylines{
Z\ket{0} = \ket{0}
\\
Z\ket{1} = \color{red}{-1}\ket{1}
}
```

ですので、マイナスを付けるのに使えそうです。
そして、今対象は２量子系ですので、制御付きＺ（$ctrlZ$）を使ってみたらどうでしょう。

```math
\displaylines{
CZ\ket{00} = \ket{00}
\\
CZ\ket{01} = \ket{01}
\\
CZ\ket{10} = \ket{10}
\\
CZ\ket{11} = \color{red}{-1}\ket{11}
}
```
なので、今回のOracleは、制御付きＺ（$ctrlZ$）で良さそうです。
つまり、下記の回路の赤い部分になります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/f2bd4a42-55bf-99c9-5849-4e59970470c4.png)

つまり、

```math
\frac{1}{2}
\left(
\ket{00}+\ket{01}+\ket{10}+\ket{11}
\right)
\xrightarrow{\color{red}{CZ_{oracle}}} 
\frac{1}{2}
\left(
\ket{00}+\ket{01}+\ket{10}\color{red}{-1}\ket{11}
\right)
```

### マーキング（位相反転）の確認
説明に利用しているQuirkの、Probabilty Display（確率表示）には、符号（位相）は表現されないので、別の可視化（Amplitude Display）で位相も確認しておきましょう。

* [Quirkで位相反転を確認する](https://algassert.com/quirk#circuit={%22cols%22:[[%22H%22,%22H%22],[%22Chance2%22],[%22Amps2%22],[],[%22%E2%80%A6%22,%22%E2%80%A6%22],[%22%E2%80%A2%22,%22Z%22],[%22Chance2%22],[%22Amps2%22],[],[%22%E2%80%A6%22,%22%E2%80%A6%22],[%22H%22,%22H%22],[%22X%22,%22X%22],[%22%E2%80%A2%22,%22Z%22],[%22X%22,%22X%22],[%22H%22,%22H%22],[%22Chance2%22]]})

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/45797b71-fdf5-3756-8947-e8ca1631c45c.png)

マウスオーバすると、$CZ$の前後で$\ket{11}$の位相（符号）だけが反転していますね。

## ②-2：IAMで、位相がマイナスの確率振幅を増幅する
上記でも確認したとおり、

* Oracleはターゲットとなる量子状態に対して、位相（符号）を反転するだけです。
* 確率振幅は増幅しないので、Oracleを適用したあとの量子状態を観測しても測定により均等な重ね合わせとなります。
* つまり、Oracleを適用後でも、00、01、10、11の観測確率はそれぞれ、$1/4$のままです。

これでは、所望の11を見つけることができないので、観測したときに所望の量子状態を観測しやすくするために（目立たせるために）位相（符号）がマイナスの量子状態の観測確率（確率振幅）を増幅します。

そして、その振幅増幅には、下記回路を使います。

<img width=500 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/e086e944-1470-f8e3-b951-22531874ad94.png>

今回の作成する回路でいうと、

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/a2a19753-afaf-8bc9-9dab-2676bcac47d4.png)

です。

* $H^{\otimes n}$は、$H$ゲートをnビットに対し適用するという意味なので上記の通り２ビットに$H$ゲートを適用しておきます。
* 少し確認したいのは、$2\ketbra{0}{0}-I$　のPhase Shift Operatorです。

### Phase Shift Operatorの確認

今回は、2bit Groverですので、[^3]

```math
\displaylines{
-(2\ket{00}\bra{00} - I) = -2 
\begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}
\begin{bmatrix} 1 & 0 & 0 & 0 \end{bmatrix}
+I
\\
= 
\begin{bmatrix}
 -2 & 0 & 0 & 0 \\
 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 0 \\
\end{bmatrix}
+
\begin{bmatrix}
 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 0 & 1 & 0 \\
 0 & 0 & 0 & 1 \\
\end{bmatrix}
=
\begin{bmatrix}
 \color{red}{-1} & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 0 & 1 & 0 \\
 0 & 0 & 0 & 1 \\
\end{bmatrix}
}
```
となり、

* **入力が$\ket{00}$**のときに、位相を**-1**にする演算子ができました。

一方で、

* **入力が$\ket{11}$**のときに、位相を**-1**にする演算子が、$CtrlZ$ですので、

```math
CtrlZ = 
\begin{bmatrix}
 1 & 0 & 0 & 0 \\
 0 & 1 & 0 & 0 \\
 0 & 0 & 1 & 0 \\
 0 & 0 & 0 & \color{red}{-1} 
\end{bmatrix}
```
つまり、

* $CtrlZ$に入力する前に、２ビットとも$X$で反転させ入力し、
* 処理が終わったあと$X$で元に戻すような演算子が必要となります。

それが、下記回路で表現されています。
実際に、下記回路のテンソル積を計算すると上記行列と一致します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/a2dd949e-ad2b-570e-9aa4-0bb4da5c3eee.png)

### IAM(Inversion About Mean)でなぜ振幅増幅するか
詳細は、下記サイトの解説を参照ください。リンクさせていただきます。

https://dojo.qulacs.org/ja/latest/notebooks/8.2_Grovers_algorithm.html#%E5%B9%BE%E4%BD%95%E5%AD%A6%E7%9A%84%E3%81%AA%E8%AA%AC%E6%98%8E

概略だけ記載すると、

* 全量子状態の確率振幅の平均値に対して折り返す。
* この操作を行うと、Oracleにより負にマーキングされた量子状態の確率振幅だけが、＋／－／＋と揺さぶられ、この折返しにより、その確率振幅が１に近い状態に近づきます。

といった感じの処理になります。

<img width=500 src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/ea1892b6-5ce8-61a2-7269-b92a4c0b55a4.png>

# ③：Grover Operatorを繰り返したあと測定する
<img src=https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/87f9666e-1f23-150b-ad77-4d3835d8f1f1.png>

最後です。
Grover Operatorにより、探したかった3に対応する$\ket{11}$の確率振幅が１に近い状態になっています。
この状態まで持ち込めば、測定により１に近い確率で、所望の$\ket{11}$を観測することができます。

# まとめ
Grover Searchについて、主にOracleを詳しく説明しました。

* Oracleは、「探し出すもの」が表現できれば、データでも良いですし、条件でも良いです。
* Oracleにより、探し出すものの確率振幅にマークをつけます（確率振幅をマイナスにする）
* 次に、IAMにより、確率振幅を平均値に対して折り返すことで、振幅増幅をします。
* そして、これらを繰り返して、観測に都合が良いタイミングになったら観測して結果をえる。

こんな流れでした。で、活用に向けたポイントとしては、

* データの表現の仕方と、Oracleの設計にコツがあると考えています。
* 一方で、IAMは形が決まってしまっているので、パターン化が可能かと。

よって、賢いデータ表現とOracleをどう設計するか？が活用のポイントになると思います。
なにかあれば、コメント等いただければと。また、よろしければ**LTGM**を
最後に補足事項をまとめておこうと思います。

# 補足
Oracleを、$CtrlZ$で実装してしまうことで、Oracle Work bitを省略しましたが、Oracle Work bitについては下記で補足しています。

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

なお、3-bit Grover Searchについては下記で扱っています。

https://qiita.com/shnchr/items/8974a3072a0f1bbe4832

# 参考
https://qiita.com/ymurata/items/343f58ebe7a1b37a4b79

https://qiita.com/quaeva/items/147731026fce60da970b

https://dojo.qulacs.org/ja/latest/notebooks/8.2_Grovers_algorithm.html#

https://quantum.riken.jp/pdf/qc4.pdf

[^abe]: https://quantum.riken.jp/pdf/qc4.pdfより引用
[^2]: 実際には、こういった複雑な情報が量子回路上で表現された上で、それを判断することができるOracleを構成する必要があるので、現状の量子コンピュータではまだまだ、情報のエンコードもOracleも実装することは出来ませんが、原理的にはこういうことだと理解しています。
[^3]: 引用した資料の図では、$2\ket{00}\bra{00}-1$なのですが、全体の符号を逆転した$-(2\ket{00}\bra{00}-1)$でないと、計算結果が合わないので全体に、マイナスを掛けています。（詳しいひと教えて下さい。。）