メインコンテンツへスキップ

解析

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

解と非解​

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

A0={x∈Σn:f(x)=0}A1={x∈Σn:f(x)=1}\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}

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

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

∣A0⟩=1∣A0∣∑x∈A0∣x⟩∣A1⟩=1∣A1∣∑x∈A1∣x⟩\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}

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

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

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

∣u⟩=1N∑x∈Σn∣x⟩.\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.

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

∣u⟩=∣A0∣N∣A0⟩+∣A1∣N∣A1⟩.\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.

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

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

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

次に、グローバー操作

G=H⊗nZORH⊗nZf,G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,

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

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

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

すべての文字列 x∈Σnx\in\Sigma^n に対して

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

が成り立つことに注意してください。したがって

Zg=−Zf.Z_g = - Z_f.

つまり、関数 ff を関数 gg に置き換えてもグローバーのアルゴリズムは何も変わりません。なぜなら、2 つの場合においてアルゴリズムから得られる状態は必然的に全体位相の違いを除いて同等だからです。

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

グローバー操作の作用​

では、量子状態ベクトル ∣A0⟩\vert A_0\rangle と ∣A1⟩\vert A_1\rangle に対する GG の作用を考えましょう。

まず、操作 ZfZ_f が ∣A0⟩\vert A_0\rangle と ∣A1⟩\vert A_1\rangle に非常に単純な作用をすることを観察します。

Zf∣A0⟩=∣A0⟩Zf∣A1⟩=−∣A1⟩\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⊗nZORH⊗nH^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} を考えます。 操作 ZORZ_{\mathrm{OR}} は次のように定義されます。

ZOR∣x⟩={∣x⟩x=0n−∣x⟩x≠0n,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∈Σnx\in\Sigma^n のすべての文字列について成り立ちます。この操作を表す便利な別の書き方は次の通りです。

ZOR=2∣0n⟩⟨0n∣−I.Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.

この式が ZORZ_{\mathrm{OR}} の定義と一致することを確認するには、標準基底状態への作用を評価すれば十分です。

したがって、操作 H⊗nZORH⊗nH^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} は次のように書けます。

H⊗nZORH⊗n=2H⊗n∣0n⟩⟨0n∣H⊗n−I=2∣u⟩⟨u∣−I,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},

ここで、∣u⟩\vert u \rangle はすべての nn ビット文字列上の一様重ね合わせを表す上記の記法と同じです。

これで ∣A0⟩\vert A_0\rangle と ∣A1⟩\vert A_1\rangle に対する GG の作用を計算する準備が整いました。 まず、GG の ∣A0⟩\vert A_0\rangle への作用を計算します。

G∣A0⟩=(2∣u⟩⟨u∣−I)Zf∣A0⟩=(2∣u⟩⟨u∣−I)∣A0⟩=2∣A0∣N∣u⟩−∣A0⟩=2∣A0∣N(∣A0∣N∣A0⟩+∣A1∣N∣A1⟩)−∣A0⟩=(2∣A0∣N−1)∣A0⟩+2∣A0∣⋅∣A1∣N∣A1⟩=∣A0∣−∣A1∣N∣A0⟩+2∣A0∣⋅∣A1∣N∣A1⟩\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}

次に、GG の ∣A1⟩\vert A_1\rangle への作用を計算します。

G∣A1⟩=(2∣u⟩⟨u∣−I)Zf∣A1⟩=−(2∣u⟩⟨u∣−I)∣A1⟩=−2∣A1∣N∣u⟩+∣A1⟩=−2∣A1∣N(∣A0∣N∣A0⟩+∣A1∣N∣A1⟩)+∣A1⟩=−2∣A1∣⋅∣A0∣N∣A0⟩+(1−2∣A1∣N)∣A1⟩=−2∣A1∣⋅∣A0∣N∣A0⟩+∣A0∣−∣A1∣N∣A1⟩\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}

どちらの計算でも、次の等式

∣u⟩=∣A0∣N∣A0⟩+∣A1∣N∣A1⟩\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

と、そこから導かれる

⟨u∣A0⟩=∣A0∣Nand⟨u∣A1⟩=∣A1∣N\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}}

を使用しています。

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

G∣A0⟩=∣A0∣−∣A1∣N∣A0⟩+2∣A0∣⋅∣A1∣N∣A1⟩G∣A1⟩=−2∣A1∣⋅∣A0∣N∣A0⟩+∣A0∣−∣A1∣N∣A1⟩.\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 の直前における Q\mathsf{Q} の状態は ∣A0⟩\vert A_0\rangle と ∣A1⟩\vert A_1\rangle によって張られる 2 次元空間に含まれており、GG がこの空間内の任意のベクトルを同じ空間内の別のベクトルに写すことを確認しました。 したがって、解析の目的上、この部分空間だけに注目すれば十分です。

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

M=(∣A0∣−∣A1∣N−2∣A1∣⋅∣A0∣N2∣A0∣⋅∣A1∣N∣A0∣−∣A1∣N),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 番目はそれぞれ ∣A0⟩\vert A_0\rangle と ∣A1⟩\vert A_1\rangle に対応します。 このシリーズのこれまでの部分では、行列の行と列は常にシステムの古典状態と関連付けてきましたが、行列はここで示しているように異なる基底上の線形写像の作用を記述するためにも使用できます。

一見すると全く明らかではありませんが、行列 MM はより単純な形の行列を2 乗することで得られます。

(∣A0∣N−∣A1∣N∣A1∣N∣A0∣N)2=(∣A0∣−∣A1∣N−2∣A1∣⋅∣A0∣N2∣A0∣⋅∣A1∣N∣A0∣−∣A1∣N)=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}^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

この行列

(∣A0∣N−∣A1∣N∣A1∣N∣A0∣N)\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}

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

(∣A0∣N−∣A1∣N∣A1∣N∣A0∣N)=(cos⁡(θ)−sin⁡(θ)sin⁡(θ)cos⁡(θ))\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}

ここで

θ=sin⁡−1(∣A1∣N).\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr).

この角度 θ\theta は以降の解析において非常に重要な役割を果たすため、初めて登場するここでその重要性を強調しておきます。

この行列の表現に照らして、次が観察されます。

M=(cos⁡(θ)−sin⁡(θ)sin⁡(θ)cos⁡(θ))2=(cos⁡(2θ)−sin⁡(2θ)sin⁡(2θ)cos⁡(2θ)).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θ2\theta による回転と同等であるためです。 別の見方としては、

θ=cos⁡−1(∣A0∣N),\theta = \cos^{-1}\biggl(\sqrt{\frac{\vert A_0\vert}{N}}\biggr),

という別の表現と、三角法の倍角公式を利用することもできます。

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

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

∣u⟩=∣A0∣N∣A0⟩+∣A1∣N∣A1⟩=cos⁡(θ)∣A0⟩+sin⁡(θ)∣A1⟩,\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,

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

G∣u⟩=cos⁡(3θ)∣A0⟩+sin⁡(3θ)∣A1⟩G2∣u⟩=cos⁡(5θ)∣A0⟩+sin⁡(5θ)∣A1⟩G3∣u⟩=cos⁡(7θ)∣A0⟩+sin⁡(7θ)∣A1⟩\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}

一般には

Gt∣u⟩=cos⁡((2t+1)θ)∣A0⟩+sin⁡((2t+1)θ)∣A1⟩.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.

幾何学的な図​

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

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

Zf∣A0⟩=∣A0⟩Zf∣A1⟩=−∣A1⟩.\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}

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

A figure depicting the action of a reflection on a vector.

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

H⊗nZORH⊗n=2∣u⟩⟨u∣−I.H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.

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

A figure depicting the action of a second reflection on a vector.

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

A figure depicting the action of the Grover operation on a vector.

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