グローバーアルゴリズム (Grover's algorithm)

12225 ワード
量子コンピュータ 量子ゲート 量子コンピュータ テキストリンク

この記事に関して

ここでは量子アルゴリズムの一つであるGrover's algorithm(グローバー アルゴリズム)について説明します。

Oracle

前回 Deutsch-Jozsa algorithm で Oracle を用いました。
このときの Oracle の $f$ は全て 0, 1 または 0, 1 を半分ずつ返すものでした。

今回は 1 つだけ 1 を返す Oracle を考えます。
つまり $f$ の入力が $\left|00\cdots00\right>$ から $\left|11\cdots11\right>$ の $2^n$ 個でどこか一つだけ 1 を返し、それ以外は全て 0 を返すもとします。

f(x) = \left\{ \begin{array}{ccc} 0 & (x \neq \omega) \\
1 & (x = \omega) \end{array} \right.

$x = \omega$ で 1 を返すとしています。

Amplitude amplification (振幅増幅)

振幅という言葉が出てきました。
各状態の係数のことを振幅、確率のことを確率振幅と言います。

以下の式を見てみます。

H\left|0\right> \otimes H\left|0\right> = \frac{1}{2}(\left|00\right>+\left|01\right>+\left|10\right>+\left|11\right>) \xrightarrow{振幅増幅}\left|00\right>

この場合、矢印の左側では確率振幅は全て $1/4$ となり、
右側の状態の確率振幅は $\left|00\right>$ が 1 となっています。

Amplitude amplification は言葉の通りこの確率振幅を上のように増幅させるアルゴリズムです。

以下の図を用いて具体的な計算を説明します。

参考: https://en.wikipedia.org/wiki/Grover%27s_algorithm

まずは記号の説明をします。
$\left|s\right>$ は全ビットの重ね合わせです。

\left|s\right> = \bigotimes_{}^{n}H\left|0\right> = \frac{1}{\sqrt{2^n}}
\sum_{x\in\{0,1\}^n}^{2^n}\left|x\right>

このうち、振幅増幅させたい状態を $\left|\omega\right>$ としています。

\left|\omega\right> = \frac{1}{\sqrt{2^n}}{}^t(0  0  \cdots  0  1  0  \cdots  0 0)

x 番目に1が入っているとします。

$\left|s'\right>$ は $\left|s\right>$ から $\left|\omega\right>$ を除いたベクトルです。

\left|s'\right> = \left|s\right> - \left|\omega\right> = \left|\omega^{\perp}\right>

$\left|\omega\right>$ に垂直なことがわかります。

次に上の図のように $\left|s'\right>$ と $\left|\omega\right>$ から成る単位円を考えます。
ただし $\left|s'\right>$ と $\left|\omega\right>$ の長さが違うので

\widetilde{\left|s'\right>} = \sqrt{\frac{2^n}{2^n-1}} \left|s'\right> \\
\widetilde{\left|\omega\right>} = \sqrt{2^n}\left|\omega\right>

として長さを共に 1 にします。

このことから、単位円上のベクトル $\left|\psi\right>$ は以下のように表せます。

\left|\psi\right> = \cos\phi \widetilde{\left|s'\right>} + \sin\phi\widetilde{ \left|\omega\right>} \\

$U_{\omega}$ は $\left|s'\right>$ を軸に $\left|\psi\right>$ を反転させる行列です。
すなわち $\left|\psi\right>$ を $-\phi$ 回転させます。

U_{\omega}\left|\psi\right> = \cos(-\phi) \widetilde{\left|s'\right>} + \sin(-\phi) \widetilde{\left|\omega\right>} = \cos\phi \widetilde{\left|s'\right>} - \sin\phi \widetilde{\left|\omega\right>}

$U_s$ は $\left|\psi\right>$ を $\left|s\right>$ で反転させる行列です。

U_s\left|\psi\right> = \cos\left\{\frac{\theta}{2}+\left(\frac{\theta}{2}-\phi\right)\right\} \widetilde{\left|s'\right>} + \sin\left\{\frac{\theta}{2}+\left(\frac{\theta}{2}-\phi\right)\right\} \widetilde{\left|\omega\right>} = \cos(\theta-\phi) \widetilde{\left|s'\right>} + \sin(\theta-\phi) \widetilde{\left|\omega\right>}

概要

アルゴリズムの概要は以下のようになります。

1 $\left|s\right>$ を $U_{\omega}$ を用いて $\left|s'\right>$ で折り返す。

2 $U_{\omega}\left|s\right>$ を $U_s$ を用いて $\left|s\right>$ で折り返す。

以上の流れを詳しく説明していきます。

1. s' に関する折り返し

$\left|s\right>$ について上の図のように $\theta$ を用いて

\left|s\right> = \cos\left(\frac{\theta}{2}\right)\widetilde{\left|s'\right>} - \sin\left(\frac{\theta}{2}\right)\widetilde{\left|\omega\right>}

と定義します。

このとき

\cos\left(\frac{\theta}{2}\right) = \sqrt{\frac{2^n-1}{2^n}}, \ \sin\left(\frac{\theta}{2}\right) = \sqrt{\frac{1}{2^n}}

と表せます。

$U_{\omega}$ で $\left|s\right>$ を $\left|s'\right>$ を軸に折り返します。
上の図から以下のようにかけます。

U_{\omega}\left|s\right> = \cos\left(-\frac{\theta}{2}\right)\widetilde{\left|s'\right>} + \sin\left(-\frac{\theta}{2}\right)\widetilde{\left|\omega\right>} = \cos\left(\frac{\theta}{2}\right)\widetilde{\left|s'\right>} - \sin\left(\frac{\theta}{2}\right)\widetilde{\left|\omega\right>}

この操作に関しては $\left|\omega\right>$ のみに作用しているので $U_{\omega}$ は上で述べた Oracle を表していることがわかります。

2. s に関する折り返し

$U_s$ で $U_{\omega}\left|s\right>$ を $\left|s\right>$ を軸に折り返します。

U_sU_{\omega}\left|s\right> = U_s\left(\cos\left(-\frac{\theta}{2}\right)\widetilde{\left|s'\right>} + \sin\left(-\frac{\theta}{2}\right)\widetilde{\left|\omega\right>}\right)\\

ここで $2\theta$ 回転させれば良いので

U_sU_{\omega}\left|s\right> = 
\cos\left(\frac{3}{2}\theta\right)\widetilde{\left|s'\right>} + 
\sin\left(\frac{3}{2}\theta\right)\widetilde{\left|\omega\right>} \\

具体的に $\cos$ と $\sin$ を求めると加法定理から

\cos\frac{3}{2}\theta = \left(1-\frac{4}{2^n}\right)\sqrt{\frac{2^n-1}{2^n}}, \ \sin\frac{3}{2}\theta = \left(3-\frac{4}{2^n}\right)\sqrt{\frac{1}{2^n}}\\

よって、$\left|s'\right>, \left|\omega\right>$ を用いると

U_sU_{\omega}\left|s\right> = \left(1-\frac{4}{2^n}\right)\left|s'\right>+\left(3-\frac{4}{2^n}\right)\left|\omega\right>

この操作によって $2^n$ 個の振幅のうち $\left|\omega\right>$ が他のよりも約３倍大きくなりました。
以上で振幅増幅させることができました。

Grover's algorithm

このアルゴリズムでは上の Oracle が与えられたときに $\left|\omega\right>$ を見つけることができます。

内容としては振幅増幅を繰り返し行い、$\left|s\right>$ を $\left|\omega\right>$ に近づけるということをします。

上の式から 1 回振幅増幅を行うと

\cos\left(\frac{3}{2}\theta\right)\widetilde{\left|s'\right>} + 
\sin\left(\frac{3}{2}\theta\right)\widetilde{\left|\omega\right>}

となりました。

よって、$n$ 回振幅増幅を行うと

\cos\left(\frac{1}{2}\theta+n\theta\right)\widetilde{\left|s'\right>} + 
\sin\left(\frac{1}{2}\theta+n\theta\right)\widetilde{\left|\omega\right>} = 
\cos\left\{\left(\frac{1}{2}+n\right)\theta\right\}\widetilde{\left|s'\right>} + 
\sin\left\{\left(\frac{1}{2}+n\right)\theta\right\}\widetilde{\left|\omega\right>}

と表せます。

振幅増幅を行うに連れて上の図の初期状態 $\left|s\right>$ が段々と $\left|\omega\right>$ に近づいて行くことがわかります。
つまり $\left|\omega\right>$ の確率振幅が 1 になっていきます。
ただこのまま繰り返ししても回転し続けるだけなので繰り返す回数を考える必要があります。

$\left|\omega\right>$ の確率振幅を 1 にするので

\sin^2\left\{\left(\frac{1}{2}+k\right)\theta\right\} < 1 \xrightarrow{\sin>0} \left(\frac{1}{2}+k\right)\theta < \frac{\pi}{2} \Leftrightarrow k < \frac{\pi}{2\theta} - \frac{1}{2}

以上から振幅増幅する回数が決まり、$\left|\omega\right>$ が取れることがわかりました。

補足 (量子プログラミングへの応用)

量子プログラミングでは振幅増幅は以下のように考えます。

$U_{\omega}$ はシンプルに $\left|s\right>$ の定義から $\left|s\right> = \left|s'\right> + \left|\omega\right>$ と分けて考えると

U_{\omega}(\left|s'\right> + \left|\omega\right>) = \left|s'\right> - \left|\omega\right>

となります。
つまりZ、CZゲートなどのように特定の状態だけ符号を変えるゲートを用いれば良いことがわかります。

$U_s$ は上の図から幾何的に考えると以下のようにかけます。

\begin{align} U_sU_{\omega}\left|s\right> &= 2(\left<s|U_{\omega}|s\right>\left|s\right> - U_{\omega}\left|s\right>) + U_{\omega}\left|s\right> \\
&= 2\left|s\right>\left<s\right|U_{\omega}\left|s\right> - U_{\omega}\left|s\right> \\
&= (2\left|s\right>\left<s\right| - I)\ U_{\omega}\left|s\right>
\end{align}

よって $U_s = 2\left|s\right>\left<s\right| - I$ となります。

さらに $U_s$ は以下のように分解できます。

2\left|s\right>\left<s\right| - I = 2H^{\otimes n}\left|0^n\right>\left<0^n\right|H^{\otimes n} - I = H^{\otimes n}(2\left|0^n\right>\left<0^n\right|-I)H^{\otimes n}\\(\left|0^n\right> = \left|00\cdots00\right>)

ここで $2\left|0^n\right>\left<0^n\right|-I$ に関して

2\left|0^n\right>\left<0^n\right|-I = \left(\begin{array}{ccccc} 
-1 & 0 & 0 & \cdots & 0 & 0\\
0 & 1 & 0 & \cdots & 0 & 0\\
0 & 0 & 1 & \cdots & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1\\
\end{array}\right)

と表せる。

これは

XZX = \left(\begin{array}{cc}
-1 & 0 \\
0 & 1 \\
\end{array}\right)

の性質から

2\left|0^n\right>\left<0^n\right|-I = X^{\otimes n}C^nZX^{\otimes n}

とかける。

以上から Grover's algorithm をゲートで書き直すことができた。

まとめ

今回は Grover's algorithm について説明しました。
次回は 量子位相推定( Quantum Phase Estimation ) について説明しようと思います。

参考文献

石坂 智、小川 朋宏、河内 亮周、木村 元、林 正人 (2012) 『量子情報科学入門』 共立出版

Grover の検索アルゴリズム と Quantum Amplitude Amplification/Estimation
https://whyitsso.net/physics/quantum_mechanics/AA_AE_Grover.html

Week2: Groverのアルゴリズム
https://github.com/quantum-challenge/2019/blob/master/problems/week2/week2.ipynb