やりたいこと
探索問題を考える．探索問題では，入力が正解なら1を，不正解なら0を返すような関数(オラクル)f(x)を考える:
f(\text{正解})=1,\quad f(\text{不正解})=0
探索問題では，入力を複数回試した時，何回目に正解が求まるかが重要となる．入力を複数回試すということは，オラクルを複数回用いるということである．量子アルゴリズムでは，
|x\rangle|q\rangle \stackrel{U_{f}}{\longrightarrow}|x\rangle|q \oplus f(x)\rangle
というユニタリ演算子U_fを何回用いるかで，計算量を評価する．
位相オラクル
wが求めたい答えであるとき，
f_w(x)=\left\{\begin{array}{ll}
1 & (x=w) \\
0 & (x\neq w)
\end{array}\right.
という関数（オラクル）を考える．これに対して，
U_w|x\rangle=(-1)^{f_w(x)}|x\rangle
を満たすユニタリ演算子を考える．このユニタリ演算子は次のように書ける．
U_w=I-2|w\rangle\langle w|
グローバーのアルゴリズム
n量子ビットを考える（N=2^n）．初期状態は重ね合わせの状態にする．
|s\rangle=H^{\otimes n}|0\rangle^{\otimes n}=\frac{1}{\sqrt{N}} \sum_{x=0}^{N-1}|x\rangle
|s\rangleは|w\rangleとこれに直交する状態\left|w^{\perp}\right\rangle:=\frac{1}{\sqrt{N-1}} \sum_{x \neq w}|x\rangleの線形和で表せる．
\begin{aligned}
|s\rangle &=\sqrt{\frac{N-1}{N}}\left|w^{\perp}\right\rangle+\frac{1}{\sqrt{N}}|w\rangle \\
&=: \cos \frac{\theta}{2}\left|w^{\perp}\right\rangle+\sin \frac{\theta}{2}|w\rangle
\end{aligned}
ただし，\theta=2 \arcsin \frac{1}{\sqrt{\bar{N}}}である．この|w\rangleの振幅を大きくすれば答えを得る確率が高くなる．
そのために，まず(\mathrm{i})位相オラクルU_wを作用させる．
U_w|s\rangle=\cos \frac{\theta}{2}\left|w^{\perp}\right\rangle-\sin \frac{\theta}{2}|w\rangle
次に，(\mathrm{ii})以下で定義されるユニタリ演算子U_sを作用させる．
U_{s}=2|s\rangle\langle s|-I=\cos \theta(\left|w^{\perp}\right\rangle\left\langle w^{\perp}\right|-\left|w\right\rangle\left\langle w\right|)+\sin \theta(|w\rangle\left\langle w^{\perp}\right|+|w^\perp\rangle\left\langle w\right|)
すると，
U_sU_w|s\rangle=\cos \frac{3\theta}{2}\left|w^{\perp}\right\rangle+\sin \frac{3\theta}{2}|w\rangle
となる．この(\mathrm{i}),(\mathrm{ii})をr回繰り返すことで，\frac{\theta}{2}\to\frac{2r+1}{2}\thetaとなる（図形的な考察は例えば）．ここで，\frac{2r+1}{2}\thetaがおおよそ\pi/2となれば |w\rangleの振幅が大きくなり答えを得る確率が高くなる． よって，この等式が成り立つ程度にr回繰り返せば良い．
計算量としては，\thetaが十分小さければ，
\sin\frac{\theta}{2}=\frac{1}{\sqrt{N}}\simeq\frac{\theta}{2}\Rightarrow r=\mathcal{O}(\sqrt{N})
となることが分かる．
実際のプログラムは例えばを参照．
Discussion