量子位相推定アルゴリズム

量子コンピューティングにおいて、量子位相推定アルゴリズムは、与えられたユニタリ演算子の固有値に対応する位相を推定する量子アルゴリズムである。ユニタリ演算子の固有値は常に単位係数を持つため、位相によって特徴付けられ、したがって、このアルゴリズムは位相または固有値自体を取得することと同等に説明できる。このアルゴリズムは、1995年にアレクセイ・キタエフによって最初に導入された。^{[1] [2] : 246}

位相推定は、ショアのアルゴリズム、^{[2] ：131、}線形方程式の量子アルゴリズム、量子計数アルゴリズムなどの他の量子アルゴリズムのサブルーチンとして頻繁に使用されます。

このアルゴリズムは、ここではレジスタと呼ばれる 2 セットの量子ビットに対して動作します。2 つのレジスタには、それぞれ との量子ビットが含まれます。を-量子ビットレジスタに作用するユニタリ演算子とします。ユニタリ演算子の固有値は単位係数を持つため、その位相によって特徴付けられます。したがって、が の固有ベクトルである場合、ある に対して が成り立ちます。複素指数関数の周期性により、 を常に想定できます。 ${\displaystyle n}$${\displaystyle m}$${\displaystyle U}$${\displaystyle m}$${\displaystyle |\psi \rangle }$${\displaystyle U}$${\displaystyle U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle }$${\displaystyle \theta \in \mathbb {R} }$${\displaystyle 0\leq \theta <1}$

目標は、ゲート数が少なく成功確率の高い の近似値を生成することです。量子位相推定アルゴリズムは、 への神託的なアクセスと、 が量子状態として利用可能であることを前提としてこれを実現します。つまり、アルゴリズムの効率性について議論する際には、 を使用する必要のある回数だけを気にすればよく、実装自体 のコストは気にしなくてよいということです。${\displaystyle \theta}$${\displaystyle U}$${\displaystyle |\psi \rangle }$${\displaystyle U}$${\displaystyle U}$

より正確には、アルゴリズムは、最初のレジスタの量子ビットと制御U操作を使用して、加法誤差 の範囲内での近似値を高い確率で返します。さらに、制御Uを合計 回使用することで、任意のに対する成功確率を に改善することができ、これは最適です。^[3]${\displaystyle \theta}$${\displaystyle \epsilon }$${\displaystyle n=O(\log(1/\varepsilon ))}$${\displaystyle O(1/\バレプシロン )}$ ${\displaystyle 1-\Delta }$${\displaystyle \Delta >0}$${\displaystyle O(\log(1/\Delta )/\varepsilon )}$

システムの初期状態は次のとおりです。

${\displaystyle |\Psi _{0}\rangle =|0\rangle ^{\otimes n}|\psi \rangle ,}$

ここで、 はを通じて発展する -量子ビット状態です。まず、最初のレジスタにn 量子ビットのアダマール ゲート演算を適用し、状態を生成します。ここで、 -量子ビット レジスタのバイナリ表現と -arry 表現を切り替えていることに注意してください。右側のket は-量子ビット状態の省略形であり、 はのバイナリ分解です。 ${\displaystyle |\psi \rangle }$${\displaystyle m}$${\displaystyle U}$ ${\displaystyle H^{\otimes n}}$$${\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 .}$$${\displaystyle n}$${\displaystyle n}$${\displaystyle |j\rangle}$${\displaystyle n}$${\displaystyle |j\rangle \equiv \bigotimes _{\ell =0}^{n-1}|j_{\ell }\rangle }$${\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}$${\displaystyle j}$

この状態は、すべての に対してと記述できる制御ユニタリー進化を通じて進化します。この進化は、 と簡潔に記述することもでき、その制御された性質を強調しています。つまり、 は、最初のレジスタ である条件付きで 2 番目のレジスタに適用されます。 に対して保持される固有値条件を思い出して、に適用すると、 が得られ、ここでは を使用しました。 ${\displaystyle |\Psi _{1}\rangle }$${\displaystyle U_{C}}$$${\displaystyle U_{C}(|k\rangle \otimes |\psi \rangle )=|k\rangle \otimes (U^{k}|\psi \rangle ),}$$${\displaystyle k=0,...,2^{n}-1}$$${\displaystyle U_{C}=\sum _{k=0}^{2^{n}-1}|k\rangle \!\langle k|\otimes U^{k​​},}$$${\displaystyle U^{k​​}}$${\displaystyle |k\rangle }$${\displaystyle |\psi \rangle }$${\displaystyle U_{C}}$${\displaystyle |\Psi _{1}\rangle }$$${\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 ,}$$${\displaystyle U^{k​​}|\psi \rangle =e^{2\pi ik\theta }|\psi \rangle }$

も効率的に実装できることを示すために、 と書けることに注目してください。ここで、 は、最初のレジスタの - 番目の量子ビットが である条件付きで 2 番目のレジスタにを適用する操作を表します。正式には、これらのゲートは、その動作によって次のように特徴付けられます。この式は、 のとき、つまり- 番目の量子ビットが のとき、状態は変更されないままであり、 - 番目の量子ビットのとき、ゲートは2 番目のレジスタに適用される、と解釈できます。したがって、これらの制御ゲートの合成は となり、最後のステップはバイナリ分解 から直接続きます。 ${\displaystyle U_{C}}$${\displaystyle U_{C}=\prod _{\ell =0}^{n-1}C_{\ell }(U^{2^{\ell }})}$${\displaystyle C_{\ell}(U^{2^{\ell}})}$${\displaystyle U^{2^{\ell}}}$${\displaystyle \ell}$${\displaystyle |1\rangle }$$${\displaystyle C_{\ell }(U^{k})(|j\rangle \otimes |\psi \rangle )=|j\rangle \otimes (U^{j_{\ell }k}|\psi \範囲)。}$$${\displaystyle j_{\ell}=0}$${\displaystyle \ell}$${\displaystyle |0\rangle }$${\displaystyle U^{k​​}}$${\displaystyle \ell}$${\displaystyle |1\rangle }$$${\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},}$$${\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}$

この時点から、2 番目のレジスタはそのまま残されるため、アルゴリズムの残りの部分で考慮する必要がある唯一の -qubit レジスタ の状態を使用して と記述すると便利です。${\displaystyle |\Psi _{2}\rangle =|{\チルダ {\Psi }}_{2}\rangle \otimes |\psi \rangle }$${\displaystyle |{\チルダ {\Psi }}_{2}\rangle }$${\displaystyle n}$

回路の最後の部分では、逆量子フーリエ変換（QFT）を最初のレジスタに適用します。QFTとその逆は、基底状態に対する作用によって次のように特徴付けられます。 ${\displaystyle {\mathcal {QFT}}}$${\displaystyle |\Psi _{2}\rangle }$$${\displaystyle |{\チルダ {\Psi }}_{3}\rangle ={\mathcal {QFT}}_{2^{n}}^{-1}|{\チルダ {\Psi }}_{ 2}\rangle .}$$$${\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}}}$$

${\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 .}$

状態を計算基底で分解すると、係数は と等しくなります。ここで、は に最も近い整数であると書きました。差は 定義により を満たしている必要があります。これは、 の値を最も近い整数に 丸めて近似することに相当します。${\textstyle |{\tilde {\Psi }}_{3}\rangle =\sum _{x=0}^{2^{n}-1}c_{x}|x\rangle ,}$$${\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},}$$${\displaystyle 2^{n}\theta =a+2^{n}\delta ,}$${\displaystyle a}$${\displaystyle 2^{n}\theta }$${\displaystyle 2^{n}\delta }$${\displaystyle 0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}}$${\displaystyle \theta \in [0,1]}$${\displaystyle 2^{n}\theta }$

最後のステップでは、最初のレジスタの計算基底で測定を実行します。これにより、確率 で結果が算出されます。したがって、 、つまり がと表記できる場合、常に結果 が得られます。一方、 の場合、確率は となります。この式から、のとき であることがわかります。これを確認するには、 の定義から不等式 が得られることに着目します。したがって、次の式が成り立ちます。^{[4] : 157  [5] : 348}${\displaystyle |y\rangle }$$${\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}.}$$${\displaystyle \operatorname {Pr} (a)=1}$${\displaystyle \delta =0}$${\displaystyle \theta }$${\displaystyle \theta =a/2^{n}}$${\displaystyle y=a}$${\displaystyle \delta \neq 0}$$${\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}.}$$${\displaystyle \Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405}$${\displaystyle \delta \neq 0}$${\displaystyle \delta }$${\displaystyle |\delta |\leqslant {\tfrac {1}{2^{n+1}}}}$$${\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\\[6pt]&={\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}\\[6pt]&={\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\sin(\pi \delta )|^{2}}}\\[6pt]&\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 |\\[6pt]&\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}}}\\[6pt]&\geqslant {\frac {4}{\pi ^{2}}}.\end{aligned}}}$$

このアルゴリズムは、少なくとも の確率での最良のビット推定値（つまり、正解の以内にある推定値）を提供するという結論に達しました。 のオーダーの数の余分な量子ビットを追加し、余分な量子ビットを切り捨てることで、確率は まで増加します。^[5]${\displaystyle n}$${\displaystyle 1/2^{n}}$${\displaystyle \theta }$${\displaystyle 4/\pi ^{2}}$${\displaystyle O(\log(1/\epsilon ))}$${\displaystyle 1-\epsilon }$

アルゴリズムの最も単純な例を考えてみましょう。ここでは、をエンコードするために必要な量子ビットに加えて、 量子ビットのみが関係します。 の固有値が、を読み取ると仮定します。アルゴリズムの最初の部分では、1 量子ビットの状態 が生成されます。この場合、逆 QFT を適用することは、アダマール ゲートを適用することと同じです。したがって、最終的な結果の確率は となり、ここで、またはより明確には 、つまり と仮定します。すると、となり、測定結果から の正確な値を確定的に回復します。 の場合も同様です。 ${\displaystyle n=1}$${\displaystyle |\psi \rangle }$${\displaystyle |\psi \rangle }$${\displaystyle \lambda =e^{2\pi i\theta }}$${\displaystyle \theta \in [0,1)}$${\textstyle |\phi \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle +\lambda |1\rangle )}$${\displaystyle p_{\pm }=|\langle \pm |\phi \rangle |^{2}}$${\textstyle |\pm \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle \pm |1\rangle )}$$${\displaystyle p_{\pm }={\frac {|1\pm \lambda |^{2}}{4}}={\frac {1\pm \cos(2\pi \theta )}{2}}.}$$${\displaystyle \lambda =1}$${\displaystyle |\phi \rangle =|+\rangle }$${\displaystyle p_{+}=1}$${\displaystyle p_{-}=0}$${\displaystyle \lambda }$${\displaystyle \lambda =-1}$

一方、の場合は、 つまり となり、となります。 この場合、結果は決定論的ではありませんが、 が0 よりも 1 に近いという事実と矛盾せず、結果の方が可能性が高いことがわかります。 ${\displaystyle \lambda =e^{2\pi i/3}}$${\displaystyle p_{\pm }=[1\pm \cos(2\pi /3)]/2}$${\displaystyle p_{+}=1/4}$${\displaystyle p_{-}=3/4}$${\displaystyle |-\rangle }$${\displaystyle 2/3}$

より一般的には、 の場合、 の場合に限ります。に対応するの場合、位相は決定論的に取得され、他の位相はこれら 2 つの位相に近いほど高い精度で取得されるため、これは上記の結果と一致しています。 ${\displaystyle \lambda =e^{2\pi i\theta }}$${\displaystyle p_{+}\geq 1/2}$${\displaystyle |\theta |\leq 1/4}$${\displaystyle \lambda =\pm 1}$${\displaystyle \theta =0,1/2}$

• ショアのアルゴリズム
• 量子カウントアルゴリズム
• パリティ測定