復習を少し：任意の整数 $N$ の因数を求めるためのショアのアルゴリズムの紹介の途中だった。$m$ を $N$ と互いに素で
$$1 < m < N$$である整数とし、
$$m^a\equiv 1\hskip 2mm {\rm {mod}} N$$である整数 $a$ の内最小のものを $r$ と置く。$r$ は周期と呼ばれ、任意の $a$ について
$$m^{a+r}\equiv m^a \hskip 2mm {\rm {mod}} N$$である。$r$ を求めることができれば、しかもそれが偶数であれば、$N$ の因数がわかる。
光子の偏光状態のように、二つの状態をもつミクロな対象物の $n$ 個からなる体系（$S$ と呼んだ）は、
$$(0), \hskip 2mm (1), \cdots , \hskip 2mm (a), \cdots , \hskip 2mm (A-1)$$だけの状態を持つことになる。但し
$$A=2^n$$と置いた。
ここで、ミクロ世界の特徴をうまく使うと、系 $S$ に
\begin{equation} {1\over {\sqrt{k_0+1}}}\Bigl[ (a_0)+(a_0+r)+(a_0+2r)+\cdots +(a_0+k_0r)\Bigr] \label{eq:kurikase2}\end{equation}の状態を取らせることができる。但し、ここに現れる $a_0+kr$ は、$m^a$ を $N$ で割った余りが一定値となるすべての $a$ を、大きさの順に列挙したものである。$k_0$ は
$$a_0+kr\leq A-1$$となる $k$ の最大値であり、先頭の因子 $1/{\sqrt {k_0+1}}$ は全体の大きさを $1$ にするためである。この状態を利用して $r$ の値を求めるのが今回の目標である。
例えば、
$$N=15、\hskip 2mm m=2$$の場合、$r=4$ だが、$2^a$ を $15$ で割る時の余りは
$$1, \hskip 2mm 2, \hskip 2mm 4, \hskip 2mm 8$$だけであり、$A=16$ とすると (\ref{eq:kurikase2}) 式としては
$${1\over 2}\left[ (0)+(4)+(8)+(12)\right] $$や
$${1\over 2}\left[ (1)+(5)+(9)+(13)\right] $$等が現れる。
余計な複雑さは避けたいので、$a_0=0$ の場合を考える。一般の $a_0$ に拡張することはたやすい。誰でも、$S$ の状態を検出する装置に $S$ を通すことを考えると思うが
$${1\over {\sqrt {k_0+1}}}\Bigl[ (0)+(r)+(2r)+\cdots +(k_0r)\Bigr] $$の状態の $S$ をそのような検出器に通すと
$$(0), \hskip 2mm (r), \hskip 2mm (2r), \hskip 2mm \cdots , \hskip 2mm (k_0r)$$のどれかに均等の確率で転移する。もし、$(r)$ に特に高い確率で転移するのであれば、$r$ の値を高い確率で推測できるが、そうではない。そこで少し工夫を要する。
$S$ の各状態 $(a)$ を
$${1\over {\sqrt A}}\sum _{c=0}^{A-1}e^{2\pi iac/A}(c)$$に変える操作を $U$ で表す。$S$ に $U$ を施してそのような変化を起こさせることは、実際にはいくつかのゲートを $S$ にくぐらせることによって実行できる。大事な点は、$n$ の増加と共にゲートの個数は増えるが、指数関数の勢いで増えるのではなく $n^2$ のオーダーにとどまる点である。
操作 $U$ を $S$ に施すと、状態
$${1\over {\sqrt {k_0+1}}}\left[ (0)+(r)+(2r)+\cdots +(k_0r)\right] $$は、状態
\begin{equation} {1\over {\sqrt {A(k_0+1)}}}\sum _{c=0}^{A-1}\Bigl[ 1+e^{2\pi irc/A}+e^{2\pi i2rc/A}+\cdots +e^{2\pi ik_0rc/A}\Bigr] (c)\label{eq:tennisurusaki} \end{equation}に変わる。ここで大括弧の中身は公比が
\begin{equation} e^{2\pi irc/A} \label{eq:e2kouhi} \end{equation}の等比級数である。従ってこの公比が $1$ でない $c$ に対しては
\begin{equation} 大括弧={{1-e^{2\pi i(k_0+1)rc/A}}\over {1-e^{2\pi irc/A}}} \label{eq:kakkonokakami} \end{equation}に等しい。
数式がごたごたしてきたので、簡単な場合として
$$(k_0+1)r=A$$が成り立つ場合を特に考えてみる。つまり、$A$ がたまたま周期 $r$ の整数倍に一致する場合である。この場合 (\ref{eq:kakkonokakami}) 式の分子は $0$ になる（$c$ は整数！）。一方で公比 (\ref{eq:e2kouhi}) が $1$ であるのは
$${{rc}\over A}=l (整数)$$なる $c$ に対してである。このような整数は
$$l=0, \hskip 2mm 1, \hskip 2mm 2, \hskip 2mm \cdots , \hskip 2mm r-1$$に限られる。以上を総合すると
$$(\ref{eq:tennisurusaki})={1\over {\sqrt r}}\sum _{l=0}^{r-1}(Al/r)$$となる。ここで状態 $(a)$ のどれかに転移させる検出器に $S$ を通すと
$$(Al/r)$$の状態に転移する。$A$ は最初に設定した値でありよくわかっているから、従って
$${l\over r} \hskip 2mm (l=0, 1, \cdots , r-1)$$のどれかの値が得られることになる。
得られた数 $x$ を既約分数 $q/p$ で表し、$p$ によって $r$ を推定する方法を取る。既約分数による表示は一意的だから、もし $l/r$ が既約分数であるなら $p=r$ となる。従ってこの推定法にとって、$l/r$ が既約分数である、つまり $r$ と $l$ が互いに素である確率が問題だが、それが $1/\log(\log r)$ の程度以上であることが知られている（オイラーの関数 $\phi (r)$ に対し、$\phi (r)/r$ を評価して得られる）。この確率は $r$ が非常に大きくてもかなり大きい。例えば十進法で $1000$ 桁の数であっても $1/8$ 程度である。よって $8$ 回程度試行すれば正しい $r$ が得られる。この意味で $r$ を推定するこの方法はかなり効率的な方法だと言える。
正しい $r$ が得られたかどうかはもちろん
$$m^{r/2}+1, \hskip 2mm m^{r/2}-1$$と $N$ との最大公約数を求め、実際に $N$ の因数が得られるかどうかで確認する。
$A$ がたまたま周期 $r$ の整数倍に一致する場合は以上で $r$ が推定できるが、そうでない場合は
\begin{eqnarray} (\ref{eq:tennisurusaki})&=&{1\over {\sqrt{A(k_0+1)}}}\sum _{rc/A\not= 整数}{{1-e^{2\pi i(k_0+1)rc/A}}\over {1-e^{2\pi irc/A}}}(c) \nonumber \\ &&+{\sqrt{{k_0+1}\over A}}\sum _{rc/A=整数}(c) \label{eq:tenisuru2} \end{eqnarray}であって、第一項が残る。
検出器に $S$ を通す時、(\ref{eq:tenisuru2}) の第二項に含まれる $(c)$ に転移する確率はすべて等しく
\begin{equation} {{k_0+1}\over A}={{k_0+1}\over {2^n}} \label{eq:proba2} \end{equation}である。また $r$ から $2$ のベキの最大個数（$s$ とする）を取り出して
$$r=2^sr'$$と置く（先に見た $A=2^n$ が $r$ の整数倍の時とは $r'=1$ の時である）。この時、第二項に含まれる $(c)$ の個数は $2^s$ であり、よって第一項に含まれる $(c)$ の個数は
$$A-2^s=2^n-2^s$$に等しい。
第二項に含まれる $(c)$ のいずれかに転移する確率は、
$$k_0r\leq A-1<(k_0+1)r$$に注意するならば
\begin{equation} {{k_0+1}\over {2^n}}\times 2^s>{{2^n-1}\over {2^nr'}}\approx {1\over {r'}} \label{eq:2koukakuwa} \end{equation}だとわかる。よって第一項に含まれる $(c)$ に転移する確率は平均して
\begin{equation} {{1-(1/r')}\over {2^n-2^s}} \label{eq:prob1} \end{equation}以下である。
第二項に含まれる $(c)$ の一つに転移する確率 (\ref{eq:proba2}) に対する、第一項に含まれる $(c)$ の一つに転移する確率 (\ref{eq:prob1}) の比を計算すると $r/2^n$ 以下であることがわかる。この値は一般に $1$ に比して十分小さいはずであり、第二項に含まれる $c$ を観測する確率の方が高いことになる。
従って、高い確率で
$$c={A\over r}l$$の形の $c$ を観測する（私はこの結論には違和感を覚える。後の注意を参照）。但し
$$l=0, \hskip 2mm r', \hskip 2mm 2r', \cdots , \hskip 2mm (2^s-1)r'$$である。よって、先に見た「$A$ が $r$ の整数倍」の時と同じ方法によって、$r$ を推定することができる。
注意：量子コンピューターを扱っている教科書で得た知識をもとに以上説明してきたが、どうも腑に落ちないことがあるので、私の勘違いかもしれないが敢えて書いておく：(\ref{eq:tenisuru2}) の状態にある $S$ を検出器に通す時、第一項に含まれる $(c)$ の一つに転移する確率と、第二項に含まれる $(c)$ の一つに転移する確率を比べると、後者が前者より確かに大きい。しかしだからと言って、『従って、高い確率で
$$c={A\over r}l$$の形の $c$ を観測する』とは言えないように思う。
そのように言えるためには、第二項に含まれる $(c)$ のいずれかに（一つに、ではない！）転移する確率が、第一項に含まれる $(c)$ のいずれかに（一つに、ではない）転移する確率と比べて大きくなければならない、と私は思う。
(\ref{eq:2koukakuwa}) で見たように、第二項のいずれかに転移する確率は $1/r'$ の程度。従って第一項のいずれかに転移する確率は $1-(1/r')$ の程度である。ここで $r'$ は
$$r=2^sr'$$に現れる $r'$ である。よって、$2^s$ が小さく、$r'$ がかなり大きい場合があり得る。その場合、$1/r'$ は $0$ に近く、$1-(1/r')$ は $1$ に近くなる。つまり、第二項を構成する $(c)$ の個数($=2^s$)が少数で、第一項を構成する $(c)$ の個数（$=2^n-2^s$）が非常に多数の場合、
$$(小さな確率)\times (多数) > (大きな確率)\times (少数)$$が生じ得る。
この状況では、$S$ を測定機に通しても、ほとんどの場合、第一項に属する $(c)$ に転移する。そのような $c$ は $Al/r$ の形をしていないので、そこから $r$ が推定できる論理的根拠はない。
かなり深刻な疑問であるように思うのだが、少なくとも私の手元にある教科書には何の記述もない。私の勘違いかもしれない。
目次を表示