MIP*=RE 入門– Interactive Proofとnonlocal ゲーム —

2020/12/25 マルゼミ「MIP*=RE 入門」概要

このセミナーですが、次のような構成を考えています。

第一部「Nonlocal Game– エンタングルメントとゲーム」では、アインシュタインらの「隠れた変数論」を理論的に否定して量子論を基礎づけたBellの仕事と、それをゲームの形で表現したCHSHゲームの話をします。1960年代に始まる研究です。

「非局所的」なエンタングルメントの際立った性質は、エンタングルした量子を共有するゲームプレーヤーが、たとえゲーム中の直接のコミュニケーションを禁止されていたとしても、古典的なゲームプレーヤーより高いゲーム勝率を持つ「nonlocal game」で、実験的にもはっきりと確かめることができます。

第二部「Interactive Proof — 複雑性理論の古典論とその転換」では、1970年代に Cook, Levin, Karpらによって始まった「NP-完全」の理論を中心とする複雑性理論の発展を振り返ります。現在では、複雑性理論の「古典論」とも呼ばれるものの始まりです。複雑性理論の「古典論」は、90年代に大きく発展します。エポック・メイキングだったのは「Interactive Proof」という証明手法の発見です。

PとNPの関係は、多くの人はご存知だと思いますが、同じような関係を、EXPとNEXPの間に考えることができます。前者のEXPは指数関数的時間で証明可能な問題の複雑性のクラスで、後者のNEXPは、ある問題の解が正しいことを、指数関数的時間でチェックできる問題の複雑性のクラスです。

セミナーでは、この時期の代表的な到達点である、「MIP=NEXP」（複雑性クラスNEXPは、Interactive Proof MIPで認識できる複雑性のクラスと一致する）の話をしたいと思います。

第一部と第二部でみた二つの流れは、21世紀に入ってから合流していきます。

第三部「MIP* = RE 定理 — 量子論と複雑性理論の交わるところ」は、この間の「量子複雑性」の理論で、もっとも重要な発見である「MIP* = RE」の話です。「MIP* = RE」は、MIP*クラスが、Turingマシンの「停止問題」のクラスと同様に「計算不可能」だということを意味します。

セミナーでは、「MIP* = RE」定理の証明の骨組みを構成している、「停止問題」から、二人のプレーヤーによるnonlocalゲームがエンタングルした値1を持つかあるいは最大でも1/2の値を持つかどちらかなのかを決定する問題への、実効的な還元が存在するというロジックの大まかな流れを紹介しようと思います。