妥当性の代数的な証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/07 09:25 UTC 版)
「グローバーのアルゴリズム」の記事における「妥当性の代数的な証明」の解説
代数的な解析をするには、 U s U ω {\displaystyle U_{s}U_{\omega }} を繰り返し適用したときに何が起こるかを見る必要がある。これは、行列の固有値解析によって見ることができる。アルゴリズムの計算の間、状態は常に s {\displaystyle s} と ω {\displaystyle \omega } の線形結合で表されるいることに注意する。そこで、 { | s ⟩ , | ω ⟩ } {\displaystyle \{|s\rangle ,|\omega \rangle \}} によって張られる空間において、 U s {\displaystyle U_{s}} と U ω {\displaystyle U_{\omega }} の動作は次のように表すことができる。 U s : a | ω ⟩ + b | s ⟩ ↦ [ | ω ⟩ | s ⟩ ] [ − 1 0 2 / N 1 ] [ a b ] {\displaystyle U_{s}:a|\omega \rangle +b|s\rangle \mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}} U ω : a | ω ⟩ + b | s ⟩ ↦ [ | ω ⟩ | s ⟩ ] [ − 1 − 2 / N 0 1 ] [ a b ] {\displaystyle U_{\omega }:a|\omega \rangle +b|s\rangle \mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}} よって、 { | ω ⟩ , | s ⟩ } {\displaystyle \{|\omega \rangle ,|s\rangle \}} を基底とすると（ただし，これらは直交していないし、全体の空間の基底にはなっていない）、 U ω {\displaystyle U_{\omega }} を作用させてから U s {\displaystyle U_{s}} を作用させるという動作 U s U ω {\displaystyle U_{s}U_{\omega }} は、次の行列で表せる。 U s U ω = [ − 1 0 2 / N 1 ] [ − 1 − 2 / N 0 1 ] = [ 1 2 / N − 2 / N 1 − 4 / N ] {\displaystyle U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}} この行列は、非常に便利なジョルダン標準形をしている。 t = arcsin ( 1 / N ) {\displaystyle t=\arcsin(1/{\sqrt {N}})} と定義すれば、 U s U ω = M [ exp ( 2 i t ) 0 0 exp ( − 2 i t ) ] M − 1 {\displaystyle U_{s}U_{\omega }=M{\begin{bmatrix}\exp(2it)&0\\0&\exp(-2it)\end{bmatrix}}M^{-1}} where M = [ − i i exp ( i t ) exp ( − i t ) ] {\displaystyle M={\begin{bmatrix}-i&i\\\exp(it)&\exp(-it)\end{bmatrix}}} と書ける。これにより、この行列の r 乗（r 回の繰り返しに対応する）は、 ( U s U ω ) r = M [ exp ( 2 r i t ) 0 0 exp ( − 2 r i t ) ] M − 1 {\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{bmatrix}\exp(2rit)&0\\0&\exp(-2rit)\end{bmatrix}}M^{-1}} となる。この形式を使えば、三角関数の公式を使って、r 回の繰り返しの後に目的の ω {\displaystyle \omega } が観測される確率を | [ ⟨ ω | ω ⟩ ⟨ ω | s ⟩ ] ( U s U ω ) r [ 0 1 ] | 2 = sin 2 ( ( 2 r + 1 ) t ) {\displaystyle \left|{\begin{bmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{bmatrix}}(U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\right|^{2}=\sin ^{2}\left((2r+1)t\right)} と計算することができる。（幾何学的な解析で得た確率と同じ。） あるいは、最適な繰り返し回数は、角度 2 r t {\displaystyle 2rt} と − 2 r t {\displaystyle -2rt} が最も離れているときであり、これは 2 r t ≈ π / 2 {\displaystyle 2rt\approx \pi /2} に対応する、と考えてもよい。つまり、 r = π / 4 t = π / 4 arcsin ( 1 / N ) ≈ π N / 4 {\displaystyle r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4} が得られる。このとき、システムは [ | ω ⟩ | s ⟩ ] ( U s U ω ) r [ 0 1 ] ≈ [ | ω ⟩ | s ⟩ ] M [ i 0 0 − i ] M − 1 [ 0 1 ] = | ω ⟩ 1 cos ( t ) − | s ⟩ sin ( t ) cos ( t ) {\displaystyle [|\omega \rangle \,|s\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|s\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|s\rangle {\frac {\sin(t)}{\cos(t)}}} の状態で終了する。少し計算すれば、観測によって（エラー確率 O(1/N) を除き）正しい答え ω {\displaystyle \omega } が得られることがわかる。
※この「妥当性の代数的な証明」の解説は、「グローバーのアルゴリズム」の解説の一部です。
「妥当性の代数的な証明」を含む「グローバーのアルゴリズム」の記事については、「グローバーのアルゴリズム」の概要を参照ください。
- 妥当性の代数的な証明のページへのリンク
