Groverアルゴリズム 自分用まとめ

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

Groverアルゴリズムの自分用まとめ。「Grover アルゴリズムについて」を主に参照。一部式が見えないので補完、自分が気になった内容を変更・追記、量子回路シミュレーター「QCEngine」のメモ書きするために自分で一からまとめ直した。

Groverアルゴリズムの概要

次のような全状態$\ket{\phi}$の2qubit量子系

\begin{eqnarray}
\ket{\phi} &=& \alpha \ket{00} + \beta \ket{10} + \gamma \ket{01} + \delta \ket{11}
\end{eqnarray}

について、ある固有状態、例えば$\ket{01}$が含まれているかどうかを探索する。言い換えると、$\ket{01}$の係数$\gamma$がゼロであるか非ゼロであるかを判定するアルゴリズムである。より一般化すれば、Nqubit系において$2^N$の状態の中からある特定の状態を探索することができる。古典アルゴリズムでは、N個の要素からなるランダムなデータベースから特定の要素を探索するには$\mathcal{O}(N)$オーダーの計算量となるが、Groverアルゴリズムでは$\mathcal{O}(\sqrt{N})$のステップ数で済むという。

簡単な具体例

Groverアルゴリズムでは、量子操作によって検索したい固有状態の確率振幅を1に近づけることで、測定によりその固有状態が観測されやすくする。その操作は、固有状態が元々含まれていない場合は確率振幅0を保つので、もし測定にかかればその時点で検索対象の固有状態の存在が保証されることになる。以下に具体例を示す。

例1

・次の全状態$\ket{\phi}$の2qubit量子系に$\ket{01}$が含まれていることを確認する。

\begin{eqnarray}
\ket{\phi} &=& \frac{1}{2} (\ket{00} + \ket{10} + \ket{01} + \ket{11})
\end{eqnarray}

まずは対象の固有状態の位相をマイナスに反転する操作を行う。

\begin{eqnarray}
\ket{\phi} &=& \frac{1}{2} (\ket{00} + \ket{10} - \ket{01} + \ket{11})
\end{eqnarray}

この後、$\ket{\phi}$に含まれる各固有状態の係数を平均値のまわりで逆転させる。今の場合、平均値は$\frac{\frac{1}{2}+\frac{1}{2}-\frac{1}{2}+\frac{1}{2}}{4}=\frac{1}{4}$なので、$\ket{01}$の係数が$\frac{1}{4}\times2-(-\frac{1}{2})=1$、その他の係数が$\frac{1}{4}\times2-(\frac{1}{2})=0$となる。最終的な全状態は、

\begin{eqnarray}
\ket{\phi} &=& \ket{01}
\end{eqnarray}

となり、測定すれば100%の確率で$\ket{01}$の状態が得られる。

・反対に、全状態$\ket{\phi}$に$\ket{01}$が含まれていない場合を考えると、これまでの操作では最終状態に$\ket{01}$の状態は存在しないことがわかる。よって測定によって$\ket{01}$が得られる確率は0%である。

以上により、全状態$\ket{\phi}$に$\ket{01}$が含まれているかどうかを測定結果から判別することができることがわかる。

例2

・次の全状態$\ket{\phi}$の2qubit量子系に$\ket{01}$が含まれていることを確認する。

\begin{eqnarray}
\ket{\phi} &=& \frac{1}{10} (0.5768\ket{00} + 0.5768\ket{10} + 0.0407\ket{01} + 0.5768\ket{11})
\end{eqnarray}

例1と同様の手順により、次のような最終状態になる。

\begin{eqnarray}
\ket{\phi} &=& \frac{1}{10} (0.2680\ket{00} + 0.2680\ket{10} + 0.8857\ket{01} + 0.2680\ket{11})
\end{eqnarray}

観測により、$(0.8857)^2\simeq0.78$なので、測定するとおよそ78%の確率で$\ket{10}$が得られる。初期状態では0.04という小さな確率振幅であったものが操作後には0.89と増大している。

量子計算による実現

上でみたように、Groverアルゴリズムでは検索対象の固有状態の位相を反転する、位相を平均値周りで反転するという2つの操作が必要となる。特に後者は古典的には単純だが、量子操作で実現可能かどうかは非自明に思える。ここでは一般的な場合に2つの操作がどのように実現されるかを見る。

1.選択的反転

一般の量子状態(N状態、$\mathrm{log}_2N$個qubit)

\begin{eqnarray}
\ket{\phi} \equiv \sum_{x=0}^{N-1} \omega_x \ket{x}
\end{eqnarray}

の中に存在するある固有状態$\ket{z}$に対してのみ位相反転するような量子操作$\hat{R}_f$を実現したい。
演算としては、

\begin{eqnarray}
\hat{R}_f \equiv \hat{1}-2\ket{z}\bra{z}
\end{eqnarray}

のように、$\ket{z}$の係数を-2倍したものをマイナスすればよさそう。確認のため、$\ket{\phi}$に作用させてみれば、

\begin{eqnarray}
(\hat{1}-2\ket{z}\bra{z})\ket{\phi} = \ket{\phi} - 2\omega_z \ket{z}
\end{eqnarray}

となる。

2.平均値周りで反転

一般の量子状態(N状態、$\mathrm{log}_2N$個qubit)

\begin{eqnarray}
\ket{\phi} \equiv \sum_{x=0}^{N-1} \omega_x \ket{x}
\end{eqnarray}

について、平均値$\bar{\omega} \equiv \frac{1}{N} \sum_{x=0}^{N-1} \omega_x$まわりで全ての係数を反転する操作を実現したい。最終的に

\begin{eqnarray}
\ket{\phi} \equiv \sum_{x=0}^{N-1} (2\bar{\omega} - \omega_x) \ket{x}
\end{eqnarray}

となればよい。直感的には難しいので、まず答えを示す。

\begin{eqnarray}
\hat{D} \equiv -\hat{1} + 2\ket{\phi_0}\bra{\phi_0} \\
ここで、\ket{\phi_0} \equiv \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \ket{x}
\end{eqnarray}

確認のため、$\ket{\phi}$に作用させてみると、

\begin{eqnarray}
\hat{D} \ket{\phi} &=& (-\hat{1} + 2\ket{\phi_0}\bra{\phi_0}) \ket{\phi} \\ 
&=& -\ket{\phi} + 2\ket{\phi_0} \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \bra{x} \sum_{x'=0}^{N-1} \omega_x' \ket{x'} \\
&=& -\ket{\phi} + 2\ket{\phi_0} \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \omega_x \\
&=& -\ket{\phi} + 2 \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1} \ket{x} \frac{1}{\sqrt{N}} \sum_{x'=0}^{N-1} \omega_x' \\
&=& -\ket{\phi} + 2N\bar{\omega} \ket{x} \\
&=& \sum_{x=0}^{N-1} (2\bar{\omega}-\omega_x) \ket{x} 
\end{eqnarray}

となった。

量子ゲートによる実装

Groverアルゴリズムに必要な操作が選択的反転$\hat{R}_f$および平均値周りで反転$\hat{D}$により実現することがわかった。しかし、実際の量子計算では量子回路上の量子ゲート演算で操作を行うため、これらの操作がゲート演算に置き換え可能でなければならない。ここでは2つの操作がどのような量子回路で実装できるのかを見る。
量子回路シミュレータとしてQCEngineを使用している。

1.選択的反転

選択的反転操作は、特定の固有状態の位相を反転するものであった。ここでは2qubit系について見てみる。

\begin{eqnarray}
\ket{\phi} &=& \alpha \ket{00} + \beta \ket{10} + \gamma \ket{01} + \delta \ket{11}
\end{eqnarray}

・まずは、最も扱いが容易な$\ket{11}$の位相を反転させる。これはCZゲート(controlled-Z)により実現できる。CZゲートは制御ゲートが$\ket{1}$の場合にZゲートを作用させる。量子回路で示すと、

選択的反転(CZゲート)により状態$\ket{3}=\ket{11}$の位相が反転していることがわかる。 また、CZゲートはアダマールゲートとCNOTゲートの組み合わせでも実現できる。

・次に、$\ket{11}$以外、例えば$\ket{00}$の位相を反転させたい場合。まずは$\ket{00}$を$\ket{11}$と入れ替える(1,2番目qubitに対してNOTゲートを作用させる)。この後、上で見た方法で$\ket{11}$の位相を反転する。再び$\ket{00}$と$\ket{11}$と入れ替えることで、無事$\ket{00}$の位相が反転した状態が得られる。他の固有状態についても同様である。

以下にQCEngineで使用したコードを示す。

// |φ>の作成
qc.reset(2);
var a = qint.new(2, 'a');
a.write(0);
a.hadamard();
qc.nop();

// CZゲート ver1
/*qc.codeLabel('選択的反転');
a.phase(180);
qc.codeLabel('');*/

// CZゲート ver2
/*qc.codeLabel('選択的反転');
qc.hadamard(1);
qc.cnot(1, 2)
qc.hadamard(1);
qc.codeLabel('');*/

// |00>を反転
qc.codeLabel('選択的反転');
a.not();
qc.hadamard(1);
qc.cnot(1, 2)
qc.hadamard(1);
a.not();
qc.codeLabel('');

2.平均値周りで反転

平均値周りでの反転操作は次のような演算子で表現されるものであった。

\begin{eqnarray}
\hat{D} \equiv -\hat{1} + 2\ket{\phi_0}\bra{\phi_0}
\end{eqnarray}

$\ket{\phi_0} = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \ket{x}$は全ての固有状態が等しく重ね合わさった状態であり、次のように$\ket{0}$状態にアダマールゲートを全qubitに作用させることで作成可能である。

この操作をユニタリ演算子$\hat{U}$と表現すれば、

\begin{eqnarray}
\ket{\phi_0} = \hat{U} \ket{0}
\end{eqnarray}

となるので、

\begin{eqnarray}
\hat{D} &=& -\hat{1} + 2\ket{\phi_0}\bra{\phi_0} \\
&=& -\hat{1} + 2 \hat{U} \ket{0} \bra{0} \hat{U}^{\dagger} \\
&=& -\hat{U} (\hat{1} - 2\ket{0} \bra{0}) \hat{U}^{\dagger}
\end{eqnarray}

ユニタリ演算子に挟まれた$\hat{1} - 2\ket{0} \bra{0}$の部分は、選択的反転で扱った演算子そのものである。つまり、$\ket{0}$の位相を反転する演算子である。この演算子に対応する量子ゲートは先程見たとおりである。
(この辺の参照元 : https://whyitsso.net/physics/quantum_mechanics/AA_AE_Grover.html)

以上のアダマールゲートと選択的反転を組み合わせることで、演算子$\hat{D}$の操作に対応する量子回路が作成できる。

以下にQCEngineで使用したコードを示す。

// |φ>の作成
qc.reset(2);
var a = qint.new(2, 'a');
a.write(0);
a.hadamard();
qc.nop();

// |00>を反転
qc.codeLabel('選択的反転');
a.not();
a.phase(180);
a.not();
qc.codeLabel('');

qc.nop();
qc.codeLabel('Grover');
a.Grover();

計算量について

・より一般のGroverアルゴリズム
ここまではN状態から一つの正解を探索するような場合に限定して考えていたが、より一般的な場合のGroverアルゴリズムを示す。そしてそのGroverアルゴリズムの計算ステップが$\mathcal{O}(\sqrt{N})$となることを確認する。
全状態$\ket{\psi}$について、探索したい対象の固有状態によって張られる部分空間$\ket{\psi_1}$、それ以外の部分空間$\ket{\psi_0}$とすると、

\begin{eqnarray}
\ket{\psi} &=& \cos \theta \ket{\psi_0} + \sin \theta \ket{\psi_1} 
\end{eqnarray}

のように表記出来る。係数として$\cos \theta, \sin \theta$を用いた(本来は複素振幅であるがとりあえず)。
選択的反転操作$\hat{R}_f$は$\ket{\psi_1}$の位相を反転させるものであり、反転操作を新たに$\hat{D}=-\hat{1} + 2\ket{\psi}\bra{\psi}$のように定義する。

この時、$\ket{\psi}$に対するGroverアルゴリズムは、次のような図で表すことが出来る。(もはや反転操作は平均値周りでの位相反転では無くなっているので注意。このような位相の回転に対応することの証明は後に示す。)

操作後$\ket{\psi}$は$\ket{\psi_1}$方向に$2\theta$だけ回転している。この操作によって$\theta \rightarrow 3\theta$へと変化し、これを$k$回繰り返すと$(2k+1)\theta$となる。

\begin{eqnarray}
\ket{\psi} &=& \cos ((2k+1)\theta) \ket{\psi_0} + \sin ((2k+1)\theta) \ket{\psi_1} 
\end{eqnarray}

$\ket{\psi_1}$の観測確率が1に近づくのは、

\begin{eqnarray}
(2k+1)\theta\simeq\frac{\pi}{2}
\end{eqnarray}

つまり

\begin{eqnarray}
k \simeq \frac{\pi}{4\theta}-\frac{1}{2}
\end{eqnarray}

の時。Nが十分に大きい時、$\sin \theta$は小さい値を取るので$\sin \theta \simeq \theta$と近似して、$\theta \simeq \frac{1}{\sqrt{N}}$。よって、

\begin{eqnarray}
k &\simeq& \frac{\pi \sqrt{N}}{4}-\frac{1}{2} \\
&=& \mathcal{O} (\sqrt{N})
\end{eqnarray}

よって計算ステップ数Nが$\mathcal{O} (\sqrt{N})$のオーダーであることがわかった。 (このあたりの参照元)

・Groverアルゴリズムが位相平面上の回転操作に対応することの幾何学的証明

$\hat{R}_f$は$\ket{\psi_1}$の位相を反転させるので、$\hat{R}_f \ket{\psi}$は$\ket{\psi_0}$の軸に関して反転したものになる。

$2\ket{\psi}\bra{\psi} \hat{R}_f\ket{\psi}$は$\hat{R}_f \ket{\psi}$を$\ket{\psi}$に射影したベクトル$\ket{\psi}\bra{\psi} \hat{R}_f\ket{\psi}$を2倍に引き伸ばしたものになる。

さらに$-\hat{R}_f\ket{\psi}$すると、$(-\hat{1} + 2\ket{\psi}\bra{\psi}) \ket{\psi}$となる。上図の大きな四角形は全辺の長さが等しいひし形になっている。よって角度については、対角線にあたる$\ket{\psi}$を挟んで対称的に$2\theta$となり図のようになる

・Groverアルゴリズムが位相平面上の回転操作に対応することの数学的証明
係数が複素数の場合に拡張し、上の議論が成立することを確認する。

\begin{eqnarray}
\ket{\psi} &=& \alpha \ket{\psi_0} + \beta e^{i \phi} \ket{\psi_1} \\
&=& 
\begin{pmatrix}
\alpha  \\
\beta e^{i \phi} 
\end{pmatrix}
\end{eqnarray}

選択的反転操作$\hat{R}_f$は$\ket{\psi_1}$の位相を反転させるので、行列表記は

\begin{eqnarray}
\hat{R}_f &=& 
\begin{pmatrix}
1 & 0  \\
0 & -1
\end{pmatrix}
\end{eqnarray}

のように書ける。
平均値周りの反転操作$\hat{D}$は、

\begin{eqnarray}
\hat{D} &=& -\hat{1} + 2\ket{\psi}\bra{\psi} \\
&=& -\hat{1} + 2 (\alpha \ket{\psi_0} + \beta e^{i \phi} \ket{\psi_1}) (\alpha \bra{\psi_0} + \beta e^{-i \phi} \bra{\psi_1}) \\
&=& -\hat{1} + 2\alpha^2\ket{\psi_0}\bra{\psi_0} + 2\beta^2\ket{\psi_1}\bra{\psi_1} + 2\alpha\beta e^{-i \phi} \ket{\psi_0}\bra{\psi_1} + 2\alpha\beta e^{i \phi} \ket{\psi_1}\bra{\psi_0} \\
&=& \begin{pmatrix}
2\alpha^2-1 & 2\alpha\beta e^{-i \phi}  \\
2\alpha\beta e^{i \phi} & 2\beta^2-1
\end{pmatrix}
\end{eqnarray}

よって、$k$回の操作を行った場合、状態は

\begin{eqnarray}
(\hat{D} \hat{R}_f)^k \ket{\psi} &=& 
\begin{pmatrix}
2\alpha^2-1 & 2\alpha\beta e^{-i \phi}  \\
2\alpha\beta e^{i \phi} & 2\beta^2-1
\end{pmatrix}^k
\begin{pmatrix}
1 & 0  \\
0 & -1
\end{pmatrix}^k
\begin{pmatrix}
\alpha  \\
\beta e^{i \phi} 
\end{pmatrix}\\
&=&
\begin{pmatrix}
2\alpha^2-1 & -2\alpha\beta e^{-i \phi}  \\
2\alpha\beta e^{i \phi} & -2\beta^2+1
\end{pmatrix}^k
\begin{pmatrix}
\alpha  \\
\beta e^{i \phi} 
\end{pmatrix}\\
\end{eqnarray} 

行列

\begin{eqnarray}
\begin{pmatrix}
2\alpha^2-1 & -2\alpha\beta e^{-i \phi}  \\
2\alpha\beta e^{i \phi} & -2\beta^2+1
\end{pmatrix}
\end{eqnarray} 

の固有値・固有ベクトルは、

\begin{eqnarray}
\lambda_{\pm} &=& \cos 2\theta + i \sin 2\theta = e^{\pm2i\theta} \\
\ket{\psi_{\pm}} &=& \frac{1}{\sqrt2} 
\begin{pmatrix}
1 \\
\mp i e^{i \phi}
\end{pmatrix}
= \frac{1}{\sqrt2} (\ket{\psi_0} \mp i e^{i\phi} \ket{\psi_1})
\end{eqnarray}

固有ベクトルの線形結合で$\ket{\psi}$を表すと、

\begin{eqnarray}
\ket{\psi} &=& \frac{1}{\sqrt2} (e^{i\theta} \ket{\psi_{+}} + e^{-i\theta} \ket{\psi_{-}})
\end{eqnarray} 

よって、

\begin{eqnarray}
(\hat{D} \hat{R}_f)^k \ket{\psi} &=& (\hat{D} \hat{R}_f)^k \frac{1}{\sqrt2} (e^{i\theta} \ket{\psi_{+}} + e^{-i\theta} \ket{\psi_{-}}) \\
&=& \frac{1}{\sqrt2} (e^{i(2k+1)\theta} \ket{\psi_{+}} + e^{-i(2k+1)\theta} \ket{\psi_{-}}) \\
&=& \cos (2n+1)\theta \ket{\psi_0} + e^{i\phi} \sin (2n+1)\theta \ket{\psi_1} 
\end{eqnarray} 

これで、係数が実数の場合と同じ考察を行うことが出来、計算ステップが$\mathcal{O} (\sqrt{N})$であることが示される。 (このあたりの参照元)