妥当性の代数的な証明
出典: フリー百科事典『ウィキペディア（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 } が得られることがわかる。
※この「妥当性の代数的な証明」の解説は、「グローバーのアルゴリズム」の解説の一部です。
「妥当性の代数的な証明」を含む「グローバーのアルゴリズム」の記事については、「グローバーのアルゴリズム」の概要を参照ください。
Weblioに収録されているすべての辞書から妥当性の代数的な証明を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から妥当性の代数的な証明を検索 - 妥当性の代数的な証明のページへのリンク
