Quantum algorithm for eigenvalue estimation
量子コンピューティング において 、 量子位相推定アルゴリズムは、与えられた ユニタリ演算子 の固有値に対応する位相を推定する 量子アルゴリズム である 。ユニタリ演算子の固有値は常に 単位係数 を持つため、位相によって特徴付けられる。したがって、このアルゴリズムは位相または固有値そのものを取得することと同義である。このアルゴリズムは、1995年に アレクセイ・キタエフ によって初めて導入された。 [1] [2] : 246
位相推定は、ショアのアルゴリズム 、 [2] ：131、 線形方程式の量子アルゴリズム 、 量子 計数アルゴリズム などの他の量子アルゴリズムのサブルーチンとして頻繁に使用されます 。
アルゴリズムの概要 このアルゴリズムは、ここでは レジスタ と呼ばれる2組の量子ビットに対して動作します。2つのレジスタには、それぞれ と の量子ビットが含まれます 。 を - 量子ビット レジスタに作用する ユニタリ演算子 とします 。ユニタリ演算子の固有値は単位係数を持ち、したがって位相によって特徴付けられます。したがって、 が の 固有ベクトル である場合 、 ある に対して が成り立ちます 。複素指数関数の周期性により、 は常に と仮定できます 。 n {\displaystyle n} m {\displaystyle m} U {\displaystyle U} m {\displaystyle m} | ψ ⟩ {\displaystyle |\psi \rangle } U {\displaystyle U} U | ψ ⟩ = e 2 π i θ | ψ ⟩ {\displaystyle U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle } θ ∈ R {\displaystyle \theta \in \mathbb {R} } 0 ≤ θ < 1 {\displaystyle 0\leq \theta <1}
目標は、 ゲート数が少なく成功確率の高い の良好な近似値を生成することです。 量子位相 推定アルゴリズムは、 への神託的なアクセス と、 を 量子状態 として利用できることを前提としてこれを実現します。つまり、アルゴリズムの効率性について議論する際には 、 の使用 回数のみを考慮すればよく、実装コストは考慮しなくて済みます 。 θ {\displaystyle \theta } U {\displaystyle U} | ψ ⟩ {\displaystyle |\psi \rangle } U {\displaystyle U} U {\displaystyle U}
より正確には、このアルゴリズムは、 第1レジスタの量子ビットと 制御 U 演算を用いて、 加法誤差 の範囲内で、 の近似値を 高い確率で 返します。さらに、制御Uを合計 回使用することで、任意の に対する 成功確率を まで向上させることができ 、これは最適です。 [3] θ {\displaystyle \theta } ε {\displaystyle \varepsilon } n = O ( log ( 1 / ε ) ) {\displaystyle n=O(\log(1/\varepsilon ))} O ( 1 / ε ) {\displaystyle O(1/\varepsilon )} 1 − Δ {\displaystyle 1-\Delta } Δ > 0 {\displaystyle \Delta >0} O ( log ( 1 / Δ ) / ε ) {\displaystyle O(\log(1/\Delta )/\varepsilon )}
アルゴリズムの詳細な説明 量子位相推定のための回路。
国家の準備 システムの初期状態は次のとおりです。
| Ψ 0 ⟩ = | 0 ⟩ ⊗ n | ψ ⟩ , {\displaystyle |\Psi _{0}\rangle =|0\rangle ^{\otimes n}|\psi \rangle ,} ここで 、 は を通じて発展する -量子ビット状態 です 。まず、 最初のレジスタに n 量子ビットの アダマール ゲート演算を 適用し、状態を生成します。ここで、 -量子ビット レジスタのバイナリ 表現と -arry 表現を切り替えていることに注意してください。 右側の ketは -量子ビット状態の省略形であり 、 は のバイナリ分解です 。 | ψ ⟩ {\displaystyle |\psi \rangle } m {\displaystyle m} U {\displaystyle U} H ⊗ n {\displaystyle H^{\otimes n}} | Ψ 1 ⟩ = ( H ⊗ n ⊗ I m ) | Ψ 0 ⟩ = 1 2 n 2 ( | 0 ⟩ + | 1 ⟩ ) ⊗ n | ψ ⟩ = 1 2 n / 2 ∑ j = 0 2 n − 1 | j ⟩ | ψ ⟩ . {\displaystyle |\Psi _{1}\rangle =(H^{\otimes n}\otimes I_{m})|\Psi _{0}\rangle ={\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle ={\frac {1}{2^{n/2}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle .} n {\displaystyle n} n {\displaystyle n} | j ⟩ {\displaystyle |j\rangle } n {\displaystyle n} | j ⟩ ≡ ⨂ ℓ = 0 n − 1 | j ℓ ⟩ {\displaystyle |j\rangle \equiv \bigotimes _{\ell =0}^{n-1}|j_{\ell }\rangle } j = ∑ ℓ = 0 n − 1 j ℓ 2 ℓ {\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }} j {\displaystyle j}
制御U操作 この状態は 、制御ユニタリー発展によって発展します。この発展の作用は、 すべての に対して と表すことができます 。この発展は と簡潔に表すこともでき、 これはその制御された性質を強調しています。つまり、 は、 最初のレジスタが であることを条件として、2番目のレジスタに適用されます 。 に対して成立する固有値条件を思い出し 、 に適用すると、 が得られます 。 ここで を使用しました。 | Ψ 1 ⟩ {\displaystyle |\Psi _{1}\rangle } U C {\displaystyle U_{C}} U C ( | k ⟩ ⊗ | ψ ⟩ ) = | k ⟩ ⊗ ( U k | ψ ⟩ ) , {\displaystyle U_{C}(|k\rangle \otimes |\psi \rangle )=|k\rangle \otimes (U^{k}|\psi \rangle ),} k = 0 , . . . , 2 n − 1 {\displaystyle k=0,...,2^{n}-1} U C = ∑ k = 0 2 n − 1 | k ⟩ ⟨ k | ⊗ U k , {\displaystyle U_{C}=\sum _{k=0}^{2^{n}-1}|k\rangle \!\langle k|\otimes U^{k},} U k {\displaystyle U^{k}} | k ⟩ {\displaystyle |k\rangle } | ψ ⟩ {\displaystyle |\psi \rangle } U C {\displaystyle U_{C}} | Ψ 1 ⟩ {\displaystyle |\Psi _{1}\rangle } | Ψ 2 ⟩ ≡ U C | Ψ 1 ⟩ = ( 1 2 n / 2 ∑ k = 0 2 n − 1 e 2 π i θ k | k ⟩ ) ⊗ | ψ ⟩ , {\displaystyle |\Psi _{2}\rangle \equiv U_{C}|\Psi _{1}\rangle =\left({\frac {1}{2^{n/2}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle \right)\otimes |\psi \rangle ,} U k | ψ ⟩ = e 2 π i k θ | ψ ⟩ {\displaystyle U^{k}|\psi \rangle =e^{2\pi ik\theta }|\psi \rangle }
も効率的に実装できることを示すために 、 と書けることに注目してください。 ここで、 は、 最初のレジスタの - 番目の量子ビット が である条件付きで 2 番目のレジスタに を適用する操作を表します 。正式には、これらのゲートは、次のような動作によって特徴付けられます。この式 は、 のとき、つまり - 番目の量子ビットが のとき は状態は変更されないが、 - 番目の量子ビットが の ときはゲートが 2 番目のレジスタに適用される、と解釈できます 。したがって、これらの制御ゲートの合成は となり、 最後のステップはバイナリ分解 から直接続きます 。 U C {\displaystyle U_{C}} U C = ∏ ℓ = 0 n − 1 C ℓ ( U 2 ℓ ) {\displaystyle U_{C}=\prod _{\ell =0}^{n-1}C_{\ell }(U^{2^{\ell }})} C ℓ ( U 2 ℓ ) {\displaystyle C_{\ell }(U^{2^{\ell }})} U 2 ℓ {\displaystyle U^{2^{\ell }}} ℓ {\displaystyle \ell } | 1 ⟩ {\displaystyle |1\rangle } C ℓ ( U k ) ( | j ⟩ ⊗ | ψ ⟩ ) = | j ⟩ ⊗ ( U j ℓ k | ψ ⟩ ) . {\displaystyle C_{\ell }(U^{k})(|j\rangle \otimes |\psi \rangle )=|j\rangle \otimes (U^{j_{\ell }k}|\psi \rangle ).} j ℓ = 0 {\displaystyle j_{\ell }=0} ℓ {\displaystyle \ell } | 0 ⟩ {\displaystyle |0\rangle } U k {\displaystyle U^{k}} ℓ {\displaystyle \ell } | 1 ⟩ {\displaystyle |1\rangle } ∏ ℓ = 0 n − 1 C ℓ ( U 2 ℓ ) ( | j ⟩ ⊗ | ψ ⟩ ) = | j ⟩ ⊗ ( U ∑ ℓ = 0 n − 1 j ℓ 2 ℓ | ψ ⟩ ) = U C ( | j ⟩ ⊗ | ψ ⟩ ) , {\displaystyle \prod _{\ell =0}^{n-1}C_{\ell }(U^{2^{\ell }})(|j\rangle \otimes |\psi \rangle )=|j\rangle \otimes \left(U^{\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}|\psi \rangle \right)=U_{C}\left(|j\rangle \otimes |\psi \rangle \right),} j = ∑ ℓ = 0 n − 1 j ℓ 2 ℓ {\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}
この時点から先は、2 番目のレジスタはそのまま残されるため、アルゴリズムの残りの部分で考慮する必要がある唯一の -qubit レジスタ の状態 を使用して と 記述すると便利です。 | Ψ 2 ⟩ = | Ψ ~ 2 ⟩ ⊗ | ψ ⟩ {\displaystyle |\Psi _{2}\rangle =|{\tilde {\Psi }}_{2}\rangle \otimes |\psi \rangle } | Ψ ~ 2 ⟩ {\displaystyle |{\tilde {\Psi }}_{2}\rangle } n {\displaystyle n}
回路の最後の部分では、逆 量子フーリエ変換 （QFT）を 最初のレジスタに適用します 。QFT とその逆は、基底状態に対する作用によって 次の
ように特徴付けられます。 Q F T {\displaystyle {\mathcal {QFT}}} | Ψ 2 ⟩ {\displaystyle |\Psi _{2}\rangle } | Ψ ~ 3 ⟩ = Q F T 2 n − 1 | Ψ ~ 2 ⟩ . {\displaystyle |{\tilde {\Psi }}_{3}\rangle ={\mathcal {QFT}}_{2^{n}}^{-1}|{\tilde {\Psi }}_{2}\rangle .} Q F T N | k ⟩ = N − 1 / 2 ∑ j = 0 N − 1 e 2 π i N j k | j ⟩ , Q F T N − 1 | k ⟩ = N − 1 / 2 ∑ j = 0 N − 1 e − 2 π i N j k | j ⟩ . {\displaystyle {\begin{aligned}{\mathcal {QFT}}_{N}|k\rangle &=N^{-1/2}\sum _{j=0}^{N-1}e^{{\frac {2\pi i}{N}}jk}|j\rangle ,\\{\mathcal {QFT}}_{N}^{-1}|k\rangle &=N^{-1/2}\sum _{j=0}^{N-1}e^{-{\frac {2\pi i}{N}}jk}|j\rangle .\end{aligned}}}
| Ψ ~ 3 ⟩ = 1 2 n 2 ∑ k = 0 2 n − 1 e 2 π i θ k ( 1 2 n 2 ∑ x = 0 2 n − 1 e − 2 π i k x 2 n | x ⟩ ) = 1 2 n ∑ x = 0 2 n − 1 ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( x − 2 n θ ) | x ⟩ . {\displaystyle |{\tilde {\Psi }}_{3}\rangle ={\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}\left({\frac {1}{2^{\frac {n}{2}}}}\sum _{x=0}^{2^{n}-1}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle \right)={\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle .} 状態を計算基底において分解すると、 係数は と等しくなります。ここで は に 最も近い整数であると 書きました 。この差は 定義により を満たさなければなりません 。これは、 の値を 最も近い整数に 丸めることで近似することに相当します。 | Ψ ~ 3 ⟩ = ∑ x = 0 2 n − 1 c x | x ⟩ , {\textstyle |{\tilde {\Psi }}_{3}\rangle =\sum _{x=0}^{2^{n}-1}c_{x}|x\rangle ,} c x ≡ 1 2 n ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( x − 2 n θ ) = 1 2 n ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( x − a ) e 2 π i δ k , {\displaystyle c_{x}\equiv {\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}(x-2^{n}\theta )}={\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-a\right)}e^{2\pi i\delta k},} 2 n θ = a + 2 n δ , {\displaystyle 2^{n}\theta =a+2^{n}\delta ,} a {\displaystyle a} 2 n θ {\displaystyle 2^{n}\theta } 2 n δ {\displaystyle 2^{n}\delta } 0 ⩽ | 2 n δ | ⩽ 1 2 {\displaystyle 0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}} θ ∈ [ 0 , 1 ] {\displaystyle \theta \in [0,1]} 2 n θ {\displaystyle 2^{n}\theta }
測定 最後のステップでは、 最初のレジスタの計算基底における 測定 を実行します。これにより、確率 の結果が得られます。 したがって 、 、つまり が と書ける場合 、常に結果 が得られます 。一方、 の場合 、確率 となります。この式から、 のとき と なることがわかります 。これを確認するには、 の定義から 不等式 が得られることに着目します 。したがって、次の式が成り立ちます。 [4] : 157 [5] : 348 | y ⟩ {\displaystyle |y\rangle } Pr ( y ) = | c y | 2 = | 1 2 n ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( y − a ) e 2 π i δ k | 2 . {\displaystyle \Pr(y)=|c_{y}|^{2}=\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}(y-a)}e^{2\pi i\delta k}\right|^{2}.} Pr ( a ) = 1 {\displaystyle \operatorname {Pr} (a)=1} δ = 0 {\displaystyle \delta =0} θ {\displaystyle \theta } θ = a / 2 n {\displaystyle \theta =a/2^{n}} y = a {\displaystyle y=a} δ ≠ 0 {\displaystyle \delta \neq 0} Pr ( a ) = 1 2 2 n | ∑ k = 0 2 n − 1 e 2 π i δ k | 2 = 1 2 2 n | 1 − e 2 π i 2 n δ 1 − e 2 π i δ | 2 . {\displaystyle \operatorname {Pr} (a)={\frac {1}{2^{2n}}}\left|\sum _{k=0}^{2^{n}-1}e^{2\pi i\delta k}\right|^{2}={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}.} Pr ( a ) ⩾ 4 π 2 ≈ 0.405 {\displaystyle \Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405} δ ≠ 0 {\displaystyle \delta \neq 0} δ {\displaystyle \delta } | δ | ⩽ 1 2 n + 1 {\displaystyle |\delta |\leqslant {\tfrac {1}{2^{n+1}}}} Pr ( a ) = 1 2 2 n | 1 − e 2 π i 2 n δ 1 − e 2 π i δ | 2 for δ ≠ 0 = 1 2 2 n | 2 sin ( π 2 n δ ) 2 sin ( π δ ) | 2 | 1 − e 2 i x | 2 = 4 | sin ( x ) | 2 = 1 2 2 n | sin ( π 2 n δ ) | 2 | sin ( π δ ) | 2 ⩾ 1 2 2 n | sin ( π 2 n δ ) | 2 | π δ | 2 | sin ( π δ ) | ⩽ | π δ | ⩾ 1 2 2 n | 2 ⋅ 2 n δ | 2 | π δ | 2 | 2 ⋅ 2 n δ | ⩽ | sin ( π 2 n δ ) | for | δ | ⩽ 1 2 n + 1 ⩾ 4 π 2 . {\displaystyle {\begin{aligned}\Pr(a)&={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&&{\text{for }}\delta \neq 0\\&={\frac {1}{2^{2n}}}\left|{\frac {2\sin \left(\pi 2^{n}\delta \right)}{2\sin(\pi \delta )}}\right|^{2}&&\left|1-e^{2ix}\right|^{2}=4\left|\sin(x)\right|^{2}\\&={\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\sin(\pi \delta )|^{2}}}\\&\geqslant {\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\pi \delta |^{2}}}&&|\sin(\pi \delta )|\leqslant |\pi \delta |\\&\geqslant {\frac {1}{2^{2n}}}{\frac {|2\cdot 2^{n}\delta |^{2}}{|\pi \delta |^{2}}}&&|2\cdot 2^{n}\delta |\leqslant |\sin(\pi 2^{n}\delta )|{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\&\geqslant {\frac {4}{\pi ^{2}}}.\end{aligned}}}
このアルゴリズムは、少なくとも の確率での 最良のビット推定値（つまり、 正解の 以内の推定値）を提供すると結論付けます 。 のオーダーの数の追加量子ビットを追加し 、追加量子ビットを切り捨てることで、確率は まで増加します 。 [5] n {\displaystyle n} 1 / 2 n {\displaystyle 1/2^{n}} θ {\displaystyle \theta } 4 / π 2 {\displaystyle 4/\pi ^{2}} O ( log ( 1 / ϵ ) ) {\displaystyle O(\log(1/\epsilon ))} 1 − ϵ {\displaystyle 1-\epsilon }
おもちゃの例 アルゴリズムの最も単純な例を考えてみましょう。ここでは 、 をエンコードするために必要な量子ビットに加えて 、 量子ビットのみが関係します。 の固有値が 、 と読み取られると仮定します 。アルゴリズムの最初の部分では、1量子ビットの状態 が生成されます 。この場合、逆 QFT を適用することは、 アダマールゲート を適用することと同じです。したがって、最終的な結果の確率は となります。 ここで 、より明確には 、 つまり と仮定します 。すると 、 となり、測定結果から の正確な値を決定論的に回復できます 。 の場合も同様です 。 n = 1 {\displaystyle n=1} | ψ ⟩ {\displaystyle |\psi \rangle } | ψ ⟩ {\displaystyle |\psi \rangle } λ = e 2 π i θ {\displaystyle \lambda =e^{2\pi i\theta }} θ ∈ [ 0 , 1 ) {\displaystyle \theta \in [0,1)} | ϕ ⟩ ≡ 1 2 ( | 0 ⟩ + λ | 1 ⟩ ) {\textstyle |\phi \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle +\lambda |1\rangle )} p ± = | ⟨ ± | ϕ ⟩ | 2 {\displaystyle p_{\pm }=|\langle \pm |\phi \rangle |^{2}} | ± ⟩ ≡ 1 2 ( | 0 ⟩ ± | 1 ⟩ ) {\textstyle |\pm \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle \pm |1\rangle )} p ± = | 1 ± λ | 2 4 = 1 ± cos ( 2 π θ ) 2 . {\displaystyle p_{\pm }={\frac {|1\pm \lambda |^{2}}{4}}={\frac {1\pm \cos(2\pi \theta )}{2}}.} λ = 1 {\displaystyle \lambda =1} | ϕ ⟩ = | + ⟩ {\displaystyle |\phi \rangle =|+\rangle } p + = 1 {\displaystyle p_{+}=1} p − = 0 {\displaystyle p_{-}=0} λ {\displaystyle \lambda } λ = − 1 {\displaystyle \lambda =-1}
一方 、の場合は 、つまり となり、 となります 。この場合、結果は決定論的ではありませんが、 が0 よりも 1 に近い という事実と矛盾せず、結果の方が可能性が高いことがわかります 。 λ = e 2 π i / 3 {\displaystyle \lambda =e^{2\pi i/3}} p ± = [ 1 ± cos ( 2 π / 3 ) ] / 2 {\displaystyle p_{\pm }=[1\pm \cos(2\pi /3)]/2} p + = 1 / 4 {\displaystyle p_{+}=1/4} p − = 3 / 4 {\displaystyle p_{-}=3/4} | − ⟩ {\displaystyle |-\rangle } 2 / 3 {\displaystyle 2/3}
より一般的には、 の場合 、 の場合に限ります。これは 、 に対応する の 場合 、位相が決定論的に取得され、他の位相はこれら2つの位相に近いほど高い精度で取得されるため、上記の結果と一致しています。 λ = e 2 π i θ {\displaystyle \lambda =e^{2\pi i\theta }} p + ≥ 1 / 2 {\displaystyle p_{+}\geq 1/2} | θ | ≤ 1 / 4 {\displaystyle |\theta |\leq 1/4} λ = ± 1 {\displaystyle \lambda =\pm 1} θ = 0 , 1 / 2 {\displaystyle \theta =0,1/2}
参照
参考文献 ^ Kitaev, A. Yu (1995-11-20). 「量子測定とアーベル安定化問題」. arXiv : quant-ph/9511026 . ^ ab ニールセン、マイケル・A. & アイザック・L. チュアン (2001). 量子計算と量子情報 （復刻版）. ケンブリッジ [ua]: ケンブリッジ大学出版局. ISBN 978-0521635035 。 ^ Mande, Nikhil S.; Ronald de Wolf (2023). 「量子位相推定と関連問題に対する厳密な境界」. arXiv : 2305.04908 [quant-ph]. ^ ベネンティ、ギリアーノ;カザーティ、ジュリオ。ストリーニ、ジュリアーノ (2004)。 量子計算と情報の原理 (再版)。ニュージャージー [ua]: 世界科学。 ISBN 978-9812388582 。 ^ ab Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (1998年1月8日). 「量子アルゴリズムの再考」. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences . 454 (1969): 339– 354. arXiv : quant-ph/9708016 . Bibcode :1998RSPSA.454..339C. doi :10.1098/rspa.1998.0164. S2CID 16128238.
![{\displaystyle \theta \in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fead1e7dceab4be5ab2e91f5108144722daa8c36)
![{\displaystyle p_{\pm }=[1\pm \cos(2\pi /3)]/2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0b63cb1023df44a496f4b32ad1ff83f6e68de93)
