Nielsen and Chuang Exercise 5.21(2)

導入

Nielsen and Chuang 「Quantum Computation and Quantum Information」のExercise 5.21(2)について考えてみた。素人による個人的なメモ。

(2)では $\lvert f(x_0)\rangle$ を第２レジスタに用意できたとして、 $U_y$ で位相推定アルゴリズムを適用するとどういう結論が得られるか問われている。

---

位相推定アルゴリズム

1. 初期状態

   $$\lvert\psi\rangle = \lvert0\rangle \otimes \lvert f(x_0)\rangle$$

2. 重ね合わせ

   $$\frac{1}{\sqrt{2^t}} \sum_{x=0}^{2^t-1} \lvert x\rangle \otimes \lvert f(x_0)\rangle$$

3. 制御シフト $U_y^x$ の適用
   $x=(x_t\ldots x_1)_2$ として

   $$\frac{1}{\sqrt{2^t}} \sum_{x=0}^{2^t-1} \lvert x\rangle\,U_y^{x_t2^{t-1}}\cdots U_y^{x_1 2^0}\,\lvert f(x_0)\rangle \;=\; \frac{1}{\sqrt{2^t}} \sum_{x=0}^{2^t-1} \lvert x\rangle\,\bigl\lvert f(x_0 + x_1y2^0 + \cdots + x_ty2^{t-1})\bigr\rangle \;=\; \frac{1}{\sqrt{2^t}} \sum_{x=0}^{2^t-1} \lvert x\rangle\,\lvert f(x_0 + yx)\rangle$$

4. $\lvert f^{(\ell)}\rangle$による式変形
   式 (5.64) より

   $$\lvert f(x_0 + yx)\rangle = \frac{1}{\sqrt{r}} \sum_{\ell=0}^{r-1} e^{2\pi i\ell(x_0 + yx)/r}\,\lvert f^{(\ell)}\rangle.$$

   これを代入すると…①

   $$\frac{1}{\sqrt{2^t}} \sum_{x=0}^{2^t-1} \lvert x\rangle\,\lvert f(x_0 + yx)\rangle = \frac{1}{\sqrt{r\,2^t}} \sum_{\ell=0}^{r-1} e^{2\pi i\ell x_0/r} \sum_{x=0}^{2^t-1} e^{2\pi i\ell yx/r}\, \lvert x\rangle\,\lvert f^{(\ell)}\rangle$$

5. 逆QFT → 測定
   第１レジスタ

   $$\sum_{x=0}^{2^t-1} e^{2\pi i\ell yx/r}\,\lvert x\rangle$$

   を逆フーリエ変換すると

   $$\frac{1}{\sqrt{r}} \sum_{\ell=0}^{r-1} e^{2\pi i\ell x_0/r}\, \bigl\lvert \ell y / r \bigr\rangle \,\lvert f^{(\ell)}\rangle.$$

   第１レジスタを測定すると $\ell y/r$ を得られ、連分数アルゴリズムにより $r$ が得られる。

---

まとめ

第２レジスタに $\lvert f(x_0)\rangle$ を用意して $U_y$ で位相推定を行っても $r$ を計算することはできる。
また $x_0=0,\,y=1$ と置くと①が

$$\frac{1}{\sqrt{r\,2^t}} \sum_{\ell=0}^{r-1} \sum_{x=0}^{2^t-1} e^{2\pi i\ell x/r}\, \lvert x\rangle\,\lvert f^{(\ell)}\rangle$$

と Period finding の Step 3 と同じ式になるので、
Period finding のアルゴリズムはこの位相推定アルゴリズムの一種とも言える。