第6章Shorのアルゴリズム — 概要を追う
この章の目標
- 「素因数分解 → 位数（周期）発見 → 位相推定」という還元の流れを追えるようになる
- $N = 15$ で全工程を電卓レベルの手計算でなぞる
- 量子が担う部分と古典が担う部分を正確に切り分けられるようになる
- 「RSAはいつ壊れるか」という問いに、資源見積もりを踏まえて答えられるようになる
step.mdの方針どおり、このアルゴリズムは「位相推定の応用として概要が追えれば十分」です。数論の証明（還元がなぜ高確率で成功するか等）は事実として受け入れて進みます。
6.1 全体の流れ — 量子が働くのは1箇所だけ
合成数 $N$（例: RSAの公開鍵）を素因数分解したい。Shorのアルゴリズムの構造は、ほとんどが古典の前処理・後処理です：
| 工程 | 内容 | 担当 |
|---|---|---|
| 1 | $N$ と互いに素な $a$ をランダムに選ぶ | 古典 |
| 2 | $a$ の位数 $r$（$a^r \equiv 1 \pmod N$ となる最小の $r$）を求める | 量子（ここだけ！） |
| 3 | $r$ が偶数で $a^{r/2} \not\equiv -1 \pmod N$ なら、$\gcd(a^{r/2} \pm 1, N)$ が非自明な因数（数論の定理）。だめなら $a$ を選び直して1へ | 古典 |
$7^x \bmod 15$ を並べる：$7, 4, 13, \mathbf{1}, 7, 4, 13, 1, \dots$ → 位数 $r = 4$（周期4で1に戻る）。$r$ は偶数、$7^{r/2} = 7^2 = 49 \equiv 4 \not\equiv -1$。よって $$\gcd(4 - 1, 15) = \gcd(3, 15) = 3, \qquad \gcd(4 + 1, 15) = \gcd(5, 15) = 5$$ $15 = 3 \times 5$ ——分解成功。素因数分解が「数列 $a^x \bmod N$ の周期を見つける問題」に化けました。そして周期の抽出なら、私たちはもう道具を持っています（第4・5章）。
6.2 位数発見を位相推定に載せる
ユニタリ $U$ を「$a$ を掛ける操作」として定義します： $$U|y\rangle = |a y \bmod N\rangle$$ （$y$ は $N$ 未満の整数を基底状態として読む。可逆＝ユニタリなのは $a$ に逆元があるから）。このとき数論的な計算により：
$U$ の固有値は $e^{2\pi i s/r}$（$s = 0, 1, \dots, r-1$）であり、対応する固有状態 $|u_s\rangle$ たちの一様重ね合わせはちょうど $$\frac{1}{\sqrt r}\sum_{s=0}^{r-1}|u_s\rangle = |1\rangle$$ という作るのが一番簡単な状態になる。
これで第5章の部品がすべて噛み合います：
- 固有状態レジスタに $|1\rangle$ を入れる——これは固有状態の一様重ね合わせ（問5-5の状況）。
- 位相推定を実行——ランダムな $s$ について $\varphi = \frac{s}{r}$ が読める。
- 測定値（2進小数）から分数 $\frac{s}{r}$ を復元（連分数展開という古典アルゴリズム。「0.749878… に最も近い、分母が小さい分数は $\frac34$」を機械的に見つける道具と思えばOK）。分母が $r$ の候補。$s$ と $r$ が公約数を持つ場合は失敗するが、数回繰り返せば高確率で真の $r$ が得られる。
残る要件は問5-6(a)の「制御$U^{2^j}$ が効率よく作れるか」。ここで効くのが繰り返し二乗法です：$U^{2^j}$ は「$a^{2^j} \bmod N$ を掛ける操作」であり、$a^{2^j} \bmod N$ 自体は古典で $j$ 回の二乗で先に計算しておけます。あとはその数を掛けるモジュラー乗算回路（ステップ2第6章の可逆算術！）を組むだけ——$2^j$ 回のゲート適用が $j$ 回の二乗で済む「近道」がある。これがこの問題が位相推定に載る最後の鍵です。
古典で位数 $r$ を見つけるには、知られている最良の方法でも $N$ の桁数に対して準指数的な時間がかかります（これがRSAの安全性の根拠）。量子側は、(1) $|1\rangle$ を用意して、(2) モジュラー累乗（多項式ゲート）＋逆QFT（$O(n^2)$）を1回流し、(3) 連分数（古典・多項式）——全体が桁数の多項式時間。重ね合わせの中で $a^x$ の全値が「計算」され、その周期だけがQFTで抽出される。個々の値は誰も読んでいない——第0章の「大域的性質だけが取り出せる」の最高の実例です。
実機でのShor実行の記録は $N = 15, 21$ 級の玩具例にとどまります（しかもその多くは答えを知っている前提の簡略回路）。RSA-2048を破るには、誤り訂正済みの論理量子ビットが数千個、それを支える物理量子ビットが数百万個規模という見積もりが標準的です（現行機は物理数百〜千個台、誤り訂正はごく初期段階——第7章）。つまり「今日明日にRSAが崩れる」は誇張。一方で、「暗号文を今のうちに収集して、将来解読する（harvest now, decrypt later）」という脅威は現実に扱われており、耐量子暗号（PQC）への移行が進行中です（NISTの標準化は完了済み）。「原理は確立、資源が桁違いに不足、ただし移行は今から」——この三点セットで答えられれば、この章の目標達成です。
演習6
$N = 15$、$a = 2$ で工程を手計算せよ：数列 $2^x \bmod 15$ を書き出して位数 $r$ を求め、因数を計算せよ。
解答を見る
$2, 4, 8, \mathbf{1}, \dots$ → $r = 4$。偶数で $2^2 = 4 \not\equiv -1$。$\gcd(4-1, 15) = 3$、$\gcd(4+1, 15) = 5$。成功。$a = 7$ のときと同じ因数に到達しますが、途中の数列は別物——どの $a$ を通っても、周期という構造が同じ答えを指すのが位数発見の面白さです。
$N = 15$、$a = 14$ は失敗例である。位数を求め、どの条件で弾かれるか確認せよ。
解答を見る
$14 \equiv -1 \pmod{15}$ なので $14^2 \equiv 1$、位数 $r = 2$。偶数ですが $a^{r/2} = 14 \equiv -1$ で条件違反（$\gcd(14+1, 15) = 15$、$\gcd(14-1,15)=13$ と15は互いに素で $=1$。自明な答えしか出ない）。この場合は $a$ を選び直します。数論の定理により、ランダムな $a$ が成功する確率は $\frac12$ 以上——「たまに失敗するが、引き直せばすぐ当たる」乱択アルゴリズムとして全体が設計されています。
位相推定が $\varphi \approx 0.75$ を返したとする（カウント8ビット、測定値 $192/256$）。$\frac{s}{r} = \frac34$ と読んで位数の候補 $r = 4$ を得る流れを確認せよ。また測定値が $128/256 = \frac12$ だった場合、なぜ困るか。どう対処するか。
解答を見る
$0.75 = \frac34$：既約分数の分母4が位数候補。$a^4 \equiv 1$ を検算して確定します。$\frac12$ の場合：真の分数が $\frac{s}{r} = \frac24$ だった（$s = 2$ と $r = 4$ が公約数2を持つ）可能性があり、約分後の分母 $2$ は真の位数ではない（$a^2 \not\equiv 1$ で検算に落ちる）。対処はもう一度位相推定を回す：$s$ は毎回ランダムに引かれるので、数回で $r$ と互いに素な $s$（例: $s = 1, 3$）が出て、正しい $r = 4$ が得られます。検算がついた乱択——古典後処理まで含めてアルゴリズムです。
$U|y\rangle = |2y \bmod 15\rangle$ について、$|1\rangle$ から始めて $U$ を繰り返し適用した軌道 $|1\rangle \to |2\rangle \to \cdots$ を書け。この軌道と位数 $r$ の関係、そして「$U$ の固有状態は軌道上の状態の重ね合わせで作られる」ことの直観を述べよ。
解答を見る
$|1\rangle \to |2\rangle \to |4\rangle \to |8\rangle \to |1\rangle \to \cdots$：長さ $r = 4$ のサイクルです。$U$ はこのサイクル上の「巡回シフト」であり、巡回シフトの固有ベクトルはフーリエ的な重ね合わせ $|u_s\rangle = \frac{1}{\sqrt4}\sum_{t=0}^{3} e^{-2\pi i st/4}|2^t \bmod 15\rangle$（固有値 $e^{2\pi is/4}$）。4つの $|u_s\rangle$ を等重率で足すと位相が打ち消し合って $|1\rangle$ だけが残る——「$|1\rangle$ は固有状態の一様重ね合わせ」という6.2節の事実の中身です。「周期サイクルの巡回シフト → 固有値に $\frac{s}{r}$ が刻まれる」という絵が描ければ、Shorの量子部分の理解としては十分すぎるほどです。
「量子コンピュータは重ね合わせで $a^1, a^2, a^3, \dots$ を全部同時に計算するから速い」という説明は、第0章で否定した「素朴な並列性」とどう違うのか。Shorが素朴な並列性の罠（読み出せない）をどう回避しているか、QFTの役割を中心に説明せよ。
解答を見る
「全部同時に計算」までは同じです（モジュラー累乗をビットオラクル的に全 $x$ へ適用）。違いはその後：素朴な戦略は個々の値 $a^x$ を読もうとして失敗しますが、Shorは個々の値を一切読まず、値の列が持つ周期という大域的性質だけをQFTで位相→ピークに変換して読みます。測定で得るのは $\frac{s}{r}$ の情報だけで、$a^x$ の表は最後まで誰も見ていない。オフセット不変性（第4章）のおかげで「どの値の枝に居たか」も問われない。「全部計算する」が偉いのではなく、「全部を干渉させて1つの数に畳む」が偉い——ステップ3の冒頭に置いた原則の、最も価値の高い実例です。
次の見出しを読んだ知人に、3〜5文で正確な解説をせよ：「中国の研究チーム、量子コンピュータで暗号解読に成功——RSA時代の終焉か」（記事本文には「48ビットの整数を量子アニーリング併用の手法で分解」とある）。
解答を見る
解説例：「48ビット（15桁弱）の整数の分解は古典のノートPCで一瞬で終わる規模で、RSAで使う2048ビットとは比較になりません。また量子アニーリング併用の手法はShorのアルゴリズムとは別物で、桁数に対して指数的に難しくなる壁がそのまま残るため、大きな数への拡張性は示されていません。RSAを脅かすのは誤り訂正済みの大規模な量子コンピュータでShorを回せるようになったときで、資源見積もりは物理量子ビット数百万個規模、現状とは桁が3〜4つ違います。ただし『今の暗号文を保存して将来解読する』リスクは実在するので、耐量子暗号への移行が進んでいるのは合理的です。」——規模（何ビットか）・手法（Shorか否か・拡張性）・時間軸（誤り耐性機の要件）の3点を確認する型は、この種のニュース全部に使い回せます。