Quantum Phase Estimation による Order finding アルゴリズム

複数固有値に対する推定

enakai00.hatenablog.com

上記の記事で解説した位相推定の量子回路（下図）では、状態 ${\mid u\rangle}$ はユニタリ演算子 $U$ の特定の固有値に属する固有状態でした。

それでは、複数の固有値に対する固有状態の重ね合わせの場合、どうなるでしょうか？

結論から言うと、最後の逆フーリエ変換の出力は、それぞれの固有値に対応する状態の重ね合わせになります。

たとえば、 $\varphi_0 = [0.j_1^{(0)}\cdots j_n^{(0)}]$ と $\varphi_1 = [0.j_1^{(1)}\cdots j_n^{(1)}]$ の固有状態 ${\mid u_0\rangle}$ 、 ${\mid u_1\rangle}$ の重ね合わせ $\displaystyle {\mid u\rangle} = \frac{1}{\sqrt{2}}\left({\mid u_0\rangle}+{\mid u_1\rangle}\right)$ に対しては、最後の出力は、

　 $\displaystyle \frac{1}{\sqrt{2}}\left({\mid j_1^{(0)}\rangle}\otimes\cdots\otimes{\mid j_n^{(0)}\rangle} + {\mid j_1^{(1)}\rangle}\otimes\cdots\otimes{\mid j_n^{(1)}\rangle} \right)$

となります。従って、これを観測すると等確率で $[j_1^{(0)}\cdots j_n^{(0)}]$ もしくは $[j_1^{(1)}\cdots j_n^{(1)}]$ という結果が得られます。

これは次の簡単な計算で確認できます。たとえば、先の量子回路の一番下の量子ビット（および Second register）の変化は次になります。

　 $\displaystyle {\mid 0\rangle}\otimes {\mid u\rangle} \longrightarrow \frac{1}{\sqrt{2}}\left({\mid 0\rangle}+{\mid 1\rangle}\right)\otimes {\mid u\rangle}$ （ $H$ 演算）

　　 $\displaystyle \longrightarrow \frac{1}{2}\left\{ {\mid 0\rangle} \otimes \left({\mid u_0\rangle} + {\mid u_1\rangle}\right)+ {\mid 1\rangle}\otimes \left(e^{2\pi i \times [j_1^{(0)}\cdots j_n^{(0)}]} {\mid u_0\rangle} + e^{2\pi i \times [j_1^{(1)}\cdots j_n^{(1)}]}{\mid u_1\rangle}\right) \right\}$ （Controlled- $U$ 演算）

　　　　 $=\displaystyle \frac{1}{2}\left\{ \left( {\mid 0\rangle} + e^{2\pi i \times [j_1^{(0)}\cdots j_n^{(0)}]} {\mid 1\rangle}\right)\otimes {\mid u_0\rangle}+ \left({\mid 0\rangle} + e^{2\pi i \times [j_1^{(1)}\cdots j_n^{(1)}]} {\mid 1\rangle}\right)\otimes {\mid u_1\rangle} \right\}$

他の量子ビットについても同様で、全体として、2種類の計算を個別に行って、結果を重ね合わせたものと同じになります。（量子回路演算の線形性を考えると、実は当たり前なのですが。。。。）

これから位相情報を取り出す逆フーリエ変換もまた、線形変換なので、結果は、個別に計算したものの重ね合わせと同じにものになります。

Cirq による実験例はこちらにあります。

github.com

Order finding

「 $x,\,N$ を適当な自然数として、 $x^r = 1\mod N$ となる最小の自然数 $r$ を発見する」という問題を考えます。

これは、「 $\mod N$ で $x$ 倍する」というユニタリ演算 $U$ に対する固有値から解くことができます。 ${\mid x\rangle}$ を自然数 $x$ の各桁を量子ビットで表現した状態として、 $U$ は次で定義されます。

　 $U {\mid y\rangle} = {\mid xy\mod N\rangle}$

これは、 $s = 0,\cdots r-1$ として、次の $r$ 個の固有状態を持ちます。

　 $\displaystyle {\mid u_s\rangle} := \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}\exp\left(-2\pi i\frac{sk}{r}\right){\mid x^k\mod N\rangle}$

直接計算から分かるように、固有値は $\displaystyle\exp\left(2\pi i\frac{s}{r}\right)$ です。

そして、これらの固有状態をすべて重ね合わせると、ちょうど ${\mid 1 \rangle}$ になります。これも直接計算でわかります。

　 $\displaystyle \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}{\mid u_s\rangle} = {\mid 1 \rangle}$

したがって、冒頭の量子回路で、Second registor を ${\mid 1 \rangle}$ に初期化して、演算子 $U$ に対する位相推定を行うと、 $\displaystyle\frac{s}{r}$ （ $s=0,\cdots,r-1$ ）のいずれか１つが得られます。得られた値に対して、「互いに素な値による既約分数として表す」ための既知のアルゴリズム（Continued fractions）を適用すると、 $s$ と $r$ が個別に決定されます。これで、先ほどの問題の解 $r$ が得られます。（運悪く $\displaystyle\frac{s}{r}=0$ が観測された場合は、測定をやり直します。）