位数を求めるための量子計算機(shorのアルゴリズムの主要部)

ここでは、高い確率で式6.23の条件を満たす$c$を作り出す量子コンピュータを考える。集合$C$を条件式6.23を満たす$c$の集合と定義しておく。

$$C =\{ x\vert \left\vert \frac{d}{r}-\frac{x}{q}\right\vert \le \frac{1}{2q},\gcd (r,d)=1,for\exists d\in \{1,2\cdots r-1\} \}$$ (6.28)

ここでは次のような操作をする。まず、初期状態 $\lvert 0,0 \rangle$を量子コンピュータ$U$に作用させてエンタングルメント状態

$$\hat{U}\lvert 0,0 \rangle =\sum_{x =0}^{q-1}\sum_{z=o}^{q-1}v(x ,z)\lvert x ,z \rangle$$

を引き起こさせ続いて、量$x$を観測する。この観測によって$x \in C$となる$x$を得る確率は

$$P_r \le \sum_{x \in C}P(x )=\sum_{x \in C}\sum_{z=0}^{q-1} \left\vert v(x,z)\right\vert ^2$$ (6.29)

なので、$P_r$が大きくなる様な量子コンピュータ$U$を考えれば良いことになる。ショアーが使った演算子は

$$\hat{U} = (\hat{U}_{QFT}\otimes\hat{I}) \hat{U}_{a,N} (\hat{U}_{QFT}\otimes \hat{I})$$ (6.30)

である。ただし、 $\hat{U}_{QFT}$はフーリエ変換であり、 $\hat{U}_{a,N}$は次式6.31の変換を満たす演算子である(指数関数を計算する量子コンピュータと呼ぶ)。

$$\hat{U}_{a,N}\lvert x,0 \rangle = \lvert x,a^x(modN) \rangle$$ (6.31)

実際にこのショアーの演算子を状態 $\lvert 0,0 \rangle$に作用させてみると

$$\hat{U}\lvert 0,0 \rangle = (\hat{U}_{QFT}\otimes\hat{I}) \hat{U}_{a,N} \frac{1}{\sqrt{q}}\sum_{y=0}^{q-1} \lvert y,0 \rangle$$ (6.32)

$$= (\hat{U}_{QFT}\otimes\hat{I})\frac{1}{\sqrt{q}}\sum_{y=0}^{q-1} \lvert y,a^y(modN) \rangle$$ (6.33)

$$= \frac{1}{q}\sum_{y=0}^{q-1} \sum_{x=0}^{q-1} \exp\left(\frac{2\pi i}{q}xy \right)\lvert x,a^y(modN) \rangle$$ (6.34)

となる。しかし、

$$\{0,1\cdots ,q-1 \} = \{ br+k\vert k=0,1\cdots ,r-1;b=0,1 \cdots \lfloor \frac{q-k-1}{r} \rfloor \}$$ (6.35)

が成り立つことを使って和の取り方を変えてやると

$$\hat{U}\lvert 0,0 \rangle = \frac{1}{q} \sum_{x=0}^{q-1} \sum_{k=... ...or }\exp \left( \frac{2\pi i}{q}x(br+k)\right) \lvert x,a^{br+k} (modN) \rangle$$ (6.36)

しかし、$r$は $a^{r}\equiv 1(modN)$なので

$$a^{br+k}=(a^r)^b a^k\equiv a^k$$ (6.37)

となり、これを上の式に代入して、

$$\hat{U}\lvert 0,0 \rangle = \frac{1}{q} \sum_{x=0}^{q-1} \sum_{k=0}^{r-1} \sum_{b=0}^{\lfloor... ...\rfloor }\exp \left( \frac{2\pi i}{q}x(br+k)\right) \lvert x,a^k (modN) \rangle$$

$$= \frac{1}{q} \sum_{x=0}^{q-1} \sum_{k=0}^{r-1} \exp \left( \frac{2... ...{r} \rfloor } \exp \left( \frac{2\pi i}{q}xbr\right) \lvert x,a^k(modN) \rangle$$

とできるので、観測によってある$x$を得る確率は

$$P(x)=\frac{1}{q^2}\sum_{k=0}^{r-1} \left\vert \sum_{b=0}^{\lfloor \frac{q-k-1}{r}\rfloor} \exp \left( \frac{2\pi i}{q}xbr\right)\right\vert^2$$ (6.38)

となる。これを下から評価するために次のように変形する。

$$\left\vert \sum_{b=0}^{ \lfloor \frac{q-k-1}{r}\rfloor } \exp \left(2\pi i\frac{xr}{q}b\right) \right\vert ^2 = \left\vert \sum_{b=0}^{ \lfloor \frac{q-k-1}{r}\rfloor }\exp \left(2\pi i\frac{xr}{q}-d\right) b \right\vert ^2$$ (6.39)

$$= \frac{1-\cos (\alpha_k\theta )}{1-\cos (\theta )}$$ (6.40)

ただし

$$\left\{ \begin{array}{rl} & \theta = 2\pi i\left( \frac{xr}{... ...lpha_k = \lfloor \frac{q-k-1}{r} \rfloor +1 \end{array}\right.$$

続いて$x$が$C$に含まれるときの確率を考える。$x \in C$ならば $\left\vert \frac{xr}{q}-d \right\vert \le \frac{r}{2q}$より、

$$\vert \theta \vert \le \frac{r}{q}\pi$$ (6.41)

となる。そして$q \ge N^2$と$N\gg1$から、

$$r<N \ll N^2 \leq q$$ (6.42)

よって、式6.42、6.43より

$$\vert\theta \vert \ll \pi$$ (6.43)

なので、式6.41の $\cos\theta$に$\theta$に関する2次までの近似を取り、式6.39は、

$$P(x)=\sum_{k=0}^{r-1}\frac{2\alpha_k^2}{q^2}\frac{1-\cos(\alpha_k\theta )}{(\alpha_k\theta )^2}$$ (6.44)

となるが、

$$\left\vert\alpha_k\theta \right\vert = \left( \lfloor \frac{q-k-1}{r} \rfloor +1 \right) \frac{\pi r}{q} \le \left( \frac{q-k-1}{r}+1 \right) \frac{\pi r}{q}$$ (6.45)

$$= \pi \left( 1-\frac{k+1}{q}+\frac{r}{q} \right) \le \pi \left( 1+\frac{r}{q} \right)$$ (6.46)

そして、$r/q\ll 1$なので結局 $\vert\alpha_k\theta \vert\le \pi$となり、式6.45右辺の最大値は $-\pi\le\alpha_k\theta\le\pi$の範囲で探せば良い。 $1-\cos(\alpha_k\theta)/(\alpha_k\theta)^2$の最大値は、 $\vert\alpha_k\theta \vert=\pi$のとき、

$$\left.\frac{1-\cos(\alpha_k\theta )}{(\alpha_k\theta )^2}\right\vert _{\alpha_k\theta =\pm\pi}=\frac{2}{\pi^2}$$ (6.47)

であり、式6.45の$\alpha_k$については、$k \le r-1$より

$$\alpha_k = \lfloor \frac{q-k-1}{r} \rfloor +1 \ge \lfloor \frac{q-r}{r} \rfloor +1$$ (6.48)

$$= \frac{q-r}{r}-1+1=\frac{q}{r}-1 \cong -1$$ (6.49)

なので、結局、式6.45は上の二つの式から

$$P(x) \ge \sum_{k=0}^{r-1}\frac{4}{\pi^2 q^2}\left(\frac{q}{r}-1\right)^2 \cong \frac{4}{\pi r}$$ (6.50)

と下から抑えられる。 したがって、$x \in C$のどれかを得る確率は

$$P_r=\sum_{x\in C}P(x) \le \sum_{x\in C}\frac{4}{\pi^2r}$$ (6.51)

となり、$C$に属すから$x$は6.23を満たすので

$$\left\vert \frac{d}{r}-\frac{x}{q}\right\vert \le \frac{q}{2}$$ (6.52)

つまり、

$$\frac{qd}{r}-\frac{1}{2} \le x \le \frac{qd}{r}+\frac{1}{2}$$ (6.53)

なので、ある一つの $d\in\{\{ 1,2\cdots r-1\}\vert\gcd (r,d)=1\}$に対して、少なくとも一つの$x$が存在する。このような条件を満たす$d$の個数は$r$のオイラー関数$\phi (r)$であり、その値については次の定理が知られている。

定理 6.5   オイラー関数の評価式

$$\liminf_{r \to \infty} \left(\frac{\phi (r)\log\log r}{r}\right) = e^{-\gamma}$$ (6.54)

ただし、ここで $\gamma \cong 0.5771$はオイラー定数である。

したがって、

$$\phi (r) \ge e^{-\gamma } \frac{r}{\log\log r} \ge e{-\gamma } \frac{r}{\log r} \ge e^{-\gamma } \frac{r}{\log N}$$ (6.55)

が成り立ち、式6.52は、

$$P_r \ge \frac{4e^{\gamma}}{\pi^2}\frac{1}{\log N}$$ (6.56)

と評価できる。したがってここで言えることは $\hat{U}\lvert 0,0 \rangle$の演算と$x$の観測を$O(\log N)$回以上行えば式6.23(古典計算への入力に対する条件)を満たす$c$を得ることが出来るということである。よって、この一連の位数を求めるアルゴリズムを$O(\log N)$回以上繰り返せば正しい位数$r$が一回は出力される計算になる。だがこの議論では重要なことがまだ一つ抜けている、つまりこのアルゴリズムを一回繰り返すのにどれだけの計算時間がかかるのかはまだ議論していなかった。このアルゴリズムにおいて多項式時間で計算できることが不明な個所は、量子計算で指数関数を求めるところ(つまり $\hat{U}_{a,N}$)のみであるが、 $\hat{U}_{a,N}$が多項式オーダーのステップで組み立てられることは付録Cに示してある。