振幅増幅

振幅増幅は量子コンピューティングの技術であり、グローバーの探索アルゴリズムの背後にあるアイデアを一般化し、一連の量子アルゴリズムを生み出した。これは1997年にジル・ブラッサードとピーター・ホイヤーによって発見され、 ^[1] 1998年にロブ・グローバーによって独立に再発見された。^[2]

量子コンピュータでは、振幅増幅を使用することで、いくつかの従来のアルゴリズムに比べて 2 倍の高速化を実現できます。

ここで示す導出は、2000年にBrassardらが示したものとほぼ同様である。^[3]量子系の状態空間を表す次元ヒルベルト空間 があり、その空間は正規直交計算基底状態によって張られているとする。さらに、エルミート射影演算子があるとする。あるいは、ブールオラクル関数 と正規直交演算基底 によって与えられる場合もあり、その場合、 ${\displaystyle N}$ ${\displaystyle {\mathcal {H}}}$${\displaystyle B:=\{|k\rangle \}_{k=0}^{N-1}}$ ${\displaystyle P\colon {\mathcal {H}}\to {\mathcal {H}}}$${\displaystyle P}$${\displaystyle \chi \colon \mathbb {Z} \to \{0,1\}}$${\displaystyle B_{\text{op}}:=\{|\omega _{k}\rangle \}_{k=0}^{N-1}}$

${\displaystyle P:=\sum _{\chi (k)=1}|\omega _{k}\rangle \langle \omega _{k}|}$。

${\displaystyle P}$は、互いに直交する 2 つの部分空間、つまり良好な部分空間と不良な部分空間の直和に分割するために使用できます。言い換えると、射影子 を介して「良好な部分空間」を定義しています。アルゴリズムの目標は、ある初期状態をに属する状態に進化させることです。 ${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {H}}_{1}}$${\displaystyle {\mathcal {H}}_{0}}$$${\displaystyle {\begin{aligned}{\mathcal {H}}_{1}&:={\text{Image}}\;P&=\operatorname {span} \{|\omega _{k}\rangle \in B_{\text{op}}\;|\;\chi (k)=1\},\\{\mathcal {H}}_{0}&:={\text{Ker}}\;P&=\operatorname {span} \{|\omega _{k}\rangle \in B_{\text{op}}\;|\;\chi (k)=0\}.\end{aligned}}}$$${\displaystyle {\mathcal {H}}_{1}}$${\displaystyle P}$${\displaystyle |\psi \rangle \in {\mathcal {H}}}$${\displaystyle {\mathcal {H}}_{1}}$

両方の部分空間と重なりがゼロでない正規化された状態ベクトルが与えられた場合、それを次のように一意に分解できる。 ${\displaystyle |\psi \rangle \in {\mathcal {H}}}$

${\displaystyle |\psi \rangle =\sin(\theta )|\psi _{1}\rangle +\cos(\theta )|\psi _{0}\rangle }$、

ここで、、、 はそれぞれ、 との部分空間への正規化された射影です 。この分解により、ベクトル とによって張られる2 次元の部分空間が定義されます 。測定時にシステムが良好な状態にある確率はです。 ${\displaystyle \theta =\arcsin \left(\left|P|\psi \rangle \right|\right)\in [0,\pi /2]}$${\displaystyle |\psi _{1}\rangle }$${\displaystyle |\psi _{0}\rangle }$${\displaystyle |\psi \rangle }$${\displaystyle {\mathcal {H}}_{1}}$${\displaystyle {\mathcal {H}}_{0}}$${\displaystyle {\mathcal {H}}_{\psi}}$${\displaystyle |\psi _{0}\rangle }$${\displaystyle |\psi _{1}\rangle }$${\displaystyle \sin^{2}(\theta )}$

ユニタリ演算子を定義する。ここで ${\displaystyle Q(\psi,P):=-S_{\psi}S_{P}\,\!}$

${\displaystyle {\begin{aligned}S_{\psi }&=I-2|\psi \rangle \langle \psi |\quad {\text{and}}\\S_{P}&=I-2P.\end{aligned}}}$

${\displaystyle S_{P}}$良好な部分空間内の状態の位相を反転しますが、 初期状態の位相を反転します。 ${\displaystyle S_{\psi}}$${\displaystyle |\psi \rangle }$

この演算子の作用は次のように表される 。${\displaystyle {\mathcal {H}}_{\psi}}$

${\displaystyle Q|\psi _{0}\rangle =-S_{\psi }|\psi _{0}\rangle =(2\cos ^{2}(\theta )-1)|\psi _{ 0}\rangle +2\sin(\theta )\cos(\theta )|\psi _{1}\rangle }$そして

${\displaystyle Q|\psi _{1}\rangle =S_{\psi }|\psi _{1}\rangle =-2\sin(\theta )\cos(\theta )|\psi _{0} \rangle +(1-2\sin ^{2}(\theta ))|\psi _{1}\rangle }$。

したがって、部分空間では角度による回転に対応します。 ${\displaystyle {\mathcal {H}}_{\psi}}$${\displaystyle Q}$${\displaystyle 2\theta \,\!}$

${\displaystyle Q={\begin{pmatrix}\cos(2\theta )&-\sin(2\theta )\\\sin(2\theta )&\cos(2\theta )\end{pmatrix}} }$。

状態に時間を 適用すると 、 ${\displaystyle Q}$ ${\displaystyle n}$${\displaystyle |\psi \rangle }$

${\displaystyle Q^{n}|\psi \rangle =\cos((2n+1)\theta )|\psi _{0}\rangle +\sin((2n+1)\theta )|\psi _{1}\rangle }$、

状態を良い部分空間と悪い部分空間の間で回転させる。反復後、システムが良好な状態にある確率は である。確率は、以下を選択した場合に最大化される。 ${\displaystyle n}$${\displaystyle \sin^{2}((2n+1)\theta )\,\!}$

${\displaystyle n=\left\lfloor {\frac {\pi }{4\theta }}\right\rfloor }$。

この時点まで、各反復で良好な状態の振幅が増加するため、この手法の名前が付けられています。

簡単にするために、N 個の要素を持つソートされていないデータベースと、検索している適切なエントリを認識できるOracle 関数が あると仮定します。 ${\displaystyle \chi}$${\displaystyle B_{\text{op}}=B}$

データベースに良いエントリが全部ある場合、量子レジスタを量子ビットで初期化することで、データベースのすべての要素を均一に重ね合わせ、 ${\displaystyle G}$ ${\displaystyle |\psi \rangle }$${\displaystyle n}$ ${\displaystyle 2^{n}=N}$${\displaystyle N}$

${\displaystyle |\psi \rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}|k\rangle }$

そして、上記のアルゴリズムを実行します。この場合、初期状態と良好な部分空間の重なりは、データベース内の良好なエントリの頻度の平方根に等しくなります。 の場合、必要な反復回数は次のように近似できます。 ${\displaystyle \sin(\theta )=|P|\psi \rangle |={\sqrt {G/N}}}$${\displaystyle \sin(\theta )\ll 1}$

${\displaystyle n=\left\lfloor {\frac {\pi }{4\theta }}\right\rfloor \approx \left\lfloor {\frac {\pi }{4\sin(\theta )}}\right\rfloor =\left\lfloor {\frac {\pi }{4}}{\sqrt {\frac {N}{G}}}\right\rfloor =O({\sqrt {N}}).}$

状態を測定すると、高い確率で適切なエントリの 1 つが得られます。 の各アプリケーションには単一のオラクル クエリが必要であるため (オラクルが量子ゲートとして実装されていると仮定)、オラクル クエリだけで適切なエントリを見つけることができ、最良の従来型アルゴリズムに比べて 2 倍の高速化が得られます。 (データベースを検索する従来の方法は、ソリューションが見つかるまですべてのクエリを実行することであり、クエリのコストがかかります。) さらに、クエリを使用してすべてのソリューションを見つけることができます。 ${\displaystyle S_{P}}$${\displaystyle O({\sqrt {N}})}$${\displaystyle e\in \{0,1,\dots ,N-1\}}$${\displaystyle O(N)}$${\displaystyle G}$${\displaystyle O({\sqrt {GN}})}$

セットのサイズを1 に設定すると、上記のシナリオは基本的に元のGrover 検索に縮小されます。 ${\displaystyle G}$

有効なエントリの数が未知であると仮定します。が小さい場合、となることを推定することを目標とします。 は、ユニタリ演算子 に量子位相推定アルゴリズムを適用することで解くことができます。 ${\displaystyle {\tilde {G}}}$${\displaystyle (1-\delta )G\leq {\tilde {G}}\leq (1+\delta )G}$${\displaystyle \delta >0}$${\displaystyle {\tilde {G}}}$${\displaystyle Q}$

と はの唯一の 2 つの固有値であるため、それらの対応する固有ベクトルを およびとすることができます。の固有値を求めることができますが、これはこの場合、位相 を推定することと同等です。これは、量子位相推定アルゴリズムで説明されているように、フーリエ変換と制御されたユニタリ演算を適用することで実行できます。 を推定すると、 を推定でき、これは を推定します。 ${\displaystyle e^{2i\theta }}$${\displaystyle e^{-2i\theta }}$${\displaystyle Q}$${\displaystyle |\psi _{1}\rangle }$${\displaystyle |\psi _{2}\rangle }$${\displaystyle e^{2i\theta }}$${\displaystyle |\psi \rangle }$${\displaystyle \theta }$${\displaystyle {\tilde {\theta }}}$${\displaystyle \sin {\theta }}$${\displaystyle G}$

固有ベクトルとの代わりに、任意の開始状態 で推定したいとします。これは、との線形結合に分解し、位相推定アルゴリズムを適用すること で実行できます。${\displaystyle \theta }$${\displaystyle |s\rangle }$${\displaystyle |\psi _{1}\rangle }$${\displaystyle |\psi _{2}\rangle }$${\displaystyle |s\rangle }$${\displaystyle |\psi _{1}\rangle }$${\displaystyle |\psi _{2}\rangle }$