講演資料


講義資料スライドの表紙

講義資料スライドの表紙です。スライド画像、または下の要約文中の青いページ番号リンクをクリックすると、別のタブで無駄なノイズのない、純粋なPDFビューア画面が起動し、指定されたページへ直接ジャンプして快適に閲覧できます。

全体概要

本セミナーは、量子計算（Quantum Computing）の基礎的な数理構造から、その代表的なアルゴリズムである量子フーリエ変換（Quantum Fourier Transform: QFT）に至るまでを、系統的かつ厳密に解説する技術講義です。

中心的な「問い」は、「古典的な情報処理の枠組みを超えるとはどういうことか、そしてその超越はいかなる数学的・物理的原理に根ざしているのか」というものです。講義はこの問いに対し、qubitという量子ビットの概念定義から出発し、重ね合わせ・測定・ユニタリ変換という量子力学の公理的枠組みを丁寧に整備したうえで、絡み合い（Entanglement）、超高密度符号化（Superdense Coding）、量子テレポーテーション（Quantum Teleportation）、量子並列性（Quantum Parallelism）といった量子情報科学の核心的現象へと議論を展開します。

技術史的な位置づけとして、本講義は特にShorのアルゴリズムを射程に収めています。Shorのアルゴリズムは素因数分解を多項式時間で解く量子アルゴリズムとして1994年に発表され、現代の公開鍵暗号基盤（RSAなど）を脅かす存在として量子計算の実用的脅威を世界に知らしめました。本講義はそのアルゴリズムの核心部品であるQFTの回路実装を、古典的なDFT（離散フーリエ変換）・FFT（高速フーリエ変換）との対比を通じて明示し、「なぜ量子計算が指数関数的優位を持ちうるか」を具体的な回路構造の段階から理解させる構成を取っています。

探求の結論として本講義が示すのは、n個のqubitがH⊗nゲートにより2ⁿ個の重ね合わせ状態を一度に生成し（量子並列性）、その状態空間全体にフーリエ変換を多項式個のゲート操作で施せるというQFTの本質的効率性です。これは古典FFTのO(N log N)をさらに圧倒するO(n²)の回路複雑度を達成するものであり、位相推定（Phase Estimation）や周期発見（Period Finding）を経由してShorアルゴリズムの指数的高速化を支える基盤となっています。付録ではこれらの応用的文脈も扱われており、理論から実装まで一貫した視点を提供する、高密度かつ体系的な技術講義となっています。

講義のロードマップ

■ Part 1: 量子計算の基礎概念と量子情報の性質

  • この部の核心:

量子計算を支える基本単位であるqubitの数理的定義を確立し、古典ビットとの根本的差異を明示します。さらに、No Cloning定理・Entanglement・Superdense Coding・Quantum Teleportation・Quantum Parallelismという五つの量子情報科学の核心的性質を順に展開することで、「量子系が古典系に対して何が本質的に異なるか」を多角的に論証します。

  • 論理展開:
  • qubitの定義と状態空間: 古典bit（0または1）に対し、qubitはc₀|0⟩+c₁|1⟩（|c₀|²+|c₁|²=1）という複素係数による重ね合わせ状態をとり、Bloch球上で幾何的に表現されます。測定するとBornの規則に従い確率的に収縮します。[p.11], [p.12], [p.14], [p.20]
  • テンソル積と多qubit系: 複数qubitの結合状態はテンソル積⊗で構成され、n qubitはn個の0/1ラベルの積空間{0,1}ⁿ上の2ⁿ次元状態ベクトルで記述されます。[p.28], [p.29], [p.30], [p.31]
  • 量子ゲートとユニタリ演算子: 量子操作はユニタリ演算子Uで表され、内積を保存するという制約が可逆性を保証します。1-qubitゲート（X, Z, H）、2-qubitゲート（CNOT, Control-U）が具体的回路記号とともに定義されます。[p.24], [p.25], [p.43], [p.48], [p.49]
  • No Cloning定理: 任意の未知量子状態|ψ⟩を完全にコピーするユニタリ演算は存在しません。証明は⟨ψ|φ⟩=（⟨ψ|φ⟩）²という矛盾から導かれ、直交状態のみコピー可能という帰結が古典情報との整合性を説明します。[p.57], [p.59], [p.60], [p.65], [p.66]
  • Entanglementと Bell状態: 1/√2(|00⟩+|11⟩)のような状態は積状態に分解不可能な「絡み合い」状態（EPR対）であり、H+CNOTの回路で生成される4種のBell状態として体系化されます。一方のqubitの測定が他方の状態を即座に決定しますが、超光速通信には利用できません。[p.71], [p.72], [p.74], [p.75], [p.80], [p.81], [p.82], [p.83], [p.84], [p.85]
  • Superdense Coding: 1 qubitの物理的送信により2 bitの古典情報を伝達します。Alice側でBell状態に対しI/Z/X/iYを選択適用し、Bob側がBell測定を行うことで実現されます。[p.87], [p.88], [p.90], [p.91], [p.92]
  • Quantum Teleportation: EPR対を事前共有したAlice–Bob間で、AliceがCNOT+Hを適用して2 bitの古典通信を行うことで、Bob側に|ψ⟩を再現します。No Cloningに矛盾せず、Alice側の状態は消滅します。[p.95], [p.96], [p.98], [p.99], [p.101], [p.102], [p.103], [p.104], [p.105]
  • Quantum Parallelism: n qubitにH⊗nを適用すると2ⁿ個の入力に対するUf|x⟩|0⟩を一度に計算でき、∑|x,f(x)⟩の重ね合わせが生成されます。ただし測定すると一つの値しか得られないため、有用な情報抽出には干渉を活用したアルゴリズム設計が必要です。[p.108], [p.109], [p.110], [p.112]

■ Part 2: 量子フーリエ変換（QFT）の理論と回路実装

  • この部の核心:

古典的なフーリエ解析（連続・離散・高速）の数理的構造を段階的に整備したうえで、Quantum Fourier Transform（QFT）がDFTの量子アナログとして定義され、H+Controlled Phase ShiftゲートのみによるO(n²)の回路で実装できることを示します。これがShorのアルゴリズムをはじめとする量子アルゴリズムの指数的優位の核心的基盤となることを明示します。

  • 論理展開:
  • フーリエ級数とDFT: 連続フーリエ変換ではsin/cosが直交基底を形成し（∫sin(mx)sin(nx)dx = πδₘₙ）、任意の周期関数がその線形結合で展開できます。離散版DFTはN点列に対し行列ωʲᵏ（ω=e^{2πi/N}）で定義されるDFT行列で計算されます。[p.117], [p.122], [p.123], [p.143], [p.146], [p.147]
  • FFTとDFT行列の分解: N=8のDFT行列は偶数列・奇数列に並べ替えることで2つのN/2サイズのDFTに分解でき（Cooley-Tukey法）、計算量はO(N²)からO(N log N)へ削減されます。「20世紀最重要のアルゴリズム」と称されます。[p.157], [p.158], [p.159], [p.162], [p.163], [p.164], [p.165], [p.170], [p.173], [p.180]
  • QFTの数学的定義: |j⟩→(1/√N)∑_k e^{2πijk/N}|k⟩で定義され、j=j₁j₂…jₙのビット表現を用いると積形式に展開できます: QFT|j⟩=(|0⟩+e^{2πi0.jₙ}|1⟩)⊗(|0⟩+e^{2πi0.jₙ₋₁jₙ}|1⟩)⊗…。[p.191], [p.199], [p.200], [p.201], [p.202]
  • QFT回路の構成部品: Phase Shift GateRₖ（k段目のビットに対して位相e^{2πi/2ᵏ}を付与）とHadamardゲートを組み合わせ、n(n+1)/2個のゲートでQFTが実装されます。最後にSWAPで出力ビット順を反転します。[p.185], [p.192], [p.197], [p.198], [p.203], [p.204], [p.205], [p.206], [p.208]
  • QFTの優位性: n qubitで2ⁿ個の振幅を持つ状態にQFTを施すのに必要なゲート数はO(n²)であり、古典FFTのO(N log N)=O(n·2ⁿ)と比べ指数関数的に少ないゲート操作で実現します。[p.212], [p.213]

■ Appendix: 周期発見と位相推定

  • この部の核心:

QFTの応用として、Shorアルゴリズムの中核をなす「周期発見（Period Finding）」と、その基盤となる「位相推定（Phase Estimation）」を解説します。これらはQFTが単なる変換操作を超え、整数の数論的性質を量子状態の干渉として読み出す強力な道具であることを示します。

  • 論理展開:
  • Period Finding: f(x)=f(y)⟺x≡y(mod r)を満たす周期rを持つ関数に対し、Ufで∑|x,f(x)⟩を生成し、f(x₀)を測定すると{x₀, x₀+r, x₀+2r, …}に射影されます。QFTを施すとy=kN/rに確率が集中し、N/rの倍数の測定値からrが高確率で特定できます。[p.216], [p.217], [p.218], [p.219], [p.220], [p.221], [p.222]
  • Phase Estimation: ユニタリUの固有状態|u⟩に対するU|u⟩=e^{2πiφ}|u⟩の位相φをt bit精度で推定します。t個の補助qubitを|0⟩で初期化しHを適用後、Controlled-U^{2ᵏ}を順次作用させ、逆QFT（QFT†）を適用して測定することでφを読み出します。Shor・Simonアルゴリズム双方の基盤をなす汎用的プリミティブです。[p.224], [p.225], [p.226], [p.227], [p.228]