解析

グローバーのアルゴリズムを解析して、その仕組みを理解しましょう。 まず、記号的解析と呼べるものから始めます。ここではグローバー操作 $G$ がある状態にどのように作用するかを計算し、その後、この記号的解析をアルゴリズムの動作を視覚化するのに役立つ幾何学的な図と結び付けます。

解と非解

まず、2 つの文字列の集合を定義します。

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

集合 $A_1$ は探索問題のすべての解を含み、$A_0$ は解でない文字列（便宜上非解と呼ぶことがあります）を含みます。 これら 2 つの集合は $A_0 \cap A_1 = \varnothing$ および $A_0 \cup A_1 = \Sigma^n$ を満たします。すなわち、これは $\Sigma^n$ の二分割です。

次に、解の集合と非解の集合それぞれの上の一様重ね合わせを表す 2 つの単位ベクトルを定義します。

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

正確に言えば、これらのベクトルはそれぞれ対応する集合が空でない場合にのみ定義されますが、以降では $A_0$ も $A_1$ も空でない場合に焦点を当てます。 $A_0 = \varnothing$ および $A_1 = \varnothing$ の場合は別途容易に処理できるため、後ほど取り上げます。

なお、ここで使用している記法は一般的なものです。有限で空でない集合 $S$ があれば、$\vert S\rangle$ と書いて $S$ の要素上で一様な量子状態ベクトルを表すことができます。

また、$\vert u \rangle$ をすべての $n$ ビット文字列上の一様量子状態として定義します。

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

次の等式が成り立つことに注意してください。

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

また、$\vert u\rangle = H^{\otimes n} \vert 0^n \rangle$ が成り立つため、$\vert u\rangle$ はグローバーのアルゴリズムのステップ 1 における初期化後のレジスタ $\mathsf{Q}$ の状態を表します。

これは、ステップ 2 で $G$ の反復が始まる直前において、$\mathsf{Q}$ の状態が $\vert A_0\rangle$ と $\vert A_1\rangle$ によって張られる 2 次元ベクトル空間に含まれており、さらにこれらのベクトルの係数が実数であることを意味します。 これから分かるように、ステップ 2 の操作 $G$ を何回反復した後でも、$\mathsf{Q}$ の状態は常にこれらの性質を持ちます。すなわち、状態は $\vert A_0\rangle$ と $\vert A_1\rangle$ の実線形結合です。

グローバー操作についての観察

次に、グローバー操作

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

に注目し、その興味深い性質から始めましょう。

関数 $f$ を $f$ と NOT 関数の合成、すなわち $f$ の出力ビットを反転させた関数に置き換えたとします。 この新しい関数を $g$ と呼び、いくつかの記法で表すことができます。

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

次の等式が成り立つことに注意してください。

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

すべての文字列$x\in\Sigma^n$について成り立つので、したがって

$$Z_g = - Z_f.$$

これは、関数$f$を関数$g$に置き換えたとしても、Grover のアルゴリズムの動作は変わらないことを意味します——なぜなら、両方の場合においてアルゴリズムから得られる状態は必然的に大域位相を除いて等しいからです。

これは問題ではありません！ 直感的に言えば、アルゴリズムはどの文字列が解でどの文字列が解でないかを気にしません——正しく動作するためには、解と非解を区別できさえすればよいのです。

グローバー操作の作用

それでは、量子状態ベクトル $\vert A_0\rangle$ と $\vert A_1\rangle$ に対する $G$ の作用を考えてみましょう。

まず、演算$Z_f$が$\vert A_0\rangle$と$\vert A_1\rangle$に対して非常に単純な作用を持つことを見ておきましょう。

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

次に、演算$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$について見ていきます。 演算$Z_{\mathrm{OR}}$は次のように定義されます。

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[2mm] -\vert x\rangle & x \neq 0^n, \end{cases}$$

再びすべての文字列$x\in\Sigma^n$について成り立ち、この演算を表現する便利な別の方法は次のようになります。

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

この式が $Z_{\mathrm{OR}}$ の定義と一致することを確認する簡単な方法は、標準基底状態に対するその作用を評価することです。

したがって、演算$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$は次のように書くことができます。

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

上で$n$ビット文字列すべてにわたる一様重ね合わせに用いたのと同じ記法$\vert u \rangle$を使っています。

これで、$\vert A_0\rangle$と$\vert A_1\rangle$に対する$G$の作用を計算するために必要なものがそろいました。 まず、$\vert A_0\rangle$に対する$G$の作用を計算しましょう。

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

次に、$\vert A_1\rangle$に対する$G$の作用を計算しましょう。

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

どちらの場合も、次の式を使っています。

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

次の式とあわせて

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{and}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

まとめると、次が成り立ちます。

まとめると、次のようになります。

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

すでに述べたように、ステップ2の直前における$\mathsf{Q}$の状態は、$\vert A_0\rangle$と$\vert A_1\rangle$が張る2次元空間に含まれており、$G$がこの空間内の任意のベクトルを同じ空間内の別のベクトルへ写像することも確認しました。 これは、解析のためには、この部分空間だけに注目すればよいことを意味します。

この2次元空間内で何が起きているかをよりよく理解するために、この空間における$G$の作用を行列として表現してみましょう。

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

1列目と2列目（行）がそれぞれ$\vert A_0\rangle$と$\vert A_1\rangle$に対応しています。 このシリーズではこれまで、行列の行と列をシステムの古典状態と結びつけてきましたが、行列はここで見るように、異なる基底に対する線形写像の作用を記述するためにも使うことができます。

一見してまったく明らかではありませんが、行列$M$は、より単純に見える行列を2乗することで得られます。

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

行列

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

は回転行列であり、これは次のように表すこともできます。

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

for

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr).$$

この角度$\theta$は、この後の解析において非常に重要な役割を果たすことになるので、初めて登場するこの時点でその重要性を強調しておく価値があります。

この行列の表現から、次のことがわかります。

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

これは、角度$\theta$だけ2回回転することが、角度$2\theta$だけ回転することと等価であるためです。 これを見るもう一つの方法は、次の別の表現を利用することです。

$$\theta = \cos^{-1}\biggl(\sqrt{\frac{\vert A_0\vert}{N}}\biggr),$$

三角関数の倍角公式とあわせて

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

まとめると、ステップ2の開始時点でのレジスタ$\mathsf{Q}$の状態は

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

であり、この状態に $G$ を適用する効果は、$\vert A_0\rangle$ と $\vert A_1\rangle$ によって張られる空間内でその状態を角度 $2\theta$ だけ回転させることです。 たとえば、次が成り立ちます。

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

一般には

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle.$$

幾何学的な図

ここで、先ほどの解析を幾何学的な図と結び付けましょう。 操作 $G$ は 2 つの反射、すなわち $Z_f$ と $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ の積です。 そして 2 つの反射を合成した正味の効果は回転を行うことです。

まず $Z_f$ から始めます。 先ほど観察したように、次が成り立ちます。

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

$\vert A_0\rangle$ と $\vert A_1\rangle$ によって張られる 2 次元ベクトル空間内において、これは $\vert A_0\rangle$ に平行な直線 $L_1$ についての反射です。 次の図は、$\vert A_0\rangle$ と $\vert A_1\rangle$ の実線形結合と仮定した仮想的な単位ベクトル $\vert\psi\rangle$ に対するこの反射の作用を示しています。

次に操作 $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ を考えます。これは既に次のように書けることを見ました。

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

これもまた反射であり、今度はベクトル $\vert u\rangle$ に平行な直線 $L_2$ についての反射です。 次の図は単位ベクトル $\vert\psi\rangle$ に対するこの反射の作用を示しています。

これら 2 つの反射を合成すると回転が得られます。回転角は反射の軸の間の角度の 2 倍です。これを次の図が示しています。

これにより、グローバー操作の効果が $\vert A_0\rangle$ と $\vert A_1\rangle$ の線形結合を角度 $2\theta$ だけ回転させることである理由が幾何学的な観点から説明されます。