Shorのアルゴリズム（勉強過程） - tsujimotterの下書きノート

量子コンピュータが話題になっている昨今ですが、そのきっかけの一つとなったのは、素因数分解ができるという量子アルゴリズム「Shorのアルゴリズム」でしょう。

以前から、その仕組みを理解したいと思っていたのですが、よいきっかけがあったので少しずつ勉強してみようと思います。その勉強過程をここにまとめます。現時点での理解を書いているので、間違っているかもしれませんから信用はなさらないでください。

数論パート

Shorのアルゴリズムの問題設定としては、 $N$ という自然数の約数を求めたいという問題です。

まず、ランダムに $a < N$ をとってきます。これが $N$ の約数ならもうここでおしまいです。そうでない場合も、もし $\operatorname{gcd}(a, N) > 1$ であれば、それが $N$ の約数なのでおしまいです。

そこで、 $\operatorname{gcd}(a, N) = 1$ の場合を考えます。そんなときでも、 $a$ の $\bmod{N}$ の位数が分かれば、非自明な因数が得られます。その方法については、本当に初等整数論的に理解できます。

$a^r \equiv 1 \pmod{m}$ なる最小の $r$ のことを $\bmod{N}$ の位数といいます。 $a$ が $N$ と互いに素であれば、 $(\mathbb{Z}/N\mathbb{Z})^\times$ が群を成すことから必ず位数を持ちます。これが計算でき、かつ、 $r$ が偶数である場合、 $r/2$ は整数になりますので $a^{r/2}$ が計算できます。このことを念頭に

$a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod{N}$

なる因数分解を考えます。すると、 $(a^{r/2} - 1)(a^{r/2} + 1)$ が $N$ で割り切れることになります。したがって、 $a^{r/2} - 1$ か $a^{r/2} + 1$ の少なくともどちらか一方に $N$ の非自明な約数があるわけですね。

なるほど、たしかに $a$ の位数 $r$ が見つかって、それが偶数であれば $N$ の非自明な約数が見つかるわけですね。 $r$ が奇数のときは、残念ながらこの方法では約数を見つけられませんので、 $a$ を棄却して再度やり直しです。偶数位数の元は必ず存在しますので、いつかはいい感じの $a$ が見つかります。

そこで、 $a \bmod{N}$ の位数を探す旅に出るわけですね。ここまでは古典コンピュータで計算できる話なので、以降が本質的に量子アルゴリズムの領域となります。