成功確率と回路の大きさ

相対エントロピーから情報と物理を組み立てる　第6部 第3章 §6.3.4　★★ 1回の実行は定数の確率で成功し、手間は $\mathcal{O}(n^3)$。古典の最良の方法は $n^{1/3}$ の指数で増える

最も近い $m$ が出る確率

前の節の手続きが働くのは、測定値が $2^ts/r$ に最も近い整数のときである。その確率は式 (6.3.7) で $\lvert \delta\rvert \le1/2^{t+1}$ の値で、$\sin(\pi\delta)\le\pi\delta$ と、$0\le y\le\pi/2$ での $\sin y\ge2y/\pi$ を使うと

$$F_t(\delta)\ \ge\ \frac{\sin^2(\pi2^t\delta)}{(\pi2^t\delta)^2}\ \ge\ \Bigl(\frac{2}{\pi}\Bigr)^2=\frac4{\pi^2}\approx0.405\tag{6.3.11}$$

で下から押さえられる。$s$ がどの値でも、最も近い $m$ は $0.405$ 以上の確率で出る。$N=21$、$t=9$ では、$2^ts/r$ が整数でない $s=1,2,4,5$ のそれぞれについて最も近い $m$ の条件付き確率が $0.684$ で、下界より大きい。6つの山のどれかの最も近い $m$ が出る確率は $0.789$ である。

そのうえで $\gcd(s,r)=1$ なら1回で $r$ が読める。$N=21$ では、近似分数の分母を順に試す手続きで1回の実行から $r=6$ がそのまま読める確率が $0.328$ になる（山の両隣の $m$ から読める場合も含む）。読めなかった実行の結果も、式 (6.3.10) の最小公倍数で使える。いずれにせよ、成功の確率が $r$ や $N$ の大きさに比べて小さくならないことが重要で、数回の実行で失敗の確率は指数的に小さくなる。

回路の大きさ

手間を桁数 $n$ で数える。第1のレジスタは $t\approx2n$ 量子ビット、第2のレジスタは $n$ 量子ビットである。支配的なのは制御した掛け算 $U_{a^{2^j}}$ を $t$ 回当てる部分で、$n$ ビットの数どうしの掛け算と剰余を筆算の方法で組めば1回 $\mathcal{O}(n^2)$ 個のゲートなので、全体で $\mathcal{O}(n^3)$ になる。逆量子 Fourier 変換は $\mathcal{O}(t^2)=\mathcal{O}(n^2)$ 個のゲートで（第6部第2章）、連分数と最大公約数の古典の後処理も $\mathcal{O}(n^3)$ である。量子ビットの数は工夫で減らせて、第1のレジスタを1個の量子ビットの使い回しに置き換えると、全体で $2n+3$ 個で組める¹1S. Beauregard (2003), Quantum Inf. Comput. 3, 175。下の脚注へ閉じる。

古典の側で知られている最良の方法は数体ふるい法で、手間の目安（発見的な評価で、補正の $o(1)$ を落としたもの）は

$$L_N=\exp\Bigl[\Bigl(\frac{64}{9}\Bigr)^{1/3}(\ln N)^{1/3}(\ln\ln N)^{2/3}\Bigr]\tag{6.3.12}$$

である。$n$ の多項式より速く、$2^n$ より遅く増える。図 6.3.3 が $n^3$ と $L_N$ の桁の比較で、$n=2048$ では $n^3\approx8.6\times10^9$ に対し $L_N\approx10^{35}$ である。定数倍を無視した比較なので、実際の時間の比ではない。比べられるのは $n$ を増やしたときの増え方である。

図 6.3.3　因数分解の手間の目安。Shor のアルゴリズムのゲートの数の増え方 $n^3$ と、数体ふるい法の式 (6.3.12)（$o(1)$ を落とした目安）を、桁数 $n$ について比べた。どちらも定数倍を無視している。

RSA の 2048 ビットに要る資源の見積もり

$\mathcal{O}(n^3)$ は論理ゲートの数で、実際の量子コンピュータは誤りを含む。誤りを抑える符号化（第3部第9章、表面符号は 第6部第5章）の手間を込めると、物理的な量子ビットの数は論理量子ビットの数の何桁も上になる。Gidney と Ekerå は、物理的なゲートの誤り率を $10^{-3}$、表面符号で誤りを抑えると仮定して、2048 ビットの RSA の数を約 2000 万個の物理的な量子ビットで約8時間で因数分解できると見積もった²2C. Gidney and M. Ekerå (2021), Quantum 5, 433。下の脚注へ閉じる。Gidney はその後、誤り率 $0.1\%$、表面符号の1周期 $1\,\mu\mathrm s$、制御系の反応時間 $10\,\mu\mathrm s$ という同様の仮定のもとで、物理的な量子ビット 100 万個未満・1週間未満という見積もりを出した³3C. Gidney (2025), arXiv:2505.15917。下の脚注へ閉じる。どちらも実際の装置の性能でなく、仮定した性能のもとでの見積もりである。実験で Shor のアルゴリズムを走らせた最初の例は、核磁気共鳴の7量子ビットで $15=3\times5$ を分解したものである⁴4L. M. K. Vandersypen et al. (2001), Nature 414, 883。下の脚注へ閉じる。