ショアのアルゴリズム — 素因数分解は「周期発見」だった

大きな数の素因数分解は古典計算機の手に負えない — その事実が RSA 暗号を30年支えてきました。ショアのアルゴリズムはこの問題を「関数の周期を見つける問題」に言い換え、周期だけは量子フーリエ変換（QFT）で一発で読み取ります。N=15 のトイ例で、変換のからくりから QFT のピークが立つ瞬間まで全工程を動かします。

1. 世界で一番有名な「難しい問題」

15 = 3 × 5 は暗算できますが、桁数が数百になると話は別。既知の最良の古典アルゴリズム（数体ふるい法）でも計算量は準指数的に増え、2048ビットの合成数は事実上分解不可能です。RSA 暗号はこの「掛け算は簡単・分解は困難」という非対称性そのものを鍵にしています。

1994年、ピーター・ショアが示したのは、量子計算機なら素因数分解が多項式時間で解けるという事実。ポイントは、量子計算機が「分解が得意」なのではなく、周期的なパターンの周期を読むのが得意だということです。だから戦略はこうなります：分解を周期発見に翻訳し、周期だけ量子に解かせ、残りは古典で仕上げる。

2. 分解を「周期発見」に言い換える

N = 15 を分解したいとします。N と互いに素な数 a を選び、関数 f(x) = ax mod N を眺めると、値は必ず循環します。たとえば a = 7 なら 7, 4, 13, 1, 7, 4, 13, 1, … と周期 r = 4。この r さえ分かれば、あとは最大公約数（gcd）の計算だけで因数が転がり出てきます。下のデモで a を変えて、周期と因数の出方を確かめてください。

f(x) = a^x mod 15 の周期 → 因数への変換（ステップ実行）
点の色は「周期の中の位置（x mod r）」。同じ色が等間隔に並ぶ＝周期的。緑の破線は値 1 — ここに戻ってくるまでの長さが周期 r。下段の計算は「次のステップ」で1行ずつ進みます。どの a でも最後は 15 = 3 × 5 に辿り着くことを確認してください。
ar ≡ 1 (mod N)　⟹　(ar/2 − 1)(ar/2 + 1) ≡ 0 (mod N) N の素因数がこの2つの括弧に分かれて入っていれば、gcd(ar/2 ± 1, N) が非自明な因数を与える
POINT — 失敗することもある（が、すぐやり直せる） r が奇数のとき、または ar/2 ≡ −1 (mod N) のときは因数が出ない。たとえば a = 14 は r = 2 だが 14 ≡ −1 なので失敗する。それでもランダムに選んだ a で成功する確率は 1/2 以上と証明されており、数回引き直せばまず当たる。gcd や検算などの古典パートはすべて高速 — 唯一の難所「r を見つける」だけを量子に任せるのがショアの設計。

3. 量子で周期を見つける — 4つのステージ

では本丸、r をどう量子で見つけるか。x レジスタ（ここでは Q = 32 状態）と f(x) 用のレジスタを用意し、①重ね合わせ → ②f(x) の並列計算 → ③f 側の測定 → ④QFT、の4段階で進みます。③で x レジスタに残るのが周期 r の「櫛」状の重ね合わせ — ここが最大の見どころです。

量子周期発見 — x レジスタの振幅を4ステージで追う（a=7, N=15, Q=32）
ステージ②の色は f(x) の値（7x mod 15 ∈ {1, 7, 4, 13}）。③の測定で f の値が1つランダムに選ばれ（リセットごとに変わります）、その色の x だけが生き残って間隔4の櫛になる。④の QFT で櫛は k = 0, 8, 16, 24 のピークに化ける — 間隔 Q/r = 8 から r = 4 が読める。
POINT — 「並列計算だから速い」のではない ②の時点で f(0)〜f(31) は確かに全部同時に計算されている。だが測定すればランダムな1つが出るだけで、これでは古典と変わらない。ショアの本質は、欲しい情報が個々の値ではなく「間隔 r」という全体のパターンである点。③でどの f 値が選ばれても櫛の間隔は必ず r で、④の QFT（干渉）がその間隔だけを取り出す。選ばれた f の値（＝櫛の開始位置）は QFT 後の振幅の大きさに影響しない。

4. QFT ＝ 周波数を読む装置

QFT は音声信号処理の章で学んだフーリエ変換の、確率振幅版そのものです。時間領域の周期的なパルス列がスペクトル上で等間隔のピークになる — あの対応が振幅の世界でもそのまま成り立ちます。周期 r の櫛に QFT をかけると、ピークは Q/r の倍数の位置に立ちます。スライダーで櫛の周期と開始位置を変えて確かめてください。

櫛 → QFT → ピーク（Q=32 の離散フーリエ変換を実計算）
上＝x レジスタの櫛、下＝QFT 後の振幅の大きさ。r が 32 を割り切るとき（2, 4, 8）ピークは完璧に鋭い。割り切らないとき（3, 5, 6, 7）はピークが最寄りの整数 k に「にじむ」— 実際のショアでは測定した k から k/Q ≈ j/r を連分数展開で復元してこのにじみを処理する。開始位置 x₀ を動かしても下段が変わらないことにも注目。
QFT: |x⟩ ⟼ (1/√Q) Σk e2πi kx/Q |k⟩ 周期 r の櫛 → 間隔 Q/r のピーク。測定した k から連分数展開で r の候補を得る

5. RSA への影響 — そして「今」との距離

周期発見が多項式時間になった結果、鍵長 n ビットの RSA を破るコストは古典の準指数からおよそ n³ のオーダーまで落ちます。鍵を伸ばして逃げようにも、多項式相手では焼け石に水です。

RSA 鍵長 vs 計算量 — 古典（数体ふるい法）と量子（ショア）
縦軸は必要な演算回数の対数。赤＝古典最良（準指数：鍵長を伸ばすとまだ急増する）、緑＝ショア（多項式 〜n³：ほぼ平ら）。RSA-2048 で古典は約10³⁵回 — 10¹⁸回/秒のマシンでも宇宙年齢を超える。ショアは約10¹⁰ゲート規模で、理想的な誤り訂正付き量子計算機なら数時間〜1日のオーダーという試算。
注意 — 「まだ先」でも移行は今：耐量子暗号 RSA-2048 を破れる量子計算機は当分現れない。それでも暗号の移行が今始まっているのは、「今盗んで、後で解読する」（harvest now, decrypt later）が成立するから — 暗号化された通信を保存しておけば、10年後の量子計算機で開けられる。NIST は 2024 年に格子ベースの ML-KEM（Kyber）/ ML-DSA（Dilithium）などを耐量子暗号として標準化し、各国で置き換えが進行中。
一歩先へ — 現実の実装規模とのギャップ ショアの回路は深く長く、ノイズに極端に弱い。RSA-2048 を破るには誤り訂正済みの論理量子ビットが数千個必要で、物理量子ビットに換算すると数百万〜2000万個・実行時間約8時間という試算がある（Gidney & Ekerå 2019）。対して現在の実機は物理量子ビット数百〜千個規模で、誤り訂正はようやく損益分岐点を越えた段階。実際に量子計算機で堂々と分解されたのは、本章のトイ例と同じ 15 = 3 × 5 や 21 = 3 × 7 といった規模である。ギャップは巨大 — しかし原理は既に検証済み、というのが現在地。

6. まとめ