なんのためのアルゴリズム？
たくさんのデータがある中で、答えを探したいとき （例）1から100までの自然数の配列があって偶数を取り出したい 組み合わせ最適化にも応用できるそうです。 とりあえず、アルゴリズムを見ていきたいと思います。$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
$$
理論的なお話
The oracle
アルゴリズムを作って実際に答えを出した際に、本当に答えかどうかをチェックしないといけません。そのために、「oracle」という'black box'なゲートを定義します。この内部でどのような操作をしているかはこのアルゴリズムの本質ではないので深入りしないことにします。\begin{align}
\ket{x}\ket{q} \xrightarrow{O} \ket{x}\ket{q\ \oplus f(x)}
\end{align}
当たり前ですが$ O $はユニタリ演算子です。
上の定義式の簡単な説明をしていきます。
最初のレジスタ$ \ket{x} $はインデックスを表しています。（配列での添え字にあたります。）
ここは$ O $を作用させても変化しません。
$ f(x) $はインデックス$ x $が正解か不正解かを判断する関数です。正解なら１、不正解なら０を返します。
$ \ket{q} $はoracle qubitと言い、$ O $を作用させた後は$ f(x) $とXOR演算をします。
ここでもし$ \ket{q} = \ket{0} $とすると、
・正解なら反転して$ \ket{1} $になる
・不正解なら変化しない
天下り的ですが、$ \ket{q} = \frac{\ket{0}-\ket{1}}{\sqrt{2}} $とすると
\begin{align}
\ket{x}(\frac{\ket{0} - \ket{1}}{\sqrt{2}}) \xrightarrow{O} (-1)^{f(x)}\ket{x}({\frac{\ket{0}-\ket{1}}{\sqrt{2}}})
\end{align}
正解の時は$ f(x) = 1 $なので反転するからマイナスがついて、不正解なら$ f(x) = 0 $なのでなにも起こりません。よく見るとoracle qubitは変化していないように見えます。なのでここからは、oracle qubitを省略します。
\begin{align}
\ket{x} \xrightarrow{O} (-1)^{f(x)}\ket{x}
\end{align}
実際にアルゴリズムを見ていく
探索する要素数を$ N = 2^n $, 正解の要素数を$ M $とします。 まず、毎度おなじみの$ \ket{0} $をn個と、oracle qubitを用意します。\begin{align}
\ket{0}^{\otimes n}\ket{0}
\end{align}
次もいつもと同様に第一レジスタに$ H $gateを作用させます。
また、oracle qubitに$ HX $gateを作用させます。
\begin{align}
\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\ket{x}[\frac{\ket{0}-\ket{1}}{\sqrt{2}}]
\end{align}
次に、$ G $というゲートを何回か作用させると、答えを得ることができます。
$ G $の中身を見ていきます。
\begin{align}
H^{\otimes n}(2\ket{0}\bra{0} - I)H^{\otimes n}O
\end{align}
結果から言うと、これは状態ベクトルの回転を表しています。ここが一番の肝になります。
少し、準備をします。
第一レジスタの状態ベクトルを$ \ket{\psi} $とします。
\begin{align}
\ket{\psi} = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\ket{x}
\end{align}
ここで$ x $とはインデックス番号のことでした。なので正解のものと、不正解のものに分けていきます。
$ \ket{\alpha} $を不正解のインデックスの重ね合わせ状態、$ \ket{\beta} $を正解のインデックスの重ね合わせ状態とします。
\begin{align}
\ket{\alpha} & = \frac{1}{\sqrt{N-M}}\sum''\ket{x} \\
\ket{\beta} &= \frac{1}{\sqrt{M}}\sum'\ket{x}
\end{align}
これを用いると$ \ket{\psi} $は以下のように表せます。
\begin{align}
\ket{\psi} = \sqrt{\frac{N-M}{N}}\ket{\alpha} + \sqrt{\frac{M}{N}}\ket{\beta}
\end{align}
$ \ket{\alpha} $と$ \ket{\beta} $は直交しているのでこの二つを二次元の線形空間の基底とすることができます。イメージしやすいように$ \ket{\alpha} $を$ x $軸、$ \ket{\beta} $を$ y $軸にとって考えます。また、$ cos{\frac{\theta}{2}} = \sqrt{\frac{N-M}{N}} $、$ sin{\frac{\theta}{2}} = \sqrt{\frac{M}{N}}$とします。（最後が分かりやすくなるために、$\frac{\theta}{2}$としています。）
準備が整いました。
まずこの状態ベクトル$ \ket{\psi} $に$ O $(oracleゲート)を作用させます。$ O $は正解のみマイナスをつけるゲートでした。正解のインデックスの重ね合わせが$ \ket{\beta} $なので$O$を作用させると次のようになります。
\begin{align}
\sqrt{\frac{N-M}{N}}\ket{\alpha} + \sqrt{\frac{M}{N}}\ket{\beta} \xrightarrow{O} \sqrt{\frac{N-M}{N}}\ket{\alpha} - \sqrt{\frac{M}{N}}\ket{\beta}
\end{align}
二次元の線形空間で考えれば$\ket{\psi}$を$\ket{\alpha}$軸に対して対称にしたものだと考えられます。
次に、$ 2\ket{\psi}\bra{\psi} - I$を作用させますが、自分は結果から逆に見ていくとわかりやすかったので、このやり方で説明していきます。
この演算子を$ O\ket{\psi} $に作用せせると$ \ket{\psi} $に関して対称な状態ベクトルになります。ここでは対称なベクトルにするためにはどのような演算子を作用させればよいかを考えていき$ 2\ket{\psi}\bra{\psi}-I $を導出します。
まず、$ \ket{\psi} $に平行な$ O\ket{\psi} $のベクトルを取り出します。
\begin{align}
\bra{\psi}O\ket{\psi}\ket{\psi} = (\ket{\psi}\bra{\psi})O\ket{\psi}
\end{align}
$ \ket{\psi} $に平行な成分は以下のように取り出せます。
\begin{align}
O\ket{\psi} - (\ket{\psi}\bra{\psi})O\ket{\psi}
\end{align}
$\ket{\psi}$に関して対称なので平行な成分はそのまま、垂直な成分はマイナスをつけます。
\begin{align}
(\ket{\psi}\bra{\psi})O\ket{\psi}-(O\ket{\psi} - (\ket{\psi}\bra{\psi})O\ket{\psi})=(2\ket{\psi}\bra{\psi}-I)O\ket{\psi}
\end{align}
よって$2\ket{\psi}\bra{\psi}-I$を得ることができました。一度$G$を作用させると、$ \theta $だけ$\beta$方向に回転することが分かりました。
状態を回転させて結局何がしたいのか？
もう一度このアルゴリズムのゴールを確認しておきます。それは、$N$個の要素の中から正解のインデックスを見つけることです。正解の状態ベクトルの重ね合わせである$\ket{\beta}$に$\ket{\psi}$を近づけていけば、$\ket{\beta}$を得る確率が上がっていきます。これを狙って回転させています。しかし、回転しすぎると通り過ぎてしまい不正解を得る確率が上がってしまい逆効果になります。次は、適切な回数を見つけていきましょう。回転させる回数は？
いままでのおさらいをすると$G$というゲートを作用させるともとの状態ベクトル$\ket{\psi}$が$\theta$回転することが分かりました。じゃあ何回$G$を作用させればいいのでしょうか。 まず$\frac{\theta}{2} > \frac{\pi}{4}$の場合を考えます。$N$個の要素のうち半分以上が正解の場合です。これは、そもそも二回やればそのうちのどちらかは答えなのでアルゴリズムを使う必要はなさそうです。（答えの要素数$ M $がもともと分からない場合は不正解なものを$N$こ要素に足してあげれば無理やり正解の要素数を半分以下にすることができます。） では$ \frac{\theta}{2} \leq \frac{\pi}{4} $の場合を考えます。$\ket{\beta}$と$\ket{\theta}$の角度は$arccos{\sqrt{\frac{M}{N}}}$と表すことができます。一回で$\theta$回転するので\begin{align}
R = CI(\frac{arccos{\sqrt{\frac{M}{N}}}}{\theta})
\end{align}
ここで$CI$は実数値に一番近い自然数を返す関数とします。
$G$をR回作用させれば高い確率で正解である$\ket{\beta}$を得ることができます。
おわりに
このアルゴリズムの計算量は$O(\sqrt{\frac{N}{M}})$なのでデータベースの探索とかは向いてなさそうです。 これから実用例を勉強していこうと思います。参考にした本