確率振幅の増幅

投稿者: | 2017年6月8日

 

概要

  • グローバー回転のように特定の状態の振幅を強める方法
  • より回転のイメージが持ちやすい形式で一般化

動機

グローバーアルゴリズムの記事では、アルゴリズムの大まかな動きを追うために、グローバー回転の回転のイメージの説明は省略しました。 今回は、グローバー回転のように特定の状態の振幅を強める方法をより一般的な形で定式化した amplitude amplification を紹介します。 amplitude amplification では回転の考えが自然と入ってくるので、グローバー回転のイメージの補強にも役立ちます。

\[
\newcommand\ket[1]{|{#1}\rangle}
\newcommand\bra[1]{\langle{#1}|}
\newcommand{\bracket}[2]{\left\langle #1 \middle|#2 \right\rangle}
\]

定義


ヒルベルト空間 \(\mathcal{H}\) 上の \(N\) 個の直行する基底 \(\ket{i}\) を考える。 \(\mathcal{H}\) 上のある重ね合わせ状態を \(\ket{\psi}\)とする、 この時、0,1 の二値を取る関数 \(\chi(i)\) について、\(\chi(i) = 1\) を満たすような \(i\) の確率振幅を選択的に増幅する演算子を \[
Q = S_\psi S_\chi
\]
で定義する。 ただし、 \[
\begin{align}
S_\psi &= 2\ket{\psi}\bra{\psi} – I \\
S_\chi &= I – 2 P_\chi
\end{align}
\]
\(P_\chi\)\(\chi(i)=1\) である部分空間への射影で \[
P_\chi = \sum_{\chi(i)=1} \ket{i}\bra{i}
\]
である。

\(Q\) による回転

\(Q\) はユニタリ変換なので、ある種の回転ですが、 どのような回転を表すのでしょうか。 回転を特徴づけるには、

  • どこ回りの回転なのか(回転の方向)
  • 何度の回転なのか(回転の大きさ)

が重要となります。

回転の方向

回転の方向を考える前に、ヒルベルト空間 \(\mathcal{H}\)\(\chi(i)=1\) の条件を満たすものと満たさないものに分けることを考えてみましょう。 これは、直交基底 \(\ket{i}\) を二つのグループに分けられて、直交した部分空間を定めます。 \[
\mathcal{H}_0 = {\rm span}(\{ \ket{i} ; \ \chi(i)=1 \}) \\
\mathcal{H}_1 = {\rm span}(\{ \ket{i} ;\ \chi(i) = 0 \})
\]
そのため、\(\ket{\psi} \in \mathcal{H}\)は、\(\ket{\psi_0} \in \mathcal{H_0}, \ket{\psi_1} \in \mathcal{H_1}\) を用いて \[
\ket{\psi} = \alpha \ket{\psi_1} + \beta \ket{\psi_0}
\]
と表すことができます。

実は、\(Q\) による回転は、この \(\ket{\psi_0}\)\(\ket{\psi_1}\) を行き来する回転で、 確率振幅 \(\alpha,\beta\)\(Q\) によって変化します。

初期状態の \(\alpha, \beta\) を位相 \(\theta\) を用いて表すことにして、 \[
\ket{\psi} = \sin(\theta) \ket{\psi_1} + \cos(\theta) \ket{\psi_0}
\]
のように書き直しておきます。

回転の大きさ

それでは、実際に \(\ket{\psi}\)\(Q\) を作用させて回転の大きさを調べてみます。

\(\psi_1, \psi_0\)を基底とすれば、 \[
\begin{align}
\ket{\psi} \bra{\psi} = \pmatrix{
\sin^2\theta & \sin\theta\cos\theta \\
\sin\theta \cos\theta & \cos^2\theta
}
\end{align}
\]
であり、 \[
\begin{align}
S_\psi &= \pmatrix{
2\sin^2\theta – 1 & 2\sin\theta\cos\theta \\
2\sin\theta\cos\theta & 2\cos^2\theta – 1
}\\
&= \pmatrix{
-\cos2\theta & \sin2\theta \\
\sin2\theta & \cos2\theta
}
\end{align}
\]

\(\ket{\psi_1}, \ket{\psi_0}\) について考えると、 \[
\begin{align}
Q \ket{\psi_1} &= – S_\psi \ket{\psi_1}
= \cos2\theta \ket{\psi_1} – \sin2\theta \ket{\psi_0} \\
Q \ket{\psi_0} &= S_\psi \ket{\psi_0}
= \sin2\theta \ket{\psi_1} + \cos2\theta \ket{\psi_0}
\end{align}
\]
であるから、 \[
Q = \pmatrix{
\cos2\theta & -\sin2\theta \\
\sin2\theta & \cos2\theta}
\]
であり、これは \(Q\) が角度 \(2\theta\) の回転であることを示しています。

それでは、実際に数値的に回転の様子を見てみることにします。 ブロッホ球のプロットを使って、量子状態を矢印で表示しています。 \(R\) による回転を 10 回行っていて、黄色い矢印から、赤の矢印に向かって回転が進んでいっています。 初期状態として \(\ket{\psi_0}=\ket{0}\) の振幅が大きい状態から始まって、\(\ket{\psi_1} = \ket{1}\) の振幅が大きい状態へと移っており、\(\ket{\psi_1}\) の振幅が増大されている様子が分かります。 このまま、さらに回転を続けると、もとに戻ってきます。

グローバーアルゴリズムとの関係

グローバーアルゴリズムでも、まさに同じ回転が使われています。

\(R\) の回転角の大きさは初期状態の \(\ket{\psi_0}, \ket{\psi_1}\) の重ね合わせの度合い \(\theta\) によって決まります。 グローバーアルゴリズムの場合、初期状態は、探索するデータベースの全ての番号 \(\ket{i}\) の均等な重ね合わせでした。 そして、\(\ket{\psi_0},\ket{\psi_1}\) は探索対象でない番号と、探索対象である番号を表します。 もし、探索しているデータがデータベース中に一つしかなければ、初期状態は \(\ket{\psi_0}\) に偏っており、 \(\theta\) は 0 に近い値となります。 特に、データベースのサイズが大きいほど、この偏りは大きく、\(\theta\) は小さくなります。

\(\theta\) が小さい、つまり回転角が小さいと、適切な回数だけ回転をさせた時に \(\ket{\psi_1}\) により近い状態に持っていくことができます。 一歩が大きすぎると狙った所に止まるのは難しいですよね。 グローバーアルゴリズムでは、最後は観測によって確率的に \(\ket{\psi_1}\) を得ないと探索が失敗になってしまうので、 \(\ket{\psi_1}\) に近づけるように回転できると探索の成功率が上がります。 つまり、データベースのサイズが大きい方が、(適切な回転回数のもとで)グローバーアルゴリズムの探索成功率は高くなると言えます。


 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です