講演資料
講義資料スライドの表紙です。上のスライド画像をクリックすると、同じ画面のまま全編のPDF資料を快適に閲覧・印刷することができます。
セミナーの概要
本セミナー「nonlocalゲームとInteractive Proof #01」は、量子情報科学・計算複雑性理論の核心に迫る「nonlocalゲーム」の入口として設計された講義シリーズの第一回です。扱われる「ゲーム」は一見シンプルな設定ながら、その背後には情報理論・確率論・量子もつれといった深い概念が折り重なっています。
中心的な「問い」は明快です。――「互いに会話できない二人のプレイヤーが、出題者の問題に協力して答えるとき、どこまで勝率を高められるか？」。この問いは、古典的な確率戦略の限界を浮き彫りにし、後続の議論で量子もつれを用いた量子戦略がその限界を突破することを示すための土台となります。
本講義（第01回）では、まず古典的な枠組みのみで議論が展開されます。プレイヤーAとBは出題者Vから個別に問題（0または1）を受け取り、互いに通信できない状況でそれぞれ答え（0または1）を返します。勝利条件は「xy = a ⊕ b」という単純なXOR条件で表現されますが、この条件をすべての問題パターンに対して同時に満たす古典的な決定論的戦略は存在しないことが明らかになります。
その上で、ランダム戦略では勝率が1/2にとどまること、そして事前の打ち合わせによる「常に同じ答えを返す」という素朴な決定論的戦略によって勝率が3/4まで引き上げられることが計算されます。この3/4という数値は、古典的戦略の「上限」を示す重要なベンチマークとなります。後続回では、量子もつれ状態を共有することでこの古典的限界（3/4）を超えられることが示される予定であり、本回はその比較対象としての古典的ベースラインを丁寧に確立する役割を担っています。
nonlocalゲームはBell不等式の検証とも深く関連しており、物理的な「局所隠れ変数理論」の限界を情報ゲームの言葉で再定式化したものともいえます。本シリーズを通じて、量子計算・量子暗号の基礎にある非局所相関の本質を、数理的に厳密かつ直感的に理解することを目指しています。
講義のロードマップ
ここでは、セミナーの講演資料がどのようなパートから構成されているかを示します。また、それぞれのパートのポイントを紹介します。
■ Part 1: ゲームの設定と基本構造の定義
プレイヤーA・BとVerifier（出題者V）の三者で構成されるnonlocalゲームの基本フレームワークを確立します。AとBはチームを組みVと対峙しますが、ゲーム中の相互通信は厳禁であり、この制約がゲームの本質的な困難さを生み出します [p.2, p.3, p.4]。
■ Part 2: 勝利条件の定義とXOR表現への変換
「x, yのいずれかが0のとき a=b、x=y=1のとき a≠b」という二条件からなる勝利ルールを定義し、これが単一の数式 **xy = a ⊕ b**（XOR条件）に等価であることを確認します [p.8, p.9, p.10, p.11, p.12, p.13]。
■ Part 3: 必勝法の不在と古典的限界の確認
相互通信が禁止された状況では、A・Bがゲーム中に相手の受け取った問題値を知ることができないため、全問題パターンを完璧にカバーする決定論的必勝戦略は原理的に存在しないことを論じます [p.14]。
■ Part 4: 勝率の定量的計算と最適古典戦略の導出
双方がランダムに答えた場合の勝率が1/2にとどまることを計算し、次いで事前に戦略を取り決める（常にa=b=0、または常にa=b=1を返す）ことで勝率が3/4まで向上することを示します。この3/4が古典的戦略の重要な上限として機能します [p.15, p.16]。
ページのナビゲート