妥当性の幾何学的な証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/07 09:25 UTC 版)
「グローバーのアルゴリズム」の記事における「妥当性の幾何学的な証明」の解説
グローバーのアルゴリズムの最初の繰り返しの幾何学的な解釈。状態ベクトル | s ⟩ {\displaystyle |s\rangle } は、この図のように目的のベクトル | ω ⟩ {\displaystyle |\omega \rangle } に近づく。 |s>と|ω>で張られる空間を考える。この平面は、 | ω ⟩ {\displaystyle |\omega \rangle } と，それと直交する | s ′ ⟩ = 1 N − 1 ∑ x ≠ ω | x ⟩ {\displaystyle \textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle } で張られる空間と等しい。初期状態 | s ⟩ {\displaystyle |s\rangle } に作用する最初の繰り返しを考えよう。 | ω ⟩ {\displaystyle |\omega \rangle } は基底ベクトルであるから、 | s ⟩ {\displaystyle |s\rangle } と | s ′ ⟩ {\displaystyle |s'\rangle } の重なりは次のようになる。 ⟨ s ′ | s ⟩ = N − 1 N {\displaystyle \langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}} 幾何学的に言えば、 | s ⟩ {\displaystyle |s\rangle } と | s ′ ⟩ {\displaystyle |s'\rangle } のなす角度 θ / 2 {\displaystyle \theta /2} は次の関係を満す。 sin θ 2 = 1 N {\displaystyle \sin {\frac {\theta }{2}}={\frac {1}{\sqrt {N}}}} 演算子Uωは、|s>と|ω>で張られる空間を、|ω>と垂直な超平面を対称面として反転させる。つまり、空間上のベクトルを、 | s ′ ⟩ {\displaystyle |s'\rangle } に対して対称なベクトルへ移す。演算子Usは、|s>を対称面とする反転である。よって、|s>と|ω>によって張られる平面上にあるベクトルは、UsとUω で演算されても、その平面上に留まる。また、Grover iterationUsUωの各繰り返しで、状態ベクトルは |ω> に向かって角度 θ = 2 arcsin 1 N ≈ 2 1 N {\displaystyle \theta =2\arcsin {\tfrac {1}{\sqrt {N}}}\approx 2{\tfrac {1}{\sqrt {N}}}} の回転をすることが容易に分かる。 状態ベクトルが|ω>に近付いたなら、繰返しを止めなければならない。繰返しを重ねすぎると、状態ベクトルは|ω>から離れていってしまい、正しい解を与える確率を下げてしまう。 r {\displaystyle r} 回繰り返した場合に正しい答えが観測される確率は、 sin 2 ( ( r + 1 2 ) θ ) {\displaystyle \sin ^{2}\left({\Big (}r+{\frac {1}{2}}{\Big )}\theta \right)} である。したがって、ほぼ最適な測定が得られる繰り返し回数は r ≈ π N / 4 {\displaystyle r\approx \pi {\sqrt {N}}/4} である。
※この「妥当性の幾何学的な証明」の解説は、「グローバーのアルゴリズム」の解説の一部です。
「妥当性の幾何学的な証明」を含む「グローバーのアルゴリズム」の記事については、「グローバーのアルゴリズム」の概要を参照ください。
- 妥当性の幾何学的な証明のページへのリンク
