講演資料
講義資料スライドの表紙です。上のスライド画像をクリックすると、同じ画面のまま全編のPDF資料を快適に閲覧・印刷することができます。
セミナーの概要
本セミナー「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]。
■ 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]。
■ Part III: Simonのアルゴリズム
「f(x) = f(x⊕a) を満たす周期aを求めよ」というSimonの問題を通じて、量子計算が古典計算を指数関数的に上回る具体的なシナリオと、その背後にある方法論が解明されます。単なる観測ではなく「アダマール変換を再適用してから観測する」という操作が、重ね合わせの中に隠された周期情報を線形代数的に抽出する鍵であることが示されます [p.106, p.111]。
■ Part IV: Shorのアルゴリズム
素因数分解問題が「f(x) = aˣ mod N の周期rを求める問題」に帰着され、その周期発見に量子コンピュータが決定的な役割を果たすことが示されます。Simonのアルゴリズムとの違いは、最後のアダマール変換の代わりに「逆量子フーリエ変換（QFT†）」を用いる点にあり、Phase Estimationがこの全体を統一する枠組みとして機能します [p.146, p.149, p.152]。
ページのナビゲート