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

はじめに

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

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

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

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

$$
% 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のアルゴリズムの概略を説明します。¹

#	手順	図との対応
①	全ビットを$H$ゲートにより均等な重ね合わせ状態にする。
②	OracleとIAMで構成するGrover Operatorを、√N回適用する。
	②-1 Oracle：探索対象の確率振幅だけを、マイナスにする
	②-1 IAM ：マイナスの確率振幅を増幅し、見つけやすくする
③	繰り返し後に量子ビットを測定すると、探索対象が現れる

2bit Grover

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

• 2bit GroverをQuirkで開く

①：Hゲートで均等重ね合わせ

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

\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によると、「神託（神のお告げ）」ですね。
何をするかというと、神のように正解を言い当てる機能を担います。

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

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

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

ですが、、

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

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

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

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

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

    

具体例

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

ただ、今回は簡単のために数字を探します

今回の問題設定では、探索の分母の数は４となります。0～3の中から3を探します。

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

Oracleの構成方法

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

\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ゲートは

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

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

\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$）で良さそうです。
つまり、下記の回路の赤い部分になります。

つまり、

\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で位相反転を確認する

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

②-2：IAMで、位相がマイナスの確率振幅を増幅する

上記でも確認したとおり、

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

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

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

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

です。

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

Phase Shift Operatorの確認

今回は、2bit Groverですので、³

\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$ですので、

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$で元に戻すような演算子が必要となります。

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

IAM(Inversion About Mean)でなぜ振幅増幅するか

詳細は、下記サイトの解説を参照ください。リンクさせていただきます。

概略だけ記載すると、

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

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

③：Grover Operatorを繰り返したあと測定する

最後です。
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については下記で補足しています。

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

参考

1. https://quantum.riken.jp/pdf/qc4.pdfより引用 ↩

2. 実際には、こういった複雑な情報が量子回路上で表現された上で、それを判断することができるOracleを構成する必要があるので、現状の量子コンピュータではまだまだ、情報のエンコードもOracleも実装することは出来ませんが、原理的にはこういうことだと理解しています。 ↩

3. 引用した資料の図では、$2\ket{00}\bra{00}-1$なのですが、全体の符号を逆転した$-(2\ket{00}\bra{00}-1)$でないと、計算結果が合わないので全体に、マイナスを掛けています。（詳しいひと教えて下さい。。） ↩