Shorのアルゴリズム入門

全体概要

本セミナー「3時間で学ぶShorのアルゴリズム入門」は、現代の公開キー暗号・RSA暗号の安全性の根拠を根底から覆す可能性を持つ「Shorの素因数分解アルゴリズム」を、量子計算の基礎から丁寧に積み上げ、その全体像を解き明かすことを目指しています [p.1], [p.2]。

RSA暗号は、二つの大きな素数p, qの積Nを公開鍵として用い、「Nを知っていても素因数p, qを求めることは古典コンピュータでは極めて困難」という数論的事実を安全性の礎にしています。Peter Shorが1994年に発見したアルゴリズムは、量子コンピュータを用いれば、この素因数分解が多項式時間で実行できることを示しました [p.2], [p.3]。発見から25年間、量子コンピュータの実現可能性が低いとみなされていたためこの脅威は軽視されてきましたが、近年の量子技術の急速な進展を背景に、NSAやNISTが「ポスト量子暗号」への移行を本格化させており、Shorのアルゴリズムへの関心は新たな高まりを見せています [p.3]。

本講義の探求の出発点は「量子ビット（qubit）とは何か」という素朴な問いであり、そこからユニタリ変換・量子ゲート・テンソル積・量子回路という基礎概念を積み上げ、Quantum Parallelismの本質的な威力と限界を明らかにします。次に、Shorのアルゴリズムの「精神的な前身」であるSimonのアルゴリズムを詳しく解析することで、「量子コンピュータの出力をどのように有用な情報として取り出すか」という核心的な問いに答える方法論を習得します。最終的にShorのアルゴリズムへと到達し、「関数の周期を求める問題（Period Finding）」が素因数分解に還元され、その周期発見に量子フーリエ変換とPhase Estimationが決定的な役割を果たすことを論証します。量子計算の不思議さと美しさ、そして暗号技術の未来への深い示唆を与える、密度の高い一本の論理的旅路です。

講義のロードマップ

■ Part I: 量子計算の基礎

• この部の核心:

量子コンピュータが「なぜ速いのか」を理解するための数学的・概念的基盤を構築します。古典ビットが0か1の離散的な点であるのに対し、量子ビット（qubit）は複素数係数を持つ二次元ベクトルとして「重ね合わせ」の状態を取ること、そしてqubitの状態変化が「ユニタリ変換」として記述されることが、すべての議論の出発点となります [p.9], [p.17]。

• 論理展開:
• qubitは `a|0⟩ + b|1⟩`（|a|²+|b|²=1）で表現される二次元複素ベクトルであり、観測によって重ね合わせは崩壊し確率的に|0⟩か|1⟩に変化します [p.9], [p.15], [p.16]。
• 量子ゲートはユニタリ行列と一対一に対応し、代表的なゲートX（Bit Flipper）、Z（Phase Flipper）、H（Hadamard）の行列表現と動作が示されます [p.22], [p.23]。Hadamardゲートは `H|0⟩ = |+⟩`、`H|1⟩ = |−⟩` という基底変換を実現し、`HH = I`（自己逆）という重要な性質を持ちます [p.27], [p.29], [p.30]。
• 複数qubitの合成系はテンソル積（⊗）で記述され、`|00⟩, |01⟩, |10⟩, |11⟩` が2-qubit系の基底を成します [p.33], [p.42]。
• 量子回路は直列・並列・コントロール（Control-U）の三形式で構成され、全体としてユニタリ性（可逆性）を保たなければならないという制約から、任意の古典関数f(x)を計算するユニタリ回路 `U_f` の一般形（補助ビット Ancilla を用いる形式）が導かれます [p.44], [p.61], [p.62], [p.65], [p.66], [p.67]。

■ Part II: Quantum Parallelism

• この部の核心:

n個のqubitにHadamard変換を適用することで、2ⁿ個すべての基底の等しい重ね合わせが生成できます。これをU_fへの入力とすれば、一度の回路実行でf(x)のすべての値が並列計算されるという「量子並列性（Quantum Parallelism）」の驚くべき威力が示されます。しかし同時に、この出力を「観測（測定）」した瞬間に重ね合わせは崩壊し、一つのxに対するf(x)しか得られないという本質的な限界も明確にされます [p.93], [p.94], [p.97], [p.102], [p.103]。

• 論理展開:
• n個のHadamardゲートを並列に適用することで `H⊗ⁿ|0⟩⊗ⁿ = (1/√(2ⁿ)) Σ|xᵢ⟩`（2ⁿ個の基底の均等重ね合わせ）が生成されます [p.80], [p.83], [p.84], [p.85]。
• この重ね合わせをU_fに入力すると、出力は `(1/√(2ⁿ)) Σ|x⟩|f(x)⟩` となり、n個のqubitで2ⁿ個の並列計算が実現します [p.92], [p.93], [p.94], [p.95]。
• Born則による観測では重ね合わせが崩壊して一つの `|x₀⟩|f(x₀)⟩` しか得られないため、量子並列性だけでは古典計算と比較した優位性を引き出せません [p.100], [p.101], [p.102], [p.103]。有用な情報を取り出すには「何か追加の仕組み」が必要であることが示されます。

■ Part III: Simonのアルゴリズム

• この部の核心:

「f(x) = f(x⊕a) を満たす周期aを求めよ」というSimonの問題を通じて、量子計算が古典計算を指数関数的に上回る具体的なシナリオと、その背後にある方法論が解明されます。単なる観測ではなく「アダマール変換を再適用してから観測する」という操作が、重ね合わせの中に隠された周期情報を線形代数的に抽出する鍵であることが示されます [p.106], [p.111]。

• 論理展開:
• Simonの問題では、ビット列xとaのXOR（⊕）を用いて f(x) = f(x⊕a) が成立する「周期」aを量子的に求めます。具体的な関数表（n=3の場合）で問題の難しさが直観的に示されます [p.107], [p.108]。
• 回路はHadamard群 → U_f → ターゲットレジスタ観測 → Hadamard群 → 第一レジスタ観測という流れで動作します。U_f後の状態は `|Ψ⟩' = Σ ((|x₀⟩+|x₀⊕a⟩)/√2)|f(x₀)⟩` に整理され、ターゲット観測によりデータレジスタが f(x₀) の「原像の重ね合わせ」に崩壊します [p.115], [p.116], [p.118], [p.119], [p.130], [p.131]。
• 数学的解析により、最終出力 `|Ψ₄⟩` はy・a = 0（mod 2）を満たすyのみの重ね合わせとなることが証明され [p.135]、複数回の試行でn-1個の線形方程式を集めることでaが決定できます [p.138]。

■ Part IV: Shorのアルゴリズム

• この部の核心:

素因数分解問題が「f(x) = aˣ mod N の周期rを求める問題」に帰着され、その周期発見に量子コンピュータが決定的な役割を果たすことが示されます。Simonのアルゴリズムとの違いは、最後のアダマール変換の代わりに「逆量子フーリエ変換（QFT†）」を用いる点にあり、Phase Estimationがこの全体を統一する枠組みとして機能します [p.146], [p.149], [p.152]。

• 論理展開:
• フェルマーの小定理と確率的素数判定（フェルマーテスト）を準備として、「aˣ mod N の周期rが偶数でar/2 ≠ -1 (mod N) ならば gcd(ar/2±1, N) がNの非自明な因数を与える」という核心的事実が示されます。N=15, a=7, r=4の例では gcd(50,15)=5, gcd(48,15)=3 と素因数が求まります [p.141], [p.144], [p.145], [p.146]。
• Phase Estimationは、ユニタリ演算子Uの固有値 e^{2πiφ} における未知のφを、Control-U^j 回路 → 逆QFT → 測定という手順で推定するアルゴリズムです。「Phase kick-back」により第一レジスタに位相情報が埋め込まれ、逆QFTがそれをデジタル情報として取り出します [p.153], [p.156], [p.160], [p.161], [p.162], [p.167]。
• 周期発見への適用では `U|y⟩ ≡ |xy (mod N)⟩` を定義し、このUの固有ベクトル `|uₛ⟩` の固有値 exp[2πis/r] がPhase Estimationで推定されることでs/rが判明し、連分数展開によりrが決定されます [p.169], [p.170], [p.172], [p.173]。
• N=15を実際に素因数分解する具体例で、第二レジスタ観測 → 逆QFT実行 → 周波数ピーク（0, 512, 1024, 1536）の観測 → 1536/2048=3/4 よりr=4を同定 → 15=3×5 を得るという全手順が実演されます [p.175], [p.176], [p.177], [p.178], [p.179]。
• 周期aがN=2ⁿを割り切る場合は周波数スペクトルが完全に離散的になる一方、割り切れない場合はスペクトルが広がるという実際上の困難も示され、観測値からrを確定する作業の複雑さが示唆されます [p.182], [p.183]。