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

はじめに

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

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

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

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

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

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

位数の決定

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

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

$$\hspace{1.5cm}\frac{1}{\sqrt{q}}\sum_{a=0}^{q-1}|a\rangle \tag{1}$$

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

$$\hspace{1.5cm}\frac{1}{\sqrt{q}}\sum_{a=0}^{q-1}|a\rangle|x^a\text{ mod }N\rangle \tag{2}$$

を得ます。

$|x^a\text{ mod }N\rangle$のレジスターを観測します。ここで$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\rangle$を観測したのちの状態は

$$\hspace{1.5cm} |\phi_l\rangle=\frac{1}{\sqrt{A+1}}\sum_{j=0}^{\lfloor (q-l-1)/r\rfloor}|jr+l\rangle\tag{3}$$

となります。

この状態から$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$が整数の場合

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

\begin{align} \hspace{1.5cm}|\phi_l\rangle=\sqrt{\frac{r}{q}}\sum_{j=0}^{q/r-1}|jr+l\rangle=\sum_{a=0}^{q-1}f(a)|a\rangle,\\ f(a)=\sqrt{\frac{r}{q}}\delta_{a,jr+l}, \ \ \ j=0,1,\cdots,q/r-1 \end{align}

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

\begin{align*} \hspace{1.5cm} \text{DFT}_q|\phi_l\rangle&=\sum_c\tilde f(c)|c\rangle,\\ \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} \left[ \sum_{j=0}^{q/r-1} \exp\left(2\pi i \frac{jrc}{q}\right) \right] \exp \left( 2\pi i\frac{lc}{q} \right) \\ &=\frac{\sqrt{r}}{q} \left[ \sum_{j=0}^{M-1} \exp\left(2\pi i \frac{jc}{M}\right) \right] \exp \left( 2\pi i\frac{lc}{q} \right)\tag{4} \end{align*}

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

$$\hspace{1.5cm} \tilde f(c)= \begin{cases} \exp(2\pi i lc/q)/\sqrt{r} & c\text{ が }M\text{ の倍数}\\ 0& \text{それ以外} \end{cases} $$

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

\begin{align} \hspace{1.5cm} |\tilde f(c)|^2= \begin{cases} 1/r & c\text{ が }M\text{ の倍数 }\\\ 0 & \text{それ以外} \end{cases} \end{align}

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

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

一般の$q/r$

次に一般の（整数とは限らない）$\boldsymbol{q/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{align} \hspace{1.5cm} \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(2\pi i lc/q)\sum_{j=0}^{q/r-1}\exp(2\pi i j\beta/q) \end{align}

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

\begin{align} \hspace{1.5cm} =\frac{\sqrt{r}}{q}\exp(2\pi i lc/q)\sum_{j=0}^{q/r-1}\exp(2\pi i j(rc\text{ mod }q)/q) \end{align}

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

$$ \hspace{1.5cm}\text{Prob}(c)=|\tilde f(c)|^2=\frac{r}{q^2} \left| \sum_{j=0}^{q/r-1}\exp(2\pi i j(rc\text{ mod }q)/q) \right|^2\tag{5} $$

です。

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

$$\hspace{1.5cm} -r/2\le rc\text{ mod }q\le r/2\tag{6} $$

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

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

青い点線は$q$の倍数（$0,1,2,…,(r-1)q$）であり、これを$r$の倍数（$0,r,2r,…(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$が大きくなると減ります。よって

$$\hspace{1.5cm} \text{Prob}(c)\ge \text{Prob}(\theta_c\text{ を最大にする} c) $$

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

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

となります（※$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' \le r-1$を満たす$c'$に対して

$$ \hspace{1.5cm} |rc-c'q|\le r/2 \tag{7} $$

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

$$\hspace{1.5cm} \text{Prob}(c')\ge \frac{4}{\pi^2}\frac{1}{r} $$

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

$$\hspace{1.5cm} \left|\frac{c}{q}-\frac{c'}{r}\right|\le \frac{1}{2q} \tag{8} $$

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

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

$c'$と$r$を決定するには連分数展開を用います。連分数展開に関しては この記事 noteにまとめました。具体的な計算法等の詳細はこれを読んでもらうことにして（すぐ読めます）、ここでは$c,q$が与えられたとき、Eq.(8)を満たす$c'/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'$を得る試行
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\varphi(r)/(\pi^2 r)$程度の確率で起きます。$\varphi(r)/r$はおよそ$1/\log\log(r)$程度であることが知られています（ 前回の記事 の定理2参照）。すなわち$4\varphi(r)/(\pi^2 r)$は十分高い確率であるので、この試行を繰り返す計算量はほぼ無視できることがわかります。(v)に関しても 前回の記事 の定理3で見たように非常に高い確率で起きます。すなわち(i)-(iii)以外の過程は計算量としては殆ど無視できると言えます。

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

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