Skip to main content
IBM Quantum Platform

解析

では、グローバーのアルゴリズムを分析し、その仕組みを理解しよう。 私たちはまず、グローバー演算（ 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 -bit文字列にわたる一様な量子状態と定義しよう：

∣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}

そうすると

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

すべての文字列 x∈Σnx\in\Sigma^n について、したがって

Zg=−Zf.Z_g = - Z_f.

つまり、関数 ff を関数 gg に置き換えたとしても、グローバーのアルゴリズムの動作に何の違いも生じないということになる。なぜなら、どちらの場合でも、このアルゴリズムから得られる状態は、全相位を除けば必然的に等価であるからである。

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

グローバー作戦の行動

それでは、量子状態ベクトル ∣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},

上記で、すべての nn ビット文字列にわたる一様な重ね合わせについて用いたのと同じ表記、 ∣u⟩\vert u \rangle を用いる。

これで、 GG が ∣A0⟩\vert A_0\rangle および ∣A1⟩\vert A_1\rangle に及ぼす作用を計算するために必要なものが揃いました。 まず、 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行目／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と呼びます) に関する鏡映です。以下は、この鏡映が仮想的な単位ベクトル∣ψ⟩\vert\psi\rangleに及ぼす作用を示す図です。この単位ベクトルは、 ∣A0⟩\vert A_0\rangleと∣A1⟩\vert A_1\rangleの実数線形結合であると仮定しています。

ベクトルに対する反射の作用を表した図。

次に、 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 に対するこの反射の作用を示した図を示します。

ベクトルに対する2回目の反射の作用を表した図。

これらの2つの反射を合成すると、この図が示すように、反射線間の角度の2倍の回転が得られる。

ベクトルに対するグローバー演算の作用を表した図。

これは、幾何学的な観点から、グローバー演算の効果が、 ∣A0⟩\vert A_0\rangle および ∣A1⟩\vert A_1\rangle の線形結合を 2θ2\theta の角度だけ回転させるものである理由を説明している。

このページは役に立ちましたか？
バグや誤字の報告、またはコンテンツの要求はGitHubで行ってください。