量子コンピュータにおける素因数分解(5): 位数推定と量子干渉

はじめに

この記事は量子コンピュータによる素因数分解のアルゴリズムである「Shorのアルゴリズム」の解説記事第5回目です。1-4回目は以下：

• 量子コンピュータにおける素因数分解(1): 加算器
• 量子コンピュータにおける素因数分解(2): べき剰余
• 量子コンピュータにおける素因数分解(3): 量子フーリエ変換
• 量子コンピュータにおける素因数分解(4): アルゴリズムの方針 & 関連定理

本記事では位数の推定と量子干渉との関係を、Ref.EkertHosoyaに従って議論します。Shorの元論文はRef.Shorです。

前回の記事で述べたように、量子回路で
$$\begin{array}{}\text{(1)}& x^r=1\text{ mod }N(\text{整数}x\text{と}N\text{は互いに素}。x<N)\end{array}$$
を満たす$r$（そのうち最小の$r$は位数と呼ばれる）が多項式時間で計算可能ならば、素因数分解は古典コンピュータより本質的に高速で計算できます。ここで「多項式時間で計算可能」とは、整数$N$を2進数表示したとき、計算量がその桁数の多項式で表されるという意味です。すなわち計算量がある$k\in \mathbb{N}$に対し$\mathcal{O}(({\log }_{2}N{)}^k)$であるということです。

これが可能であることを以下見ます。そのために本記事では本シリーズの最初の3記事で議論した

を用います。これらについて知りたい方は上記のリンクをご参照ください。また前回までの記事にあるように、$|j⟩(j\text{は}0\le j<2^n\text{をみたす整数})$とは、$j$を2進数表示した各桁を$j_i\in \{0,1\}(i=0,1,2,\cdots ,n-1)$として
$$\begin{array}{r}|j⟩:=|j_0⟩|j_1⟩\cdots |j_{n-1}⟩\end{array}$$
のことです（2値をとる量子状態$|0⟩,|1⟩$の存在は仮定します）。

位数の決定

改めて以下の問題を解くことを考えます：

まず$q=2^L\ge N^2$なる、2のべき乗である$q$を導入します。さらに$L$ビットの$|0⟩$を用意します。これに${\text{DFT}}_q$（前章の2.参照）を作用させれば

$$\begin{array}{}\text{(1)}& \frac{1}{\sqrt{q}}\sum _{a=0}^{q-1}|a⟩\end{array}$$

を得ます。さらに別のレジスターを用意し、これに$x^a\text{ mod }N$を作る量子回路を作用させることで

$$\begin{array}{}\text{(2)}& \frac{1}{\sqrt{q}}\sum _{a=0}^{q-1}|a⟩|x^a\text{ mod }N⟩\end{array}$$

を得ます。

$|x^a\text{ mod }N⟩$のレジスターを観測します。ここで$r$を$x$の$\text{mod }N$に関する位数とします。このとき$x^l\equiv x^{jr+l}\text{ mod }N$（$j=0,1,2,\cdots ,\lfloor (q-l-1)/r\rfloor$）です。ここで$\lfloor a\rfloor$は床関数であり、「$a$を超えない最大の整数」を表します。ここで$l<r$は実際には観測により確率的に選ばれます。$l<r<N$また$q\approx \mathcal{O}(N^2)$なので$(q-l-1)/r\approx q/r$です。$|x^a\text{ mod }N⟩$を観測したのちの状態は

$$\begin{array}{}\text{(3)}& |{\varphi }_l⟩=\frac{1}{\sqrt{A+1}}\sum _{j=0}^{\lfloor (q-l-1)/r\rfloor }|jr+l⟩\end{array}$$

となります。

この状態から$r$の情報を得ることを考えます。もしも$l$を固定できるなら、この状態自体を観測しても$r$はわかるはずです。なぜなら観測される$jr+l$は最初に$l$だけのインターバルがありその後$r$の幅で存在するからです（図1）。$l$を固定して何度も観測を続ければ、得られた$jr+l$の$l$のインターバルを除いた部分の幅から$r$を推定できます。しかしながら$l$を固定することはできないし、また何度も観測を繰り返さなくてはなりません。

Eq.(3)の状態を観測した際に得られる$jr+l$の値の分布

そこでEq.(3)に${\text{DFT}}_q$を施します。

$q/r$が整数の場合

まずは分かり易さと直感的な理解のため、$\mathit{q}/r$が整数の場合を考えます。$(l+1)/r\le 1$より、このとき$\lfloor (q-l-1)/r\rfloor =q/r-1$となります。よって

$$\begin{array}{r}|{\varphi }_l⟩=\sqrt{\frac{r}{q}}\sum _{j=0}^{q/r-1}|jr+l⟩=\sum _{a=0}^{q-1}f(a)|a⟩,\\ f(a)=\sqrt{\frac{r}{q}}{\delta }_{a,jr+l},j=0,1,\cdots ,q/r-1\end{array}$$

と表せます。Eq.(3)に${\text{DFT}}_q$を施すと

$$\begin{array}{rl}{\text{DFT}}_q|{\varphi }_l⟩& =\sum _c\tilde{f}(c)|c⟩,\\ \tilde{f}(c)& =\frac{\sqrt{r}}{q}\sum _{j=0}^{q/r-1}\exp \left(\frac{2\pi i(jr+l)c}{q}\right)\\ & =\frac{\sqrt{r}}{q}[\sum _{j=0}^{q/r-1}\exp \left(2\pi i\frac{jrc}{q}\right)]\exp \left(2\pi i\frac{lc}{q}\right)\\ \text{(4)}& & =\frac{\sqrt{r}}{q}[\sum _{j=0}^{M-1}\exp \left(2\pi i\frac{jc}{M}\right)]\exp \left(2\pi i\frac{lc}{q}\right)\end{array}$$

になります。ここで$M:=q/r\in \mathbb{N}$です。方程式$z^n=1$の解をすべて足すとゼロになることから、大括弧の中は$c$が$M$の倍数でない限りゼロになります。すなわち

$$\tilde{f}(c)=\{\begin{array}{ll}\exp \left(2\pi ilc/q\right)/\sqrt{r}& c\text{ が }M\text{ の倍数}\\ 0& \text{それ以外}\end{array}$$

となります。ゆえにEq.(4)の状態において、ある値$c$を観測する確率は Bornの規則 より

$$\begin{array}{r}|\tilde{f}(c){|}^2=\{\begin{array}{ll}1/r& c\text{ が }M\text{ の倍数 }\\ 0& \text{それ以外}\end{array}\end{array}$$

です。これから明らかなように、観測される$c$にはEq.(3)に存在した$l$の依存性がなくなっています（図2参照）。$q/r$が整数の場合はこのような完全な量子干渉が起きます。そして
$$\begin{array}{r}\frac{c}{q}=\frac{\lambda }{r}(\lambda \text{ は整数})\end{array}$$
であり、$q,c$は与えられているので、もしも$\lambda$と$r$が互いに素ならば$\lambda$と$r$が求まります。もしそうでなければ、もう一度$x$を選び直して観測をやりなおします。

Eq.(4)の状態を観測した際に得られる$c$の値の分布

一般の$q/r$

次に一般の（整数とは限らない）$\mathit{q}\mathbf{/}\mathit{r}$を考えます。このときEq.(1)の和の上限は$\lfloor (q-l-1)/r\rfloor$ですが、ここではこれを$q/r-1$とします。こうしても本質的な違いはなく、また議論が明確になります。このときEq.(4)において$M$は整数ではないです。ゆえに、前章では$\exp$の和は対称性から消えたのに対し、Eq.(4)ではそのような正確な相殺は起こりません。

ここで$rc=\alpha q+\beta ,\alpha ,\beta \in {\mathbb{Z}}_{\ge 0},0\le \beta \le q-1$のように書いておきます。これを用いてEq.(4)を書き換えると

$$\begin{array}{rl}\tilde{f}(c)& =\frac{\sqrt{r}}{q}\sum _{j=0}^{q/r-1}\exp (2\pi i(j(\alpha q+\beta )+lc)/q)\\ & =\frac{\sqrt{r}}{q}\exp \left(2\pi ilc/q\right)\sum _{j=0}^{q/r-1}\exp \left(2\pi ij\beta /q\right)\end{array}$$

となります。$\beta =rc\text{ mod }q$なので

$$\begin{array}{r}=\frac{\sqrt{r}}{q}\exp \left(2\pi ilc/q\right)\sum _{j=0}^{q/r-1}\exp (2\pi ij(rc\text{ mod }q)/q)\end{array}$$

です。ゆえに$c$を観測する確率$\text{Prob}(c)$は

$$\begin{array}{}\text{(5)}& \text{Prob}(c)=|\tilde{f}(c){|}^2=\frac{r}{q^2}{|\sum _{j=0}^{q/r-1}\exp (2\pi ij(rc\text{ mod }q)/q)|}^2\end{array}$$

です。

ここでEq.(5)の$\exp$内の$c$が

$$\begin{array}{}\text{(6)}& -r/2\le rc\text{ mod }q\le r/2\end{array}$$

を満たす場合を考えます。このとき$\exp$の各項は複素平面上の半円の中に存在するため、その和は小さくはならないです。また、Eq.(6)をみたす$c$はちょうど$r$コ存在することに注意してください。これは以下の図からわかります：

Eq.(6)を満たす$c$の値の数が$r$コであることの説明の図

青い点線は$q$の倍数（$0,1,2,\dots ,(r-1)q$）であり、これを$r$の倍数（$0,r,2r,\dots (q-1)r$）に重ねています。$r$の倍数は間隔$r$で存在しているのだから、点線から幅$r/2$の間（緑のアーチ）に存在する$r$の倍数は当然唯一つです。青い点線はrコ存在するから、Eq.(6)を満たす$c$は$r$コ存在します。

$\text{Prob}(c)$の大きさを、Eq.(6)を満たす$c$に対して見積ります。${\theta }_c=2\pi (rc\text{ mod }q)/q$を定義すると、$\text{Prob}(c)$は$\exp i{\theta }_c$の比をもつ等比級数からできています。この級数は${\theta }_c$が増加するにつれて減るので、$\text{Prob}(c)$も${\theta }_c$が大きくなると減ります。よって

$$\text{Prob}(c)\ge \text{Prob}({\theta }_c\text{ を最大にする}c)$$

が成立します。ここでEq.(6)より${\theta }_c\le \pi r/q$です。等号が成立するとき、和は初項が$1$、公比が$\exp \left(i\pi r/q\right)$、項数は$q/r-1+1=q/r$である等比級数なので

$$\begin{array}{rl}\text{Prob}(c)& \ge \frac{r}{q^2}{\left|\frac{1-\exp (i\frac{\pi r}{q}\cdot \frac{q}{r})}{1-\exp \left(i\frac{\pi r}{q}\right)}\right|}^2\\ & =\frac{r}{q^2}{\left|\frac{2}{1-\exp \left(i\frac{\pi r}{q}\right)}\right|}^2\\ & =\frac{r}{q^2}\frac{4}{(1-\exp \left(i\frac{\pi r}{q}\right))(1-\exp (-i\frac{\pi r}{q}))}\\ & =\frac{r}{q^2}\frac{2}{1-\cos \left(\frac{\pi r}{q}\right)}\\ & =\frac{r}{q^2}\frac{1}{{\sin }^2(\frac{\pi r}{2q})}\\ & \sim \frac{r}{q^2}\frac{1}{\frac{{\pi }^2{r}^2}{4q^2}}=\frac{4}{{\pi }^2}\frac{1}{r}\end{array}$$

となります（※$q/r$は整数ではないですが、小数部分の影響は軽微です）。ここで$q/r$が小さいとして$\sin \pi r/2q\approx \pi r/2q$としました。よって、$r$コ存在するそのような$c$に対して、Eq.(6)をみたす$c$を観測する確率は$4/{\pi }^2\simeq 0.4$より大きいことがわかります。すなわちEq.(6)を満たす$c$を観測する可能性は十分大きいです。

$r$の決定と連分数展開

Eq.(6)を満たす$c$が与えられたとき、$r$の情報を引き出すことを考えます。これを行うには、Eq.(6)が、ある$0\le c^{\prime }\le r-1$を満たす$c^{\prime }$に対して

$$\begin{array}{}\text{(7)}& |rc-c^{\prime }q|\le r/2\end{array}$$

と書き直せることを用います。この式は次のように解釈できます: $c^{\prime }q$とは図1における$q$軸にプロットした点のことであり、$rc$とは図1における$r$軸にプロットした青点線から$r/2$の範囲にある点のことです。このことからわかるように、Eq.(6)を満たす$r$コの$c$に対してちょうど1つづつ対応する$c^{\prime }$が存在します。ゆえに$c^{\prime }$のそれぞれの値に対し$c$と同様

$$\text{Prob}(c^{\prime })\ge \frac{4}{{\pi }^2}\frac{1}{r}$$

となります。Eq.(5)は以下のように書けます：

$$\begin{array}{}\text{(8)}& |\frac{c}{q}-\frac{c^{\prime }}{r}|\le \frac{1}{2q}\end{array}$$

ここで$c,q$はわかっていて、また$r\le N,q\ge N^2$です。Eq.(8)は、与えられた$c/q$をこの不等式を満たすある有理数$c^{\prime }/r$で近似せよ、ただしその分母は$N$未満である、ということを言っています。Eq.(8)の範囲には分母が$N$以下である$c^{\prime }/r$が最大で1つ存在します。すなわち観測から$c$が得られれば、$c^{\prime }/r$（$r<N$）が唯一に定まります。

ただし$c^{\prime }$と$r$が互いに素である必要があります。$0\le c^{\prime }\le r-1$のうち$r$と互いに素な$c^{\prime }$の個数は、 前回の記事 で導入したオイラー関数$\phi (r)$コです。よってそのような$c^{\prime }$を得る確率は上で求めた$\text{Prob}(c^{\prime })$に$\phi (r)$をかけて
$$\begin{array}{}\text{(9)}& \text{Prob}(c^{\prime })\ge \frac{4}{{\pi }^2}\frac{\phi (r)}{r}\end{array}$$
となります。

$c^{\prime }$と$r$を決定するには連分数展開を用います。連分数展開に関しては この記事 noteにまとめました。具体的な計算法等の詳細はこれを読んでもらうことにして（すぐ読めます）、ここでは$c,q$が与えられたとき、Eq.(8)を満たす$c^{\prime }/r$を連分数展開を用いて具体的に求めてみます。以下Ref.Hosoyaにある例です:

Ref.Hosoyaの練習問題には$c=77,149$の場合の$r$を求めよという問題が載っています。これも解いておきます：

本来$r$は、$N$と互いに素なある数$x$に関してEq.(1)を満たす数です。 前回の記事 で見たように、$x^{r/2}\pm 1$がどちらも$N$の倍数でない限り、$\text{gcd}(x^{r/2}\pm 1,N)$のどちらかは$N$の因数を与えます。「$x^{r/2}\pm 1$がどちらも$N$の倍数でない」は満たされない可能性があるので古典計算機でチェックします。条件が満たされなかった場合はもう一度$x$を選び直して同様なことを繰り返します。

計算量の見積もり

最後に$r$の推定における計算量を大雑把に見積もっておきます。

Shorのアルゴリズムでは以下の計算が行われます：

1. Eq.(1)の${\text{DFT}}_q$
2. Eq.(2)のべき剰余の計算
3. Eq.(4)の${\text{DFT}}_q$
4. Eq.(8)を満たし、$r$と互いに素な$c^{\prime }$を得る試行
5. 適切な$x$を選ぶ試行。すなわち$x$が適切な$r$:「$r$が偶数かつ$x^{r/2}\pm 1$がどちらも$N$の倍数でない」 を持つものを選び出す

まず量子フーリエ変換ですが、必要なゲート数が$N$の桁数の2乗程度です。すなわち(i)(iii)どちらも$({\log }_{2}N{)}^2$程度の計算量です。(ii)のべき剰余の計算は${\log }_{2}N$程度の計算量です。

(iv)に関しては上記したように$4\phi (r)/({\pi }^{2}r)$程度の確率で起きます。$\phi (r)/r$はおよそ$1/\log \log \left(r\right)$程度であることが知られています（ 前回の記事 の定理2参照）。すなわち$4\phi (r)/({\pi }^{2}r)$は十分高い確率であるので、この試行を繰り返す計算量はほぼ無視できることがわかります。(v)に関しても 前回の記事 の定理3で見たように非常に高い確率で起きます。すなわち(i)-(iii)以外の過程は計算量としては殆ど無視できると言えます。

ということで、Shorのアルゴリズムでは多項式時間で$r$を推定することができ、ひいては素因数分解を行うことが可能です。

おしまい & つづく。${}_{◼}$