導入
Nielsen and Chuang 「Quantum Computation and Quantum Information」のExercise 5.23について考えてみた。素人による個人的なメモ。
定義
式5.73の指数を正とし
\frac{1}{r} \sum_{\ell_1=0}^{r-1} \sum_{\ell_2=0}^{r-1}
e^{2\pi i (\ell_1 x_1 + \ell_2 x_2)/r} \left| \hat{f}(\ell_1, \ell_2) \right\rangle
と定義し直す。
導出
\frac{1}{r} \sum_{\ell_1=0}^{r-1} \sum_{\ell_2=0}^{r-1}
e^{2\pi i (\ell_1 x_1 + \ell_2 x_2)/r} \left| \hat{f}(\ell_1, \ell_2) \right\rangle
= \frac{1}{r} \sum_{\ell_1=0}^{r-1} \sum_{\ell_2=0}^{r-1}
e^{2\pi i (\ell_1 x_1 + \ell_2 x_2)/r}
\left[ \sum_{j=0}^{r-1} e^{-2\pi i \ell_2 j / r} \left| f(0, j) \right\rangle \right]
Exercise 5.22 により、\ell_1 = s\ell_2 \mod r の制約があるので、
和の項は \ell_1 = s\ell_2 \mod r となる場合のみ残る：
= \frac{1}{r} \sum_{\ell_2=0}^{r-1}
e^{2\pi i ((s\ell_2 \mod r) x_1 + \ell_2 x_2)/r}
\left[ \sum_{j=0}^{r-1} e^{-2\pi i \ell_2 j / r} \left| f(0, j) \right\rangle \right]
指数関数の周期性 e^{i\theta} より：
= \frac{1}{r} \sum_{\ell_2=0}^{r-1}
e^{2\pi i \ell_2 (s x_1 + x_2)/r}
\left[ \sum_{j=0}^{r-1} e^{-2\pi i \ell_2 j / r} \left| f(0, j) \right\rangle \right]
= \frac{1}{r} \sum_{j=0}^{r-1}
\left[ \sum_{\ell_2=0}^{r-1} e^{2\pi i \ell_2 (s x_1 + x_2 - j)/r} \right] \left| f(0, j) \right\rangle
等比数列の和により：
= \frac{1}{r} \sum_{j=0}^{r-1} \left[ r \cdot \delta_{s x_1 + x_2,\, j \mod r} \right] \left| f(0, j) \right\rangle
ここで s, x_1, x_2 は固定された値なので、
s x_1 + x_2 \mod r は j の値のうち一つと一致する：
= \left| f(0,\, s x_1 + x_2 \mod r) \right\rangle
= \left| a^{s x_1 + x_2 \mod r} \mod N \right\rangle
= \left| a^{s x_1 + x_2} \mod N \right\rangle
= \left| f(x_1, x_2) \right\rangle
これにより、\left| f(x_1, x_2) \right\rangle を \left| \hat{f}(\ell_1, \ell_2) \right\rangle を使って表現できたので、
改めて Step 3 の導出を行う：
\frac{1}{2^t} \sum_{x_1=0}^{2^t - 1} \sum_{x_2=0}^{2^t - 1}
\left| x_1 \right\rangle \left| x_2 \right\rangle \left| f(x_1, x_2) \right\rangle
= \frac{1}{2^t} \sum_{x_1=0}^{2^t - 1} \sum_{x_2=0}^{2^t - 1}
\left| x_1 \right\rangle \left| x_2 \right\rangle
\left[ \frac{1}{r} \sum_{\ell_1=0}^{r-1} \sum_{\ell_2=0}^{r-1}
e^{2\pi i (\ell_1 x_1 + \ell_2 x_2)/r} \left| \hat{f}(\ell_1, \ell_2) \right\rangle \right]
ここでも \ell_1 = s \ell_2 \mod r の制約により：
= \frac{1}{2^t} \sum_{x_1=0}^{2^t - 1} \sum_{x_2=0}^{2^t - 1}
\left| x_1 \right\rangle \left| x_2 \right\rangle
\left[ \frac{1}{r} \sum_{\ell_2=0}^{r-1}
e^{2\pi i (s \ell_2 x_1 + \ell_2 x_2)/r} \left| \hat{f}(s \ell_2, \ell_2) \right\rangle \right]
= \frac{1}{r \cdot 2^t} \sum_{\ell_2=0}^{r-1}
\left[ \sum_{x_1=0}^{2^t - 1} e^{2\pi i s \ell_2 x_1 / r} \left| x_1 \right\rangle \right]
\left[ \sum_{x_2=0}^{2^t - 1} e^{2\pi i \ell_2 x_2 / r} \left| x_2 \right\rangle \right]
\left| \hat{f}(s \ell_2, \ell_2) \right\rangle
Step 3 では規格化因子が \frac{1}{2^t \sqrt{r}} とされているが、
正確には \frac{1}{r \cdot 2^t} となる。
ただし \frac{1}{r \cdot 2^t} でも後続のアルゴリズムには影響はない。
Discussion