Groverのアルゴリズム - 空から毛がはえた

勉強中の量子アルゴリズムについてまとめます。間違いがありましたら、コメントください。

Groverのアルゴリズムはnビットで表される $2^{n}$ 個のビット列から、1個のビット列を探し出す量子アルゴリズムです。

アルゴリズムはおおまかには以下です。 $N = 2^{n}$ とします。

量子ビットをn個用意して、 $N$ 個の状態の重ね合わせ状態を作る。各状態が各ビット列に対応する。ここで、各状態の確率振幅が等しく $\frac{1}{\sqrt{N}}$ になるようにする。
重ね合わせ状態のうち、探索対象の状態の確率振幅にだけ-1を掛ける
確率振幅の平均値 $\mu = \sum_{x=0}^{N-1}a_{x}$ を求め、各状態の確率振幅を $a_{x}\to 2\mu - a_{x}$ のように変化させる。

2と3を繰り返すことで、探索対象の状態の確率振幅を増幅させていきます。

アルゴリズムの詳細は以下の動画が分かりやすかったです。

www.youtube.com

今回の記事では、上記手順の2と3を何回繰り返せばよいかを求めます。

まず、n個の量子ビットの状態を次のようにセッティングします。

$|\psi>=\sum_{x\neq x^{\ast}}a_{0}|x>+b_{0}|x^{\ast}>$

ここで $|x^{\ast}>$ は探索対象の状態です。また、 $a_{0}=b_{0}=\frac{1}{\sqrt{N}}$ です。

2と3を1回行うと探索対象でない状態の確率振幅 $a_{1}$ と、探索対象の状態の確率振幅 $b_{1}$ はそれぞれ以下になります。

$a_{1}=2\mu_{0}-a_{0}$ $b_{1}=2\mu_{0}+b_{0}$

ここで平均値 $\mu_{0}=\frac{(N-1)a_{0}-b_{0}}{N}$ を使いました。

2と3をk回行った後の確率振幅を求めるためには、以下の連立漸化式を解く必要があります。

$a_{0}=b_{0}=\frac{1}{\sqrt{N}}$ $\mu_{k}=\frac{(N-1)a_{k}-b_{k}}{N}$ $a_{k+1}=2\mu_{k}-a_{k}=\frac{N-2}{N}a_{k}-\frac{2}{N}b_{k}$ $b_{k+1}=2\mu_{k}+b_{k}=\frac{2(N-1)}{N}a_{k}+\frac{N-2}{N}b_{k}$

行列で書くと次のようになります。

$\begin{pmatrix} a_{k+1} \\ b_{k+1} \end{pmatrix} = \begin{pmatrix} \frac{N-2}{N} &-\frac{2}{N} \\ \frac{2(N-1)}{N} &\frac{N-2}{N} \end{pmatrix}\begin{pmatrix} a_{k} \\ b_{k} \end{pmatrix}$

行列

$A= \begin{pmatrix} \frac{N-2}{N} &-\frac{2}{N} \\ \frac{2(N-1)}{N} &\frac{N-2}{N} \end{pmatrix}$

を $k$ 回掛けた $A^{k}$ を求めるために $A$ の固有ベクトルを使います。

固有ベクトル $\vec{x_{+}}(固有値: \lambda_{+})$ , $\vec{x_{-}}(固有値: \lambda_{-})$ を並べた行列

$P=\begin{pmatrix} \vec{x_{+}} &\vec{x_{-}} \end{pmatrix}$

を使って、

$(P^{-1}AP)^{k}=P^{-1}A^{k}P=\begin{pmatrix} \lambda_{+}^{k} & 0 \\ 0 & \lambda_{-}^{k}\end{pmatrix}$

となるので、

$A^{k}=P\begin{pmatrix} \lambda_{+}^{k} & 0 \\ 0 & \lambda_{-}^{k}\end{pmatrix} P^{-1}$

となります。

固有値、固有ベクトルは以下の特性方程式を解いて求めます。

$det(A-\lambda I) = 0$

解くと、固有値、固有ベクトルは次になります。

$\lambda_{\pm} = \frac{N-2\pm 2i\sqrt{N-1}}{N}$

$\vec{x_{\pm}}=\begin{pmatrix} 1 \\ \mp i\sqrt{N-1} \end{pmatrix}$ $P=\begin{pmatrix} \vec{x_{+}} & \vec{x_{-}} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ -i\sqrt{N-1} & i\sqrt{N-1} \end{pmatrix}$ $P^{-1}=\frac{1}{2i\sqrt{N-1}}\begin{pmatrix} i\sqrt{N-1} & -1 \\ i\sqrt{N-1} & 1 \end{pmatrix}$

よって

$A^{k} = \begin{pmatrix} \frac{\lambda_{+}^{k} + \lambda_{-}^{k}}{2} & -\frac{1}{\sqrt{N-1}}\frac{\lambda_{+}^{k} - \lambda_{-}^{k}}{2i} \\ -\sqrt{N-1}\frac{\lambda_{+}^{k} - \lambda_{-}^{k}}{2i} & \frac{\lambda_{+}^{k} + \lambda_{-}^{k}}{2} \end{pmatrix}$

ここで

$\cos\theta = \frac{N-2}{N}$ $\sin\theta = \frac{2\sqrt{N-1}}{N}$

とおくと

$A^{k}=\begin{pmatrix} \cos k\theta & -\frac{1}{\sqrt{N-1}}\sin k\theta \\ -\sqrt{N-1}\sin k\theta & \cos k\theta \end{pmatrix}$

したがって

$\begin{pmatrix} a_{k} \\ b_{k} \end{pmatrix} = \begin{pmatrix} \cos k\theta & -\frac{1}{\sqrt{N-1}}\sin k\theta \\ -\sqrt{N-1}\sin k\theta & \cos k\theta \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{N}} \\ \frac{1}{\sqrt{N}} \end{pmatrix}$ $= \begin{pmatrix} \frac{1}{\sqrt{N-1}}(\sqrt{\frac{N-1}{N}}\cos k\theta - \frac{1}{\sqrt{N}}\sin k\theta) \\ -\sqrt{\frac{N-1}{N}}\sin k\theta + \frac{1}{\sqrt{N}}\cos k\theta \end{pmatrix}$ $= \begin{pmatrix} \frac{1}{\sqrt{N-1}} \cos(k\theta+\alpha) \\ \sin(k\theta + \alpha) \end{pmatrix}$