なぜ21は素因数分解されないのか？ - Shorのアルゴリズムの現在と壁

2025/10/14にQuantum Tokyoで開催した「なぜ21は素因数分解されないのか？ - Shorのアルゴリズムの現在と壁」の登壇資料です。

Transcript

1. なぜ21は素因数分解されないのか？ Shorのアルゴリズムの現在と壁 Daiki Murata Qiskit Advocate
2. 2 Daiki Murata Qiskit Advocate / IT Architect IBM Consulting, IBM Japan Quantum Tokyo Japanese Quantum Community Online Textbooks
3. 3 Quantum Tokyo 有志の日本向け Qiskit Community です。 Qiskit を中心に量子コンピュータに関する勉強 会やイベントを開催しています。 量子コンピュータの初学者も積極的にスピー カーとして登壇しています！ • YouTube チャンネル • Quantum Tokyo へようこそ ※本日の発表は個人の学習・研究結果の共有であり、 所属企業の見解や立場を示すものではありません。
4. きっかけ 4 https://algassert.com/post/2500 2001年、量子コンピュータは「15」という数を因数 分解しました。 そして今は2025年ですが、量子コンピュータはまだ 「21」を因数分解できていません。 このことから、「量子コンピュータの進歩は止まって いる証拠だ」と言われることがあります。 しかし実際には、「21」がまだ因数分解されていない のには、もっと驚くべき理由があります。
5. 本日のテーマ 5 量子コンピュータはなぜ(素)因数分解が得意と言われるのか？ なぜ最初の実験から20年以上経った今も21は解けないのか？ を理解しよう！
6. 目次 1. 量子コンピュータと素因数分解 2. Shor のアルゴリズム 3. Demo (N=15) 4. N=21への挑戦 6
7. 7 量子コンピュータと 素因数分解
8. 量子の不思議な性質を利用して 特定の問題を効率的に解くことが期待されているコンピュータ 量子コンピュータとは
9. 量子の不思議な性質 9 不確定な重ね合わせが 確定した1状態に収束 （量子特有） 測定 干渉 重ね合わせ 複数の状態を同時に持つ （波としての量子） 重ね合わせの状態どうしが 強め合ったり弱め合ったりする （波としての量子）
10. 量子コンピュータの活躍領域 10 分子の化学シミュレーション 膨大な計算が必要で、スーパーコンピュータでも困難 乱数生成 古典コンピューターでは疑似乱数しか生成できず、 シミュレーションのスケーラビリティに制約 素因数分解 現在の暗号は素因数分解の困難性 （作るのは簡単、解くのは困難）に基づいている 2048ビット整数: 47億年 創薬・材料研究 並列計算で膨大な組み合わせを計算 複雑な社会現象シミュレーション 量子乱数により、疑似乱数の周期性による制約から解放 新しいセキュリティ技術 量子アルゴリズムでは8時間 計算の困難性以外のアプローチによる セキュリティ技術の開発
11. 量子計算がもたらす変化 11 1994年アメリカの数学者 Peter Shor によって 量子計算を活用することで、素因数分解を効率的に 解けることを理論的に提唱（Shor のアルゴリズム） 計算時間が(準)指数関数時間から多項式時間へ これまでの暗号安全性の前提が根本から崩れる 引用: Quantum Expert Insight: Peter Shor | Qiskit YouTube
12. Shorのアルゴリズム
13. Shorのアルゴリズム 13 因数分解は「周期」を見つけると解ける
14. 因数分解を別の問題に置き換える 14 Nの因数は、数学的に 𝑎𝑟 ≡ 1 mod 𝑁 を満たす最小の周期r（位数）を求めれば導けることが知られています 𝑎𝑟 ≡ 1 mod 𝑁 ↓ 𝑎 𝑟 2 + 1 𝑎 𝑟 2 − 1 = 0 mod 𝑁 ↓ 𝑎 𝑟 2 ± 1 がNと非自明な因数を持つ
15. 例: N=21 15 例えば、N = 21, 𝑎 = 4 の場合 21 ≡ 2 mod 21 22 ≡ 4 mod 21 23 ≡ 8 mod 21 24 ≡ 16 mod 21 25 ≡ 11 mod 21 26 ≡ 1 mod 21 27 ≡ 2 mod 21 ⋮ 𝑎𝑟 ≡ 1 mod 𝑁を満たす最小のr（位数）は 6 • 2 6 2 + 1 = 9と21の最大公約数は3 • 2 6 2 − 1 = 7と21の最大公約数は7
16. 量子計算で周期を見抜く 16 古典コンピュータは周期を「1つずつ」試す。 量子コンピュータは「すべてのaを同時に試して、周期的な干渉パターンを観測」できる。 量子位相推定（Quantum Phase Estimation） 周期的な操作の周期情報は、その操作の固有値（位相変化）に現れる
17. Shorのアルゴリズム 17 1. 前処理（古典計算） Nに対してランダムに整数 aを選ぶ (a と N は互いに素) 2. 量子位相推定（量子計算） 𝑈 ۧ |𝑥 → ۧ |𝑎𝑥 mod 𝑁 の固有値を推定し、固有値に書き込まれた周期 情報を取り出す 3. 後処理（古典計算） 周期 r から N の因数を計算 ただし、条件を満たさず因数が得られない場合 は別の a を選んで1-2を繰り返す 2.1重ね合わせ 2.2 位相推定
18. 参考）量子位相推定 18 モジュラー指数関数 𝑼𝟐𝒎−𝟏 𝑈 ۧ |𝑥 → ൿ |𝑎2𝑚−1 𝑥 mod 𝑁 重ね合わせを利用して 𝑎𝑚𝑥 mod 𝑁 を同時に計算 → 位相に周期情報を刻む 逆量子フーリエ変換 干渉を利用して重ね合わせの状態の中から周期が 一致する成分を強調させる → 1回の操作で何周期進むか(周期の逆数)にピーク が出現 𝑐 2𝑚 ∼ 𝑠 𝑟 重ね合わせを作る
19. Demo (N=15)
20. Shorのアルゴリズムの実装 20 1994年に Shor のアルゴリズムが提唱され、 2001年に IBM と MIT の研究チームが初めて実験的に N=15の素因数分解を成功させました。 20年以上経った現在では クラウド経由で誰でも量子コンピュータを実行できる 時代となっています。 引用:It’s been 20 years since “15” was factored on quantum hardware | IBM Quantum Research Blog
21. Qiskitを使った実装 21 𝑈1 𝐼𝑄𝐹𝑇 𝑁 = 15, 𝑎 = 11
22. 𝑈𝑓 の実装 22 例えば 𝑎 = 11 の場合（※何でもOK） ۧ |𝑥 ۧ |1 → 𝑈 ۧ |𝑥 ۧ |111 mod 15 = ۧ |𝑥 ۧ |11 ۧ |𝑥 ۧ |1 𝑈2 ۧ |𝑥 ۧ |112 mod 15 = ۧ |𝑥 ۧ |1 ۧ |𝑥 ۧ |1 𝑈4 ۧ |𝑥 ۧ |114 mod 15 = ۧ |𝑥 ۧ |1 U2以降は状態を変化させていないので無視！ ↓ 一番最初の ۧ |1 → 𝑈 ۧ |11 つまり ۧ |0001 → 𝑈 ۧ |1011 の変換操作が実現できればOK a=11では状態変化が発生しないから 考慮不要 1 0 0 0 1 1 0 1
23. 位数（周期）の推定（7量子ビットシミュレータ） 23 測定値 10進数𝑐 位相𝑐/2𝑚 𝑠/𝑟の候補 | ۧ 000 | ۧ 0 0/8 = 0.00 0/1 | ۧ 100 | ۧ 4 4/8 = 0.50 1/2 | ۧ 101 | ۧ 5 5/8 = 0.62 5/8 | ۧ 110 | ۧ 6 6/8 = 0.75 3/4 | ۧ 001 | ۧ 1 1/8 = 0.12 1/8 | ۧ 111 | ۧ 7 7/8 = 0.88 7/8 | ۧ 010 | ۧ 2 2/8 = 0.25 1/4 | ۧ 011 | ۧ 3 3/8 = 0.38 3/8 位数 r の推定値は2 shot=10000 ビット数を増やすほど 位相の推定精度が向上
24. 因数の計算 24 11𝑟 ≡ 1 mod 15を満たす最小の r は 2 • 11 2 2 + 1 = 12と15の最大公約数は3 • 11 2 2 − 1 = 10と15の最大公約数は5 ↓ 15 = 3 × 5
25. 21の因数分解への挑戦
26. Qiskitを使った実装 26 ? 𝑁 = 21 𝑎 = 4
27. N=21の場合 27 100倍以上の計算コスト ※N=15の回路 回路が100倍以上複雑に
28. 位数の推定（133量子ビットシミュレータ） 28 shot=10000, backend=FakeTorino 非常に恣意的に見ればr=2 • 4 2 2 + 1 = 5と21の最大公約数は1 • 4 2 2 − 1 = 3と21の最大公約数は3 ↓ 21の因数は3 ↓ 21 = 3 × 7
29. 位数の推定（ 133量子ビット実機） 29 shot=10000, backend=ibm_torino 実機では全然だめ・・・
30. なぜ21の因数分解は難しいのか？ 30 • 汎用的なモジュラー乗算回路が必要 N=15 場合、固有の性質を利用した演算の簡略化や、Toffoli ゲートを必要としない軽量実装が可能。 例:指数が進むとすぐに「1」が現れる（例: 112 = 1 mod 15）など 一方 N=21 ではそうはいかず、Toffoli ゲートだらけの本格的な乗算回路の実装が必要 • 誤差やデコヒーレンスの影響 回路が深く、エンタングリングゲートもN=15と比べて100倍以上の量子回路では要求精度も厳しい。 現在のハードウェアの精度ではQFTのピークが潰れてしまいやすい。 • ハードウェアの制約 ハードウェアの多くは量子ビットは最近接結合のため、実際のデバイスでShorの量子回路を実行する 場合は、2量子ビットゲートを物理的に実行可能とするためにSWAPゲートが必要となり、より一層回 路を肥大化させてしまう。
31. 参考）”ズル”をすればShor回路も簡単に構築可能 31 測定値 10進数𝑐 位相𝑐/2𝑚 𝑠/𝑟の候補 | ۧ 000 | ۧ 0 0/8 = 0.00 0/1 | ۧ 010 | ۧ 2 2/8 = 0.25 1/4 | ۧ 100 | ۧ 4 4/8 = 0.50 2/4 | ۧ 110 | ۧ 6 6/8 = 0.75 3/4 | ۧ 001 | ۧ 1 1/8 = 0.12 1/8 ⋯ ⋯ ⋯ ⋯ 位数 r の推定値は４ ↓ 35 = 7 × 5 例: N=35 𝑈1 𝑈2 𝑈4 事前に 𝑎𝑥 mod 𝑁 の動きを把握 して回路を構築
32. 暗号解読の現在地はまだまだ「教材」レベル 32 • RSA2048を破るには数千万量子ビットが必要 Shorのアルゴリズムによって理論的には現在の暗号技術を破ることは可能 しかし現実の実装には桁違いのスケールを必要とする（10⁶倍以上の規模差） • 誤り訂正が膨大なリソースを要求 誤り訂正可能な1つの論理量子ビットの実現には数千〜数万の物理量子ビットが必要 現在の100物理量子ビットの規模ではまだまだ実現は遠い
33. 量子コンピュータはまだまだ将来の技術なのか？ 33 実験レベルから Utility Scale の時代へ I. Nature paper (127 qubits x 60 entangling gates) II. 1D Transverse Ising model (70 qubits x 80 entangling gates) III. The largest GHZ state challenge Replay (YouTube)： https://www.youtube.com/playlist?list=PLA- UlvpIBvpuzFXRPNTqiK94kfRgYCBMs Jupyter notebookの和訳： https://quantum-tokyo.github.io/introduction/courses/utility-scale-quantum- computing/overview-ja.html チャプター 1. はじめ 2. 量子ビット・量子ゲート・量子回路 3. 量子テレポーテーション 4. グローバーのアルゴリズム 5. 量子位相推定 6. 量子変分アルゴリズム 7. 量子系のシミュレーション 8. 古典計算によるシミュレーション 9. 量子ハードウェア 10. 量子回路の最適化 11. 量子エラー緩和 12. 量子ユーティリティーの実験 I 13. 量子ユーティリティーの実験 II 14. 量子ユーティリティーの実験 III 2025年の Quantum Tokyo で解説 Replay を YouTube で公開中！
34. 量子時代のセキュリティ 34 引用: 量子コンピュータの実用化と耐量子暗号の標準化動向
35. まとめ 35 • 量子コンピュータを使った素因数分解の高速化は理論上は可能 Shorのアルゴリズムは「暗号解読」の側面だけでなく、量子計算の力を最初に実証 した象徴的な成果 • ただしN=21のような小さな数でも実装に非常に大きな回路を必要とするため、 現在の技術では非常に限定的 • 量子コンピュータ自体は utility scale の時代へ 将来の実用化に備えてセキュリティ面では現在から耐量子暗号の取り組みが進めら れている
36. 復習教材 36 • 本日の検証 Jupyter Notebook | Quantum Tokyo へようこそ • Shor’s algorithm | IBM Quantum Documentation • ショアのアルゴリズム | IBM Quantum Challenge 2021