まずユークリッドの互除法、すなわち二つの整数の最大公約数を求めるアルゴリズムが非常に効率の良い方法であることを確認しておく：ユークリッドの互除法とは、与えられた正整数 $a, b$ （$a > b$）に対し以下の計算を実行し $r_j$ を求めることである。
\begin{eqnarray*} a&=&bq_1+r_1 \hskip 2mm (0 < r_1 < b)\\ b&=&r_1q_2+r_2 \hskip 2mm (0 < r_2 < r_1)\\ r_1&=&r_2q_3+r_3 \hskip 2mm (0 < r_3 < r_2)\\ &\vdots & \\ r_{j-2}&=&r_{j-1}q_j+r_j \hskip 2mm (0 < r_j < r_{j-1})\\ r_{j-1}&=&r_jq_{j+1} \end{eqnarray*}この $r_j$ が $a, b$ の最大公約数である。
ここで第一列を見ると $$a-r_1\geq b>r_1$$
である。よって
$$r_1<{a\over 2}$$となる。つまり、余りは割られる数の半分より小さい。この事柄は何行目の計算においても正しく、従って余りの大きさは $1/2$ のベキ乗の速さで急激に小さくなる。よって、最大公約数 $r_j$ を求める手続きは、$a, b$ が非常に大きな数であったとしても少ない手数でできる。
さて、正整数 $N$ の因数を求めたいとする。以下では $N=15$ の場合を例として説明する。簡単すぎる例かもしれないが、アルゴリズムの本質的な部分を明らかにしたいだけなので、例は簡単な方がよい。因みに、実際の量子コンピューターが最初に成功したのが、2001 年のことだが、$15=5\times 3$ の因数分解だった。
アルゴリズムの流れは以下の通り：
(I) $N$ と互いに素で、かつ $0 < m < N$ である整数 $m$ を適当に選ぶ。$N$ が大きい場合でもこのような $m$ を見つけることはたやすい。例えば $m=2$ は $N=15$ に対し条件を満たす。
(II) $m^a$ を $N$ で割って余りが $1$ になる、つまり
$$m^a\equiv 1 \hskip 2mm {\rm {mod}} N$$である正整数 $a$ の内、最小のものを $r$ で表す。任意の $a$ に対し
$$m^{a+r}\equiv m^a \hskip 2mm {\rm {mod}} N$$であり、この意味で $r$ は「周期」と呼ばれる。$N=15$ で $m=2$ の場合、$N$ を法として
$$2^1=2, \hskip 2mm 2^2=4, \hskip 2mm 2^3=8, \hskip 2mm 2^4=16\equiv 1$$だから、$r=4$ である。（$N$ が大きい場合、この $r$ を探す計算がやっかいなものになるだろうことは、実際に鉛筆を動かしてみれば予測できる。）もしこうして求めた $r$ が奇数であれば、運が悪かったとあきらめて、もう一度 $m$ を取り直し、偶数の $r$ が求まるまで繰り返す。
(III) 偶数の $r$ が求まれば
$$m^r-1=(m^{r/2}+1)(m^{r/2}-1)$$は $N$ で割り切れることになり、
$$m^{r/2}-1, \hskip 2mm m^{r/2}+1$$の少なくとも一方は $N$ と $1$ 以外の公約数を持つ。最大公約数はユークリッドの互除法により効率よく求めることができるから、これで $N$ の約数が求まる。
$N=15$ で $m=2$ であれば $r=4$ であり
$$2^2+1, \hskip 2mm 2^2-1$$の少なくとも一方は $N=15$ との間で $1$ 以外の公約数を持つはず。前者が $5$、後者が $3$ であり確かにこの条件を満たす。
ただ、この方法でまれに
$$m^{r/2}+1, \hskip 2mm m^{r/2}-1$$と $N$ との最大公約数を求めても、$N$ の自明でない約数が得られない場合が生じる。例えば $N=15$ に対し $m=14$ を選んでしまうと、$r=2$ であり
$$14+1=15, \hskip 2mm 14-1=13$$と $N=15$ との最大公約数を求めても役に立たない。そういう場合は、改めて $m$ を取り直し計算し直す。
従って問題は、周期 $r$ を求める計算だが、$m^a\equiv 1$ となる $a$ を、もし $a=1$ からしらみ潰しに調べていくとすると、おおよそ $N/2$ 個程度の $a$ について計算する必要が生じる。従って $N$ を十進法で表す時、桁数が $1$ 増すごとに計算量は $10$ 倍程度増加する。つまり桁数に関して指数関数的に計算量が増加し、実質的には計算不能な状況が生じる。ショアは量子力学的現象を用いてこの問題を解決する方法を見出した。
その方法を見る前に、少し復習が必要：光子の偏極の状態には二通りあり（例えば水平と垂直）、それぞれ $0$ と $1$ を表すと考えることができる。光子に限らず、他にも二つの状態を取り得る物理的な対象が幾つか存在する。そのような対象を二つ用意すれば、それぞれが $0, 1$ に対応する状態を取り得るから
$$00, \hskip 2mm 01, \hskip 2mm 10, \hskip 2mm 11$$の四つに対応する状態を取り得ることになる。一方、上で書いた $0, 1$ の組は、整数の二進数表示とみなすことができる。よって、そのような対象の組は
$$0, \hskip 2mm 1, \hskip 2mm 2, \hskip 2mm 3$$に対応する四つの状態を取り得ると言ってよい。この方法は容易に一般化できる。つまり二つの状態を取り得る対象の $n$ 個からなる体系（これ以降、$S$ で表す）は、
$$0, \hskip 2mm 1, \hskip 2mm 2, \cdots , \hskip 2mm 2^n-1$$に対応する $2^n$ 個の状態を取り得る。
以下では $A=2^n$ と置き、$0\leq a\leq A-1$ の $a$ に対応する $S$ の状態を $(a)$ で表す。$m^a$ を $N$ で割って余りを計算するので、$A=2^n>N$ 程に $n$ は大きく取る必要がある。つまり、大きな $N$ に対しては $n$ も大きく取らねばならない。
ここで思い出すべき重要なことは、例えば光子の場合、水平方向に偏極した状態と垂直方向に偏極した状態の和が、別の状態として存在したことである。ミクロな世界で普通に見られる顕著な現象であり、今考えている系 $S$ についても、
\begin{equation} (0)+(1)+\cdots +(a)+\cdots +(A-1) \label{eq:012A-1} \end{equation}で表される状態が存在し得る。この状態は、「$S$ が、$A$ 個の状態 $(a)$ のそれぞれに、同時にいる状態」と考えられる。$a$ それぞれについて $m^a$ の余りを個別に計算するのではなく、すべての $a$ について同時に並列的に計算する方法を、この状態を利用することによってショアは見出したと言える。
まず、$S$ と同じような系 $R$ を用意し、その状態を
$$(0), \hskip 2mm (1), \hskip 2mm \cdots , \hskip 2mm (b), \hskip 2mm \cdots $$で表す。$m^a$ を $N$ で割った余りを記録するための状態なので、これらの個数は $N$ 以上であるとする。$S$ の状態と $R$ の状態を $\otimes $ で結んで $S$ と $R$ 全体の状態を表すことにする。例えば $S$ が $(a)$ の状態にあり、$R$ が $(b)$ の状態にあることを $(a)\otimes (b)$ で表すという具合。
第一段階として
\begin{eqnarray*} &&\left[ (0)+\cdots +(a)+\cdots +(A-1)\right] \otimes (0)\\ &&=(0)\otimes (0)+\cdots +(a)\otimes (0)+\cdots +(A-1)\otimes (0) \end{eqnarray*}の状態にある $S$ と $R$ にある操作を施し
\begin{equation} (0)\otimes (m^0 {\rm {mod}} N)+\cdots +(a)\otimes (m^a {\rm {mod}} N)+\cdots +(A-1)\otimes (m^{A-1} {\rm {mod}} N) \label{eq:0timesm0} \end{equation}の状態へ変える。但し
$$m^a {\rm {mod}} N$$は $m^a$ を $N$ で割った余りを表す。
状態を変化させるこの操作は、実際には幾つかのゲートを $S$ と $R$ に通過させることによってなされる（簡単な操作なのだが、説明しようとすると少しごたごたする。ショアの方法の本質的部分と言えることは確かであり、本当は説明しなくてはいけない）。ここで肝心な点は、必要なゲートの個数が、$n$ が増加すればもちろん増加するのだが、$n$ の指数関数的な増加ではなく $n$ の多項式的な増加にとどまる点である。例えば $n^2$ の程度の増加であるとしてこの違いを比べてみる：仮に $N=10^{10}$ 程度の $N$ を扱うとすると、$A=2^n>N$ が必要だから、$2^n>10^{10}$、つまり $n>30$ 程に $n$ を大きく取らねばならない。この時 $2^n$ は百億のオーダーだが、$n^2$ は千のオーダーである。
第二段階として、$R$ の状態を検出する装置に $R$ を通す。すると、何らかの余り $b_0$ に対応する状態 $(b_0)$ に $R$ は転移する。この時 $S$ の状態は
\begin{equation} {1\over {\sqrt {k_0+1}}}\left[ (a_0)+(a_0+r)+(a_0+2r)+\cdots +(a_0+k_0r)\right] \label{eq:a0+a0r} \end{equation}の状態に転移する。但し、ここに現れる $a_0+kr$ は、$m^a$ を $N$ で割った時の余りが $b_0$ となるすべての $a$ を、大きさの順に列挙したものである。$k_0$ は
$$a_0+kr\leq A-1$$である $k$ の最大値である。各状態 $(a)$ の大きさ（長さ）は $1$ であり、お互い直交するので、先頭に付けた因子 $1/{\sqrt {k_0+1}}$ は全体の大きさを $1$ にするためである。
$N=15$、$m=2$ を例として、ここまでの段階を復習してみる：$n=4$ とすれば、必要な条件
$$A=2^n=16>N$$は満たされる。 先に計算したが、$N=15$ を法として
$$2^1=2, \hskip 2mm 2^2=4, \hskip 2mm 2^3=8, \hskip 2mm 2^4=16\equiv 1$$なので、$m^a$ を $N$ で割る時の余りは
$$1, \hskip 2mm 2, \hskip 2mm 4, \hskip 2mm 8$$の四つであり、よって (\ref{eq:0timesm0}) 式は
\begin{eqnarray*} &&(0)\otimes (2^0 {\rm {mod}} 15)+\cdots +(a)\otimes (2^a {\rm {mod}} 15)+\cdots +(15)\otimes (2^{15} {\rm {mod}} 15) \\ &&=\Bigl[ (0)+(4)+(8)+(12)\Bigr]\otimes (1)+\Bigl[ (1)+(5)+(9)+(13)\Bigr]\otimes (2)\\ &&+\Bigl[ (2)+(6)+(10)+(14)\Bigr]\otimes (4)+\Bigl[ (3)+(7)+(11)+(15)\Bigr]\otimes (8) \end{eqnarray*}となる。
ここで $R$ の状態を検出する装置に $R$ を通すと、
$$(1), \hskip 2mm (2), \hskip 2mm (4), \hskip 2mm (8)$$のどれかに $R$ は転移する。仮に $(1)$ の状態に転移したとすれば、その時 $S$ の状態は
$${1\over 2}\left[ (0)+(4)+(8)+(12)\right] $$であり、$(2)$ の状態に転移したとすれば $S$ は
$${1\over 2}\left[ (1)+(5)+(9)+(13)\right] $$の状態になる。今考えている例では、周期は $r=4$ だが、これを周期とする状態が $S$ の状態として現れている。
これをうまく利用して $r$ の値を実際に見出すことが、残された問題である。
目次を表示