グローバーのアルゴリズム

投稿者: | 2017年6月7日

概要

  • データベース探索の量子アルゴリズムの一つであるグローバーアルゴリズムを紹介
  • 特にアルゴリズムの中核となるグローバー回転に焦点を当てて説明

データベース探索

一般的に、データベースは、番号とデータで表現されます。

1: 代数幾何, 2: 統計力学, 3: 量子力学, …

といった感じです。

そこで、番号 \(i\) とデータ \(d\) の対応を関数 \(f\) とすると、 \(f\) でデータベースを表現することができます。 上の例だと、 \[ f(1) = 代数幾何, f(2) = 統計力学, f(3)= 量子力学, … \] となります。

データベースの中に、「こういうデータは入っていますか?それはどこですか?」と問われた時に、 データベースの中身を見て、尋ねられたデータを探すことをデータベースの探索と言います。 例えば、「統計力学はどこですか?」と尋ねられたら、2番目ですと答えます。

先程の関数によるデータベースの表現を使って、より一般的に書くと、\(d\) というデータはどこですかという問に対して、 \(f(i)=d\) となるような、 \(i\) を探すことが、データベースの探索となります。

グローバーアルゴリズムの概要

データベースの探索は、中身のデータを一つ一つ順番に見ていけば出来ることはすぐ分かりますが、 もっと効率の良い方法はないのかという疑問が生まれます。

グローバーアルゴリズムは、量子コンピューターを使って、データベースの探索を高速に行うための方法です。 量子コンピューターでは、量子の重ね合わせの性質を使って、データベース \(f\) への一回のアクセスで、 番号 1,2,3,… の重ね合わせに対して、その中身 \(f(1),f(2),f(3),…\) の重ね合わせの状態が得られます。 古典的には、1 回のアクセスで、1 つのデータしか見れないので、かなりの高速化が期待できそうです。

ただし、注意しないといけないのは、結果を見るために測定すると重ね合わせ状態は壊れるということです。 \(f(1),f(2),f(3),…\) の重ね合わせ状態が得られるといっても、\(f(1),f(2),f(3),…\) の中身が見える分けではありません。 \(f(1),f(2),f(3),…\) の中身が全部見えれば、探索は終わったようなものですが、 実は、探索の回答として必要なのは \(f(i)=d\) だけであって、中身が全部見える必要はありません。 そのため、測定を行う前に、\(f(i)=d\) となるものだけが残るように量子的な処理を工夫すればいいということが分かります。 これをする処理が グローバー回転 です。

グローバー回転

話を簡単にするために、データは 0,1 のどちらかで、1 が何番目にあるかを探索することにします。 従って、\(f(i) = 1\) となるような \(i\) を探すことを考えます。 また、データベースのサイズは\(N\)とします。 (ただし、データベース中で 1 は 1 個とします。)

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

定義

データベースの番号 \(i\) を量子状態 \(\ket{i}\) で表し、データベース \(f\) によって決まる演算子 \(U_f\) を次のように定義します。 \[
U_f = I – 2\ket{f_1}\bra{f_1}
\]
ただし、\(\ket{f_1}\)\(f\) の値が 1 となる量子状態、つまり答えの状態に対応します。 \(U_f\)\(\ket{f_1}\) とそれ以外の状態 \(\ket{j}\) への作用の仕方が異なっていて、 \[
\begin{align}
U_f \ket{f_1} &= -\ket{f_1} \\
U_f \ket{j} &= \ket{j}
\end{align}
\]
となります。 すなわち、\(U_f\) は 1 を格納している番号に対しては符号を反転し、それ以外については何もしないと言う形で、 データベースの中身を教えてくれる演算子となります。

次に、ある初期量子状態 \(\ket{\psi}\) に対して、次のような演算子 \(U_s\) を定義します。 \[
U_s = 2\ket{\psi}\bra{\psi} – I
\]

グローバー回転 \(R\) は、2つの演算子\(U_f, U_s\) をこの順で作用させる演算として \[
R = U_s U_f
\]
と定義されます。

グローバー回転の動き

\(\ket{\psi} = \frac{1}{\sqrt{N}} \sum_i \ket{i}\) として、グローバー回転 \(R\)\(\ket{\psi}\) に作用させた動きを見てみます。 (\(\ket{\psi}\) は全ての番号の均一な重ね合わせ状態)

まず、\(U_f\)を作用させると、\(\ket{f_1}\)のみ符号が反転するので、 \[
\begin{align}
U_f \ket{\psi} &= \frac{1}{\sqrt{N}}\sum_{j\ne f_1}\ket{j} – \frac{1}{\sqrt{N}} \ket{f_1} \\
&= \ket{\psi} – \frac{2}{\sqrt{N}}\ket{f_1}
\end{align}
\]
となります。

次に、\(U_s\)を作用させますが、\(U_s\ket{\psi}=\ket{\psi}\)に注意すれば、 \[
\begin{align}
U_s U_f \ket{\psi} &= \ket{\psi} – \frac{2}{\sqrt{N}} (2\bracket{\psi}{f_1}\ket{\psi} – \ket{f_1} )\\
&= \left(1-\frac{4}{N}\right)\ket{\psi} + \frac{2}{\sqrt{N}} \ket{f_1}
\end{align}
\]
となります。 これは、\(\psi\)\(R\)を作用させることで、均等な重ね合わせ\(\ket{\psi}\)から、\(\ket{f_1}\)の確率振幅が強められた状態に移ったことを意味します。

グローバーアルゴリズムでは、\(R\) によって、\(\ket{f_1}\) の確率振幅を増幅する操作を反復して行い、 十分に \(\ket{f_1}\) の振幅が高くなった時点で、観測を実行し、\(f(i)=1\) となる \(i\) つまり、 \(f_1\) を観測結果として得ます。 ただし、確率振幅の増幅は単調に増加するわけではないので、ちょうどいい繰り返し回数で観測に移る必要があります。 (具体的な回数については、今回は省略)

上に示したようなグローバーアルゴリズムの流れをシミュレーションで確認してみます。 ここでは、データベースのサイズを \(N=100\) として、そのうちの一つに 1 をそれ以外は 0 のデータを保持させておきます。 グラフでは、グローバー回転を 8 回行った時の、各 \(\ket{i}\) の重ね合わせの確率振幅をプロットしており、 一つの番号だけ確率振幅が 1 に近くなっていることが分かります。 実際に、この番号が 1 を保持しているデータベースの位置なので、\(\ket{0},\ket{1},\ket{2}, …\) を基底として観測を行えば、 答えのインデックス \(\ket{22}\) が高確率で得られることが分かります。

あくまで確率的アルゴリズムなので、得られた答えが必ずしも正しいとは限りませんが、100% に近い確率で正解が得られることになります。 また、古典的には最悪100回のデータベースの参照が必要となりますが、グローバーアルゴリズムでは、8回のデータベースの参照(\(U_f\) の適用) で済んでいることが分かります。


 

グローバーのアルゴリズム」への2件のフィードバック

  1. Rei

    はじめまして、学部3年物理科の物です。
    非常にわかりやすい解説ありがとうございます。

    最後の例にある、R言語のプログラムについて、解説を頂きたいのですが、
    psi = rep(1,n) / sqrt(n)
    こちらのΦの定義は上の定義とは違う気がするのですが、量子状態で足してなくて良いのでしょうか?

    返信
    1. engetu18 投稿作成者

      ご質問ありがとうございます。
      説明を省いてしまっていたのですが、プログラムの簡単化のため、
      |i> をi番目が1で他が0であるベクトル(0,0,…,0,1,0,…,0)として、
      このプログラム上では表現しています。
      そのため、プログラム上で sum_i |i> は (1,1,…,1) つまり rep(1,n) となります。

      返信

コメントを残す

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