1回目の繰り返し
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/07 09:25 UTC 版)
「グローバーのアルゴリズム」の記事における「1回目の繰り返し」の解説
演算子 U s {\displaystyle U_{s}} は U s = 2 | s ⟩ ⟨ s | − I , {\displaystyle U_{s}=2|s\rangle \langle s|-I,} で定義されており、さらに、演算子 U ω {\displaystyle U_{\omega }} は次のように書くことができることに注意する。 U ω = I − 2 | ω ⟩ ⟨ ω | {\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |} これを確認するには、 I − 2 | ω ⟩ ⟨ ω | {\displaystyle I-2|\omega \rangle \langle \omega |} が基底状態に対してどのように作用するかをチェックしてみればよい。 ( I − 2 | ω ⟩ ⟨ ω | ) | ω ⟩ = | ω ⟩ − 2 | ω ⟩ ⟨ ω | ω ⟩ = − | ω ⟩ = U ω | ω ⟩ ( I − 2 | ω ⟩ ⟨ ω | ) | x ⟩ = | x ⟩ − 2 | ω ⟩ ⟨ ω | x ⟩ = | x ⟩ = U ω | x ⟩ ∀ x ≠ ω {\displaystyle {\begin{aligned}(I-2|\omega \rangle \langle \omega |)|\omega \rangle &=|\omega \rangle -2|\omega \rangle \langle \omega |\omega \rangle =-|\omega \rangle =U_{\omega }|\omega \rangle \\(I-2|\omega \rangle \langle \omega |)|x\rangle &=|x\rangle -2|\omega \rangle \langle \omega |x\rangle =|x\rangle =U_{\omega }|x\rangle &&\forall x\neq \omega \end{aligned}}} さらに、 | ω ⟩ {\displaystyle |\omega \rangle } は基底状態で、 | s ⟩ {\displaystyle |s\rangle } は全ての状態の一様な重ね合わせであるから、 ⟨ ω | s ⟩ = ⟨ s | ω ⟩ = 1 N , ⟨ s | s ⟩ = N 1 N ⋅ 1 N = 1 {\displaystyle {\begin{aligned}\langle \omega |s\rangle &=\langle s|\omega \rangle ={\tfrac {1}{\sqrt {N}}},\\\langle s|s\rangle &=N{\tfrac {1}{\sqrt {N}}}\cdot {\tfrac {1}{\sqrt {N}}}=1\end{aligned}}} が成り立つ。したがって、1回目の繰り返しでは次にように計算される。 U ω | s ⟩ = ( I − 2 | ω ⟩ ⟨ ω | ) | s ⟩ = | s ⟩ − 2 | ω ⟩ ⟨ ω | s ⟩ = | s ⟩ − 2 N | ω ⟩ , U s ( | s ⟩ − 2 N | ω ⟩ ) = ( 2 | s ⟩ ⟨ s | − I ) ( | s ⟩ − 2 N | ω ⟩ ) = 2 | s ⟩ ⟨ s | s ⟩ − | s ⟩ − 4 N | s ⟩ ⟨ s | ω ⟩ + 2 N | ω ⟩ = 2 | s ⟩ − | s ⟩ − 4 N ⋅ 1 N | s ⟩ + 2 N | ω ⟩ = N − 4 N | s ⟩ + 2 N | ω ⟩ . {\displaystyle {\begin{aligned}U_{\omega }|s\rangle &=(I-2|\omega \rangle \langle \omega |)|s\rangle =|s\rangle -2|\omega \rangle \langle \omega |s\rangle =|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle ,\\U_{s}\left(|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle \right)&=\left(2|s\rangle \langle s|-I\right)\left(|s\rangle -{\tfrac {2}{\sqrt {N}}}|\omega \rangle \right)=2|s\rangle \langle s|s\rangle -|s\rangle -{\tfrac {4}{\sqrt {N}}}|s\rangle \langle s|\omega \rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle \\&=2|s\rangle -|s\rangle -{\tfrac {4}{\sqrt {N}}}\cdot {\tfrac {1}{\sqrt {N}}}|s\rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle \\&={\tfrac {N-4}{N}}|s\rangle +{\tfrac {2}{\sqrt {N}}}|\omega \rangle .\end{aligned}}} 分かりやすい例として、 N {\displaystyle N} が4で、条件を満たす（つまり f ( ω ) = 1 {\displaystyle f(\omega )=1} を満たす） ω {\displaystyle \omega } が一つしかない場合を考えてみると、 U s U w | s ⟩ = | ω ⟩ {\displaystyle U_{s}U_{w}|s\rangle =|\omega \rangle } となり、Grover iterator を一回作用させただけで目的の状態を得ることができることが分かる。 一般の場合では、 U ω {\displaystyle U_{\omega }} と U s {\displaystyle U_{s}} を作用させることで、目的の状態の二乗振幅は | ⟨ ω | s ⟩ | 2 = 1 N {\displaystyle \left|\langle \omega |s\rangle \right|^{2}={\tfrac {1}{N}}} から | ⟨ ω | U s U ω | s ⟩ | 2 = | 1 N ⋅ N − 4 N + 2 N | 2 = ( 3 N − 4 ) 2 N 3 = 9 ( 1 − 4 3 N ) 2 ⋅ 1 N {\displaystyle \left|\langle \omega |U_{s}U_{\omega }|s\rangle \right|^{2}=\left|{\tfrac {1}{\sqrt {N}}}\cdot {\tfrac {N-4}{N}}+{\tfrac {2}{\sqrt {N}}}\right|^{2}={\tfrac {(3N-4)^{2}}{N^{3}}}=9\left(1-{\tfrac {4}{3N}}\right)^{2}\cdot {\tfrac {1}{N}}} に増加する。
※この「1回目の繰り返し」の解説は、「グローバーのアルゴリズム」の解説の一部です。
「1回目の繰り返し」を含む「グローバーのアルゴリズム」の記事については、「グローバーのアルゴリズム」の概要を参照ください。
- 1回目の繰り返しのページへのリンク
