量子科技中心_量科网

在2020年，Ji、Natarajan、Vidick、Wright和Yuen的一项里程碑式成果表明，MIP*（即可由经典验证者与多个共享张量积模型纠缠的无限计算能力证明者交互决定的语言类）等于RE。该研究团队证明，MIPco类（一个与MIP*类似定义的复杂性类，但证明者共享的是交换算子模型纠缠）等于coRE类。这表明为证明者提供两种不同的纠缠模型会导致交互式证明系统产生两种完全不同的计算能力。 该工作的证明建立在MIP*=RE证明中使用的压缩定理基础上，并使用可迹嵌入策略框架来证明MIP*=RE中的相同压缩过程在交换算子设置中也具有相同的期望性质。该研究团队还通过整合Mousavi等人[STOC 2022]使用的同步框架以及de la Salle[ArXiv:2204.7084]引入的改进Pauli基测试，为非局域游戏提供了更简化的压缩定理证明。 该研究团队引入了一个新的RE/coRE完全问题的等价条件，称为“弱可压缩条件”。该研究团队通过压缩定理证明MIP*和MIPco都满足这个条件，从而确立了MIP*和MIPco的不可计算性可以在统一框架下得到证明（尽管这两个复杂性类不同）。值得注意的是，这种方法也为MIP*=RE定理提供了另一种证明，该证明不依赖于纠缠界的保持。除了非局域游戏外，这个新条件也可能适用于其他决策问题。