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

グローバーのアルゴリズムとは、N個の要素をもつ未整序データベースの中から指定された値を検索する探索問題を解くための量子コンピュータのアルゴリズムであり、O(N^1/2)のオーダーの計算量と、O(logN)のオーダー（ランダウの記号も参照）の記憶領域を消費する。1996年にテンプレート:仮リンクによって開発された。

概要

典型的には、未整序データベースからの探索は、O(N)の計算時間を要する線型探索を用いなければならない。グローバーのアルゴリズムは、O(N^1/2)の計算時間しか消費せず、未整序データベース探索を行う量子アルゴリズムの中で最も速い。

このアルゴリズムは他の量子アルゴリズムがしばしば、古典アルゴリズムと比較して指数的な速度向上をもたらすのとは異なり、二次の速度向上しかもたらさない。しかし、Nが大きければ、二次の向上でもかなりの向上となる。たとえば、グローバーのアルゴリズムを共通鍵暗号の総当り攻撃に利用すると、128ビット鍵であれば2⁶⁴の繰り返しで、256ビット鍵であれば2¹²⁸の繰り返しで求めることができる。このため、将来の量子総当り攻撃に対して安全性を持たせるために、鍵長を2倍にすることが提案されている。

他の量子アルゴリズムと同じように、グローバーのアルゴリズムは正しい解を高い確率で与える確率的アルゴリズムである。この解が正しくない確率は、このアルゴリズムを繰り返すことによって減少させることができる（確率的アルゴリズムでない、正しい確率が1の解を与える、決定的アルゴリズムについてはドイッチュ・ジョサのアルゴリズムを参照）。

応用

グローバーのアルゴリズムの目的は普通「データベース探索」とされるが、「逆関数の導出」と言うとより正確かもしれない。おおざっぱにいうと、y=f(x)という量子コンピュータで処理できる関数があったとして、このアルゴリズムを使うとあるyを与えるxの値を計算することができる。データベース探索は、データベースをインデックスxに対してデータyを与える関数と考えれば、逆関数を求めることと同値である。

グローバーのアルゴリズムは、平均と中央値を推定すること、また衝突問題（w:Collision problem）を解くのにも使える。また、可能性のある解を総当たりで探すことによってNP完全問題を解くことにも使える。これは、膨大な可能性を試すのに、重ね合わせを用いることで限られた計算量しか消費しないので、古典アルゴリズムに比べてかなりのスピードアップを見込めるが、指数時間かかってしまうことは変らない。あらかじめ解が複数あることとその個数がわかっている場合、このアルゴリズムはさらに高速化することができる。

準備

N個のデータを持つデータベースを考える。データベースの中から、何らかの検索条件を満たすデータを探し出す問題を考えよう。 グローバーのアルゴリズムは、$N$ 次元の状態空間 $\mathscr{H}$ を必要とする。これは$n=\lceil {\log }_{2}N\rceil$ 量子ビットあれば満され、基底状態は

$|1⟩,|2⟩,\dots ,|N⟩$

と書ける。これらの固有値 $\{{\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_N\}$ は全て異なるとする。

$f$ を、データベースのインデクス $x\in \{1,2,\dots ,N\}$ を入力すると、検索条件を満たしているか否かを判定する関数とする。例えば、値 $v$に対して$D[x]=v$ となる $x$ を探したい場合には、

$\{\begin{array}{cc}f(x)=1& \text{ if }D[x]=v,\\ f(x)=0& \text{ if }D[x]\ne v\end{array}$

である。以下では $\omega$ を、$f(\omega )=1$ を満たす値とし、次のようにふるまうユニタリ演算子 $U_{\omega }$ を自由にサブルーチンとして使えるとする。（このサブルーチンは、オラクルとも呼ばれる。）

$\{\begin{array}{cc}{U}_{\omega }|x⟩=-|x⟩& \text{for }x=\omega \text{, that is }f(x)=1\\ U_{\omega }|x⟩=|x⟩& \text{for }x\ne \omega \text{, that is }f(x)=0\end{array}$

アルゴリズムの目的は、インデクス $|\omega ⟩$ を特定することである。

なお、（下に示す量子回路のように）補助量子ビットシステムを使う場合には、演算子 $U_{\omega }$ の定義は異なるものになる。この場合の演算子は、メインシステムの $f(x)$ の値（０か１）に応じて反転させる制御NOTによって

$\{\begin{array}{cc}{U}_{\omega }|x⟩|y⟩=|x⟩|\mathrm{\neg }y⟩& \text{for }x=\omega \text{, that is }f(x)=1,\\ U_{\omega }|x⟩|y⟩=|x⟩|y⟩& \text{for }x\ne \omega \text{, that is }f(x)=0,\end{array}$

あるいは、

$U_{\omega }|x⟩|y⟩=|x⟩|y\oplus f(x)⟩.$

で表現される。

アルゴリズムの流れ

グローバーのアルゴリズムを表す量子回路

$|s⟩$ を、全ての状態の一様な重ね合わせ

$|s⟩=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩$

とし、演算子 $U_s$ を

$U_s=2|s⟩⟨s|-I$

とする。この演算子は、グローバーの拡散演算子と呼ばれている。

グローバーのアルゴリズムの流れは以下の通りである。

1. 初期状態を以下の様に用意する：
   • $|s⟩=\frac{1}{\sqrt{N}}\sum _{x=1}^N|x⟩$
2. 次にしめす"Grover iteration"を $r(N)$ 回繰返す。関数 $r(N)$ は漸近的に $O(\sqrt{N})$ である関数であり、詳細は後述する。
   1. 演算子 $U_{\omega }$ を適用する。
   2. 演算子 $U_s$ を適用する。
3. 状態Ωを観測する。観測の結果は、Nが十分に大きければ、1に近い確率でλ_ωとなり、$\omega$を得ることができる。

1回目の繰り返し

演算子 $U_s$ は

$U_s=2|s⟩⟨s|-I,$

で定義されており、さらに、演算子 $U_{\omega }$ は次のように書くことができることに注意する。

$U_{\omega }=I-2|\omega ⟩⟨\omega |$

これを確認するには、$I-2|\omega ⟩⟨\omega |$ が基底状態に対してどのように作用するかをチェックしてみればよい。

$\begin{array}{cc}(I-2|\omega ⟩⟨\omega |)|\omega ⟩& =|\omega ⟩-2|\omega ⟩⟨\omega |\omega ⟩=-|\omega ⟩=U_{\omega }|\omega ⟩\\ (I-2|\omega ⟩⟨\omega |)|x⟩& =|x⟩-2|\omega ⟩⟨\omega |x⟩=|x⟩=U_{\omega }|x⟩& & \mathrm{\forall }x\ne \omega \end{array}$

さらに、$|\omega ⟩$ は基底状態で、$|s⟩$ は全ての状態の一様な重ね合わせであるから、

$\begin{array}{cc}⟨\omega |s⟩& =⟨s|\omega ⟩=\frac{1}{\sqrt{N}},\\ ⟨s|s⟩& =N\frac{1}{\sqrt{N}}\cdot \frac{1}{\sqrt{N}}=1\end{array}$

が成り立つ。したがって、1回目の繰り返しでは次にように計算される。

$\begin{array}{cc}{U}_{\omega }|s⟩& =(I-2|\omega ⟩⟨\omega |)|s⟩=|s⟩-2|\omega ⟩⟨\omega |s⟩=|s⟩-\frac{2}{\sqrt{N}}|\omega ⟩,\\ U_s(|s⟩-\frac{2}{\sqrt{N}}|\omega ⟩)& =(2|s⟩⟨s|-I)(|s⟩-\frac{2}{\sqrt{N}}|\omega ⟩)=2|s⟩⟨s|s⟩-|s⟩-\frac{4}{\sqrt{N}}|s⟩⟨s|\omega ⟩+\frac{2}{\sqrt{N}}|\omega ⟩\\ & =2|s⟩-|s⟩-\frac{4}{\sqrt{N}}\cdot \frac{1}{\sqrt{N}}|s⟩+\frac{2}{\sqrt{N}}|\omega ⟩\\ & =\frac{N-4}{N}|s⟩+\frac{2}{\sqrt{N}}|\omega ⟩.\end{array}$

分かりやすい例として、$N$ が4で、条件を満たす（つまり $f(\omega )=1$ を満たす）$\omega$ が一つしかない場合を考えてみると、$U_s{U}_w|s⟩=|\omega ⟩$ となり、Grover iterator を一回作用させただけで目的の状態を得ることができることが分かる。

一般の場合では、$U_{\omega }$ と $U_s$ を作用させることで、目的の状態の二乗振幅は ${|⟨\omega |s⟩|}^2=\frac{1}{N}$ から ${|⟨\omega |U_s{U}_{\omega }|s⟩|}^2={|\frac{1}{\sqrt{N}}\cdot \frac{N-4}{N}+\frac{2}{\sqrt{N}}|}^2=\frac{(3N-4{)}^2}{N^3}=9{(1-\frac{4}{3N})}^2\cdot \frac{1}{N}$ に増加する。

妥当性の幾何学的な証明

グローバーのアルゴリズムの最初の繰り返しの幾何学的な解釈。状態ベクトル $|s⟩$ は、この図のように目的のベクトル $|\omega ⟩$ に近づく。

|s>と|ω>で張られる空間を考える。この平面は、$|\omega ⟩$ と，それと直交する $|s^{\prime }⟩=\frac{1}{\sqrt{N-1}}{\sum }_{x\ne \omega }|x⟩$ で張られる空間と等しい。 初期状態 $|s⟩$ に作用する最初の繰り返しを考えよう。$|\omega ⟩$ は基底ベクトルであるから、$|s⟩$ と $|s^{\prime }⟩$ の重なりは次のようになる。

$⟨s^{\prime }|s⟩=\sqrt{\frac{N-1}{N}}$

幾何学的に言えば、$|s⟩$ と $|s^{\prime }⟩$ のなす角度 $\theta /2$ は次の関係を満す。

$\sin \frac{\theta }{2}=\frac{1}{\sqrt{N}}$

演算子U_ωは、|s>と|ω>で張られる空間を、|ω>と垂直な超平面を対称面として反転させる。つまり、空間上のベクトルを、$|s^{\prime }⟩$ に対して対称なベクトルへ移す。演算子U_sは、|s>を対称面とする反転である。よって、|s>と|ω>によって張られる平面上にあるベクトルは、U_sとU_ω で演算されても、その平面上に留まる。また、Grover iterationU_sU_ωの各繰り返しで、状態ベクトルは |ω> に向かって角度 $\theta =2\arcsin \frac{1}{\sqrt{N}}\approx 2\frac{1}{\sqrt{N}}$ の回転をすることが容易に分かる。

状態ベクトルが|ω>に近付いたなら、繰返しを止めなければならない。繰返しを重ねすぎると、状態ベクトルは|ω>から離れていってしまい、正しい解を与える確率を下げてしまう。$r$ 回繰り返した場合に正しい答えが観測される確率は、

${\sin }^2\left(\right(r+\frac{1}{2}\left)\theta \right)$

である。したがって、ほぼ最適な測定が得られる繰り返し回数は $r\approx \pi \sqrt{N}/4$ である。

妥当性の代数的な証明

代数的な解析をするには、$U_s{U}_{\omega }$ を繰り返し適用したときに何が起こるかを見る必要がある。これは、行列の固有値解析によって見ることができる。アルゴリズムの計算の間、状態は常に $s$ と $\omega$ の線形結合で表されるいることに注意する。そこで、$\{|s⟩,|\omega ⟩\}$ によって張られる空間において、$U_s$ と $U_{\omega }$ の動作は次のように表すことができる。

$U_s:a|\omega ⟩+b|s⟩\mapsto [|\omega ⟩|s⟩]\left[\begin{array}{cc}-1& 0\\ 2/\sqrt{N}& 1\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]$

$U_{\omega }:a|\omega ⟩+b|s⟩\mapsto [|\omega ⟩|s⟩]\left[\begin{array}{cc}-1& -2/\sqrt{N}\\ 0& 1\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]$

よって、$\{|\omega ⟩,|s⟩\}$ を基底とすると（ただし，これらは直交していないし、全体の空間の基底にはなっていない）、$U_{\omega }$ を作用させてから $U_s$ を作用させるという動作 $U_s{U}_{\omega }$ は、次の行列で表せる。

$U_s{U}_{\omega }=\left[\begin{array}{cc}-1& 0\\ 2/\sqrt{N}& 1\end{array}\right]\left[\begin{array}{cc}-1& -2/\sqrt{N}\\ 0& 1\end{array}\right]=\left[\begin{array}{cc}1& 2/\sqrt{N}\\ -2/\sqrt{N}& 1-4/N\end{array}\right]$

この行列は、非常に便利なジョルダン標準形をしている。$t=\arcsin (1/\sqrt{N})$ と定義すれば、

$U_s{U}_{\omega }=M\left[\begin{array}{cc}\exp (2it)& 0\\ 0& \exp (-2it)\end{array}\right]M^{-1}$ where $M=\left[\begin{array}{cc}-i& i\\ \exp (it)& \exp (-it)\end{array}\right]$

と書ける。 これにより、この行列の r 乗（r 回の繰り返しに対応する）は、

$(U_s{U}_{\omega }{)}^r=M\left[\begin{array}{cc}\exp (2rit)& 0\\ 0& \exp (-2rit)\end{array}\right]M^{-1}$

となる。この形式を使えば、三角関数の公式を使って、r 回の繰り返しの後に目的の $\omega$ が観測される確率を

${|\left[\begin{array}{cc}⟨\omega |\omega ⟩& ⟨\omega |s⟩\end{array}\right](U_s{U}_{\omega }{)}^r\left[\begin{array}{c}0\\ 1\end{array}\right]|}^2={\sin }^2((2r+1)t)$

と計算することができる。（幾何学的な解析で得た確率と同じ。）

あるいは、最適な繰り返し回数は、角度 $2rt$ と $-2rt$ が最も離れているときであり、これは $2rt\approx \pi /2$ に対応する、と考えてもよい。つまり、$r=\pi /4t=\pi /4\arcsin (1/\sqrt{N})\approx \pi \sqrt{N}/4$ が得られる。このとき、システムは

$[|\omega ⟩|s⟩](U_s{U}_{\omega }{)}^r\left[\begin{array}{c}0\\ 1\end{array}\right]\approx [|\omega ⟩|s⟩]M\left[\begin{array}{cc}i& 0\\ 0& -i\end{array}\right]M^{-1}\left[\begin{array}{c}0\\ 1\end{array}\right]=|\omega ⟩\frac{1}{\cos (t)}-|s⟩\frac{\sin (t)}{\cos (t)}$

の状態で終了する。 少し計算すれば、観測によって（エラー確率 O(1/N) を除き）正しい答え $\omega$ が得られることがわかる。

発展形

もし、探索条件にあうデータが1個だけでなく、k個存在するならば、同じアルゴリズムを適用できるが、繰返し回数はπN^1/2/4の代わりにπ(N/k)^1/2/4としなければならない。 kが未知の場合を取り扱う方法は幾つかある。例として、繰返し回数を以下のようにしてグローバーのアルゴリズムを何回か走らせる方法がある。

kがどのような値でも、上のような繰返し回数で行えば正しい解を高い確率で得られる。繰返しの総回数は多くとも次のようであり、O(N^1/2)のオーダーにとどまる。

このアルゴリズムは改良の余地がある。kが未知であるとして、$O(\frac{N}{k}{)}^{1/2}$のオーダーで解を見付けることができる。このことから、このアルゴリズムは衝突問題を解く目的で使用できる。

最適性

グローバーのアルゴリズムは最適であることが知られている。つまり、データベースにU_ωのみを用いてアクセスするようなどんなアルゴリズムも、グローバーのアルゴリズムと同じかそれ以上の回数だけU_ωを作用させなければならない。この結果は量子計算の限界を理解する上で重要である。 もし、グローバーの探索問題がlog^cN回U_ω適用することで解くことができるとすれば、NP問題をグローバーの探索問題に帰着させることで、NPがBQPに含まれることが示される。グローバーのアルゴリズムが最適であることは、NPはBQPに含まれないことを示唆している（ただし証明しているわけではない）。

k個の条件に該当するデータがある場合、π(N/k)^1/2/4も最適である。

適用可能性と制約

このアルゴリズムにおいては、データベースは明示的に表されておらず、代わりに、インデクスによってデータで評価するためにオラクルを呼び出す。データベース全体をデータごとに読み込み、それをインデクスを使って評価できる形式に変換することは、グローバーの検索よりもはるかに時間がかかる場合がある。これを考えると、グローバーのアルゴリズムは、方程式や制約充足問題を解くための方法であると見ることができる。このようなアプリケーションでは、オラクルは制約を満たすかどうかをチェックする方法であり、検索アルゴリズムとは無関係に動作する。一方、従来の検索アルゴリズムでは、検索アルゴリズムを制約のチェック方法と合わせて考慮することで総当たりを回避して最適化を行うことが良くある。グローバーのアルゴリズムではこれらが分離しているため、アルゴリズムの最適化が妨げられる。グローバーのアルゴリズムの使用に関するこれらおよびその他の考慮事項は、Viamontes、Markov、およびHayesによる論文で説明されている。

関連項目

• en:Amplitude amplification

参考文献

• Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
• Grover L.K.: From Schrödinger's equation to quantum search algorithm, American Journal of Physics, 69(7): 769-777, 2001. Pedagogical review of the algorithm and its history.
• http://www.bell-labs.com/user/feature/archives/lkgrover/
• https://arxiv.org/abs/quant-ph/0301079 Grover's Algorithm: Quantum Database Search
• Grover's algorithm on arxiv.org