講演資料
講義資料スライドの表紙です。スライド画像、または下の要約文中の青いページ番号リンクをクリックすると、別のタブで無駄なノイズのない、純粋なPDFビューア画面が起動し、指定されたページへ直接ジャンプして快適に閲覧できます。
全体概要
本セミナー「Interactive Proof = nonlocalゲーム」は、計算複雑性理論における中心的な枠組みである「Interactive Proof（対話型証明）」と、量子情報理論・量子基礎論の文脈で生まれた「nonlocal（非局所）ゲーム」が、実は同一の数学的構造を持つという驚くべき認識の統一を主題としています。
この二つの概念は、それぞれ異なる動機のもとで独立に発展してきました。nonlocalゲームの代表例であるCHSHゲームは1960年代に誕生し、量子論が古典論とは本質的に異なることを理論的・実験的に示す文脈で使われてきました。一方、Interactive Proofは1990年代に計算複雑性理論の枠組みとして発展し、「検証者（Verifier）」と「証明者（Prover）」の対話によって定理の正しさを確率的に検証するという仕組みとして確立されました。両者が同一の構造を持つという認識が生まれたのは、21世紀に入ってからのことです [p.4]。
その構造的な共通点の核心は、Verifier（出題者）が二人の参加者AliceとBobに対してそれぞれ質問x、yを送り、回答a、bを受け取るという「1ラウンドの対話」にあります。nonlocalゲームではAliceとBobは「プレーヤー」と呼ばれ、Interactive ProofではAliceとBobは「Prover（証明者）」と呼ばれますが、図式としては完全に一致します [p.5]〜[p.10]。
この対応の意義はさらに深く、nonlocalゲームの枠組みで用いられる「戦略」の概念——すなわち、プレーヤーが古典的相関 Cc を使うか、量子論的相関 Cq（エンタングルメント）を使うかの違い——が、Interactive Proofにおける証明者の能力の違い、すなわちMIP（古典的）とMIP*（量子エンタングルメントを使う場合）の区別に直接対応しています [p.14], [p.15]。
本セミナーは、この深い対応関係を「確率的証明」という概念の導入を通じて丁寧に解説し、量子情報と計算複雑性という二つの分野が、どのように同じ問いへと収束してきたかを体系的に示します [p.17]。
講義のロードマップ
■ Part 1: nonlocalゲームとInteractive Proofの構造的同一性
- この部の核心:
CHSHゲームやMagic Squareゲームなどのnonlocalゲームは、量子論の非局所性を示す文脈から生まれましたが、その構造——出題者から二人のプレーヤーへの質問と回答——はInteractive Proofにおける検証者と証明者の対話と完全に一致します。この認識の確立が本セミナー全体の出発点です [p.2], [p.3], [p.4]。
- 論理展開:
- nonlocalゲームの「非局所性」とは、エンタングルメントによって古典的相関を超えた勝率が実現できることに由来します [p.2]。
- nonlocalゲームのプレーヤー（Alice/Bob）をそのままProver（証明者）と読み替えれば、図式は完全にInteractive Proofと一致します [p.7], [p.8]。
- 逆に、Interactive ProofのProverを「ゲームのプレーヤー」と見なせば、Interactive Proofはnonlocalゲームでもあります [p.10]。
■ Part 2: nonlocalゲームの定式化
- この部の核心:
nonlocalゲームは三つの要素——質問の分布 µ(x,y)、質問と回答の条件付き確率 p(a,b|x,y)、勝敗判定関数 D(a,b,x,y)——によって厳密に数理的に定式化されます。この定式化はInteractive Proofにもそのまま適用可能であり、両者の統一的な扱いを可能にします [p.12]。
- 論理展開:
- CHSHゲームの具体例では、µ(x,y)は0と1の一様分布、勝敗は a+b = xy (mod 2) で決まります [p.13]。
- 戦略 p が古典的相関 Cc に属するか量子的相関 Cq に属するかで勝率 ω(G,p) が変化します [p.14]。
- 古典最大勝率は ωc(CHSH)=3/4、量子最大勝率は ωq(CHSH)=cos²(π/8) であり、Magic Squareでは ωc=8/9、ωq=1（完全勝利）が成立します [p.15]。
■ Part 3: Interactive Proofへの「確率的証明」概念の導入
- この部の核心:
nonlocalゲームとInteractive Proofの対応関係は、Interactive Proofにゲームの勝率 ω(G,p) や量子最大勝率 ωq(G) の概念を持ち込むことを正当化します。これが「確率的証明」という新しい概念の核心であり、MIP*という複雑性クラスの理解への道を開きます [p.16], [p.17]。