連分数で分母を読む

相対エントロピーから情報と物理を組み立てる　第6部 第3章 §6.3.3　★★ $2^t\ge N^2$ に取れば、最も近い $m$ から $s/r$ が連分数の近似分数として一意に読める

どれだけの精度が要るか

位相推定で得た $m$ は、$m/2^t$ が $s/r$ の近似になっている。欲しいのは小数でなく分母 $r$ そのものである。$r<N$ なので、候補は分母が $N$ 未満の分数に限られる。分母が $N$ 以下の異なる2つの分数 $p/q$、$p'/q'$ は

$$\Bigl|\frac pq-\frac{p'}{q'}\Bigr|=\frac{\lvert pq'-p'q\rvert }{qq'}\ge\frac1{qq'}\ge\frac1{N^2}$$

だけ離れている。したがって $m/2^t$ が $s/r$ から $1/(2N^2)$ より近ければ、その範囲に分母 $N$ 以下の分数は $s/r$ 1つしかない。最も近い $m$ を得たときの誤差は $\lvert m/2^t-s/r\rvert \le1/2^{t+1}$ なので、

$$2^t\ge N^2,\qquad\text{すなわち}\quad t=\lceil2\log_2N\rceil\approx2n\tag{6.3.9}$$

に取れば、$s/r$ は $m/2^t$ から一意に決まる。位相推定の精度の要求が、第1のレジスタの量子ビットの数を桁数のほぼ2倍に決めている。

連分数と Legendre の定理

一意に決まることと、それを速く見つけることは別の問題である。有理数 $x$ を

$$x=c_0+\cfrac{1}{c_1+\cfrac{1}{c_2+\cfrac{1}{\ddots+\cfrac1{c_L}}}}\eqqcolon[c_0;c_1,c_2,\dots,c_L]$$

と書くのが連分数展開である。整数部分 $c_0$ を取り、残りの逆数の整数部分を $c_1$ とし、と繰り返す操作は Euclid の互除法と同じで、$\mathcal{O}(\log)$ 回で終わる。途中で打ち切った $[c_0;c_1,\dots,c_j]$ を近似分数と呼ぶ。近似分数 $h_j/k_j$ は漸化式 $h_j=c_jh_{j-1}+h_{j-2}$、$k_j=c_jk_{j-1}+k_{j-2}$（$h_{-1}=1$、$h_{-2}=0$、$k_{-1}=0$、$k_{-2}=1$）で順に求まる。

$2^t\ge N^2$ のとき、最も近い $m$ について $\lvert m/2^t-s/r\rvert \le1/2^{t+1}\le1/(2N^2)<1/(2r^2)$ が成り立つ。$s/r$ を既約分数に直した $s'/r'$（$r'$ は $r$ の約数）も $1/(2r'^2)\ge1/(2r^2)$ なので同じ条件を満たし、Legendre の定理から近似分数の中に現れる。手続きは次のとおりである。$m/2^t$ の近似分数を分母の小さい順に求め、分母 $q<N$ のそれぞれについて $a^q\equiv1\pmod N$ かを古典の計算で確かめる。最初に成り立った $q$ が位数の候補である。

$s$ と $r$ が共通の約数を持つとき

近似分数から得られるのは既約分数 $s'/r'$ で、$\gcd(s,r)=g>1$ なら $r'=r/g$ は位数の真の約数になり、$a^{r'}\not\equiv1$ で候補から外れる。そのときは実行をもう1回して別の $s_2$ から $r_2'$ を得て、$\operatorname{lcm}(r',r_2')$ を候補にする。$s$、$s_2$ は独立に一様なので、$\operatorname{lcm}(r',r_2')=r$ となるのは $s$、$s_2$、$r$ の3つに共通の素因数が無いときで、その確率は

$$\prod_{p\,|\,r}\Bigl(1-\frac1{p^2}\Bigr)\ \ge\ \prod_{p}\Bigl(1-\frac1{p^2}\Bigr)=\frac{6}{\pi^2}\approx0.608\tag{6.3.10}$$

である（積は素数 $p$ について取る。右の等式は Euler の積公式 $\prod_p(1-p^{-2})^{-1}=\sum_{k\ge1}k^{-2}=\pi^2/6$）。$r=6$ なら $(1-\frac14)(1-\frac19)=\frac23$ である。2回の実行と最小公倍数で、$r$ によらない定数の確率で位数が得られる。