Factoring(ショアの素因数分解) 〜Quantum Zooやっていく〜

July 17, 2021, 9:16 a.m. edited July 22, 2021, 6:51 a.m.

#Quantum Zoo  #量子情報  #量子力学 

$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$

なんだかんだ量子1アルゴリズム、 Grover と Shor しか知らないので、 Quantum Zoo をやっていく突貫企画。 多分すぐ更新は途絶える

ということで初回はお馴染み Factoring (素因数分解)

ここに訳を、と思ったが、なんか昔の翻訳記事は翻訳に許可とったりしてて、私はそんな手間をとりたくないので、英語読んで。

背景

\(n\) ビットの整数を素因数分解する最速の古典アルゴリズムは \(2^{\tilde{O}(n^{1/3})}\) であったが、 Peter Shor が開発した量子アルゴリズムにより \(\tilde{O}(n^3)\) となった2。すごい

問題

ある整数 \(N\) が与えられたとき、それを割り切ることのできる整数 \(p\in[1,N-1]\) を見つける。

アルゴリズム

[P. Shor, 1996] のアルゴリズムに従いたかったが、提案当初、という感じでなんか難しかったので、 ここ に載ってるものにしたがう3(ただ、このサイト、一部で \(a^r\) が \(ar\) になっちゃってるね・・)。

古典パート

ランダムに整数 \(a\in[2,N-1]\) を選ぶ。そして、最大公約数 \(\gcd(a, N)\) を計算4する。これでもしも 1 ではない最大公約数が見つかれば古典だけで終わり。そうでない場合は、以下の量子パートに進む。

量子パート

$$f(x):=a^x \bmod N$$

と定義する5。このとき、

$$f(x+r)=f(x)$$

を満たす \(r\) を探す。はじめに

$$\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\ket{x}\ket{0}$$

という状態を用意する。それから \(f\) を計算する。

$$\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\ket{x}\ket{f(x)}$$

ここに量子フーリエ変換6 \(U_{QFT}\) を適用する。

$$\frac{1}{N}\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}e^{2\pi ixy/N}\ket{y}\ket{f(x)}$$

ここで、 2 つのレジスタ(\(\ket{y}\) と \(\ket{f(x)}\))を測定して \(y\) および \(f(x_0)\) (\(x_0\in[0,N-1]\)) が得られる確率は

$$\frac{1}{N^2}\left|\sum_{x\ \mathrm{where}\ f(x)=f(x_0)}e^{2\pi ixy/N}\right|^2=\frac{1}{N^2}\left|\sum_b e^{2\pi i(x_0+br)y/N}\right|^2$$

となる。つまり、 \(f\) は \(r\) ごとに同じ値をとる周期関数なので、共通の \(y\) および \(f(x)=f(x_0)\) となる項が複数存在し、それらは \(r\) を何回掛けて \(x_0\) に足すかという形で整数 \(b\) を用いて右辺のように表される。このとき、 \(ry/N\) が整数であれば

$$e^{2\pi i(x_0+br)y/N}=e^{2\pi i(x_0+(b+1)r)y/N}$$

となることから確率は大きくなる(つまり、打ち消し合わないで済むということ)ので、大体それを満たす \(y\) が観測される。さらに、この観測された \(y\) を用いて \(y/N\) を計算できるが、これは整数 \(m\) を用いると

$$\frac{ry}{N}=m$$ $$\frac{y}{N}=\frac{m}{r}$$

となるため、つまり、 \(y/N\) を既約分数にすると、その分母に \(r\) が出てくることがあるということ。すごい!!・・とは言っても、そんな偶然に頼りたくないので、今回 (\(y=y_1\)) は \(m=m_1\) 、もう一回 (\(y=y_2\)) やったら \(m=m_2\) が得られたとする。すると、

$$y_1=\frac{Nm_1}{r},\ y_2=\frac{Nm_2}{r}$$ $$\frac{y_1}{y_2}=\frac{m_1}{m_2}$$

より、 \(m_1\), \(m_2\) が互いに素であれば7、ここから \(r\) が求まる。

再びの古典パート

こうして得られた \(r\) がもしも奇数だったら、もう一回最初の古典パートからやり直し。また、 \(a^{r/2}\equiv -1\bmod N\) を満たしてしまっていても、もう一回最初の古典パートからやり直し。

大丈夫であれば、

$$\gcd(a^{r/2}\pm 1, N)$$

が答えとなる。

なぜ

詳しいことは上に挙げた wiki 見て。

まず、

$$a^r\equiv 1\bmod N$$

となる \(r\) が存在することを認める(まあ、確かにありそうだし)。すると、 \(a^r-1=(a^{r/2}+1)(a^{r/2}-1)\) は \(N\) で割り切れるということになる(ここで割る 2 できる必要があるため \(r\) は奇数であってはならない。それと、割り切れるだけではまだ \(\gcd(a^{r/2}\pm 1, N)\neq 1\) とは言い切れないのだが、上に挙げた wiki ではこれを背理法により示している)。

そして、この \(r\) は量子パートで用いている \(r\) と同じなの、と疑問も出るが、これは

$$f(x+r)=f(x)$$ $$a^{x+r}\bmod N=a^x\bmod N$$

つまり、

$$a^{x+r}\equiv a^x\bmod N$$

両辺を \(a^x\) で割って

$$a^r\equiv 1\bmod N$$

より、示される。

計算量

QFT が大体 \(O((\log N)^2)=O(n^2)\) で、それからなんだかんだで冒頭に挙げた計算量になるのでしょう(丸投げ)・・・いや、 Wikipedia 見ると、この \((\log N)^2\) に \((\log \log N)(\log \log \log N)\) がくっついているので、つまり QFT 以外の量子ゲート操作を込みで冒頭に挙げた計算量になるということなのかなぁ。。


  1. Mac の Google 日本語入力、いくら量子アルゴリズムと入力してもすぐに忘れて漁師アルゴリズムになるのなんとかならんの?(手動登録なんてしたくないよ。がんばって) 

  2. \(\tilde{O}\) ってなんぞ、となったが、 log を無視するビッグオーのことらしい 

  3. なんか文献によって載ってる Shor のアルゴリズムの内容、違うんだよね。。 

  4. ユークリッドの互除法により \(O(\log N)\) で計算できる 

  5. \(\bmod\) ってなんだっけとなりがちだが、要は \(a\bmod b\) だと \(b\) で \(a\) を割ったときの余りのこと。一方、 \(a\equiv b\bmod c\) は \(a\) を \(c\) で割った余りと \(b\) を \(c\) で割った余りが同じということ(合同式)。なお、合同式では負の値も使える 

  6. \(U_{QFT}\ket{x}=\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}e^{2\pi ixy/N}\ket{y}\) 

  7. 互いに素にならない確率は \(\pi^2/6\) 未満(量子情報科学入門 p.76 に素数の自乗の逆数和を用いた証明が載ってる)