Rokiのチラ裏

学生による学習のログ

量子力学と量子コンピューターについての学習メモ #4

reading Quantum mechanics

シリーズとしては少し間が空いてしまったが前回の続き

ショアのアルゴリズム

ショアのアルゴリズムは、有名な因数分解の量子計算アルゴリズムである。因数分解したい数を $N \in \mathbb{N}$ とする。

まず $N$ に対して、お互いに約数を持たないような $N$ より小さい数 $x$ を決める。 $x$ と $N$ が互いに約数を持つかはユークリットの互除法で判定する。
$N$ と $x$ を用いて、 $\frac{x^{r}}{n}$ のあまりが 1 を満たす自然数 $r$ を探す。
- $x^{r} \in \mathbb{N}$ で、たまたま $x^{r} \bmod N= 1$ だったとした時、 $x^{r+m} \pmod N = x \bmod N$ ( $m \in \mathbb{N}$ を満たす)であり、横軸に $x$ の累乗の指数( $y$ とする)、縦軸に $x^{y} \bmod N$ を表すと、 $y$ が 1 から始まり $r$ に至るまで、 $x^{y} \bmod N$ は $y$ に応じて様々な値となるが、 $y = r$ となる部分であまりが 1 となり、グラフは周期的にそのパターンを繰り返す。この周期がわかれば $r$ が求められるため、量子フーリエ変換を量子ビットの確率振幅に行う。
この時に求まった $r$ が奇数だった場合、手順 1. に戻り $x$ を選び直してやり直す。この場合、 $r$ は偶数なので、次の手順に進む。
この段階で $\frac{x^{r}}{N}$ のあまりは 1 となっているはずである。つまり、 $(x^{r}-1)$ は $N$ の整数倍となっているはずだ。一方で $(x^{r}-1)$ は、 $(x^{\frac{r}{2}} + 1)$ と $(x^{\frac{r}{2}} - 1)$ を掛け合わせたものであり、その二つのどちらかと $N$ は公約数を持っているはずである。今 $(x^{\frac{r}{2}} +1)$ と $N$ の最大公約数を $z$ とすると、 $z$ はすなわち $N$ の因数なので、これで $N$ の因数分解ができたことになる。