MIP*与RE (多方量子交互式证明系统与递归可枚举)

本文是对MIP*=RE1一文的初步梳理, 较少涉及详细的技术细节. 自从这篇文章于2020年初被发表后, 我一直非常想试图阅读, 但总无法提起勇气. 这次由于种种机缘巧合, 我简略阅读了此文, 并参考一些阅读笔记, 记录下文章思路脉络以及重要的结论.

什么是MIP*

MIP*意为"多方量子交互式证明", 其协议可以被称为non-local games, 或者entangled games. 这部分的详细介绍参见原文的第五章.

经典的Non-local Game

Non-local game $G$: 通常用一个裁判 (验证者) 和多个玩家 (证明者) 来描述. 不失一般性, 假设玩家数量为2.

该问题的原始定义如下: $\mathcal G=(\mathcal X,\mathcal Y,\mathcal A,\mathcal B,\mu,D)$, 其中:

  • $\mathcal X$ 和 $\mathcal Y$ 是有限集合, 称为问题表.

  • $\mathcal A$ 和 $\mathcal B$ 是有限集合, 称为答案表.

  • $\mu $是在集合 $\mathcal X\times \mathcal Y$ 上的概率分布, 称为问题分布.

  • $D$ 是一个函数, 其映射为 $\mathcal X\times \mathcal Y \times \mathcal A\times \mathcal B\rightarrow \{0,1\}$.

不失一般性, 将游戏抽象为集合$\{0,1\}$上. 裁判把问题 $(s, t)$ 分发给两个玩家甲和乙, 其中 $(s, t)\in \mathcal S\times \mathcal T$. 甲和乙回复答案 $(a,b)$, 其中$(a,b)\in \mathcal A\times \mathcal B$. $\mathcal A,\mathcal B,\mathcal S,\mathcal T\in\{0,1\}$. 玩家们获胜当且仅当$V(a,b|s,t)=(a\otimes b=s\land t)$. 裁判可能的提问满足分布$\pi$.

注意以下几点:

  • 这个游戏不是玩家间的零和博弈, 玩家只可能同时获胜, 或同时失败.
  • 玩家和裁判之间的问答规模是多项式的.

那么, 玩家之间的最大获胜概率表示如下:

上面的公式是对于经典的non-local game, 即玩家不共享纠缠. 显然, 他们获胜的概率为$3/4$.

纠缠的Non-local Game

下面考虑玩家共享纠缠的情况.

如果玩家共享希尔伯特空间 $\mathcal H_A\otimes \mathcal H_B$ 上的一个纠缠态 $| \psi\rangle \in \mathcal H_A\otimes \mathcal H_B$, 玩家甲和乙的游戏策略集合是两个希尔伯特空间上的POVM (一种正定的投影测量), 或表示为

且满足归一性

那么, 玩家之间的最大获胜概率表示如下:

一个结论:

即纠缠的游戏中, 玩家的获胜率约为0.85, 高于经典的游戏.

由Non-local Game引申的定义

上面介绍了最基本的两种Non-local Game. 下面类比在经典计算理论中的一系列"复杂性类"的定义, 定义出该问题的一系列复杂性类. 以下的"量子关联集合", 全部定义为满足特定结构的$(|\psi\rangle, \{X_s^a\},\{Y_t^b\})$.

  • $\mathcal H_A, \mathcal H_B$ 都是有限维度的希尔伯特空间, 两个玩家共享纠缠态 $|\psi\rangle \in \mathcal H_A\otimes \mathcal H_B$, 两个玩家的策略 $\{X_s^a\}$ 与 $\{Y_t^b\}$ 分别定义在 $\mathcal H_A$ 与 $\mathcal H_B$ 上. 这样的量子关联集合记为 $C_q$.

  • $\mathcal H_A, \mathcal H_B$ 都是无限维度的希尔伯特空间, 两个玩家共享纠缠态 $|\psi\rangle \in \mathcal H_A\otimes \mathcal H_B$. 两个玩家的策略 $\{X_s^a\}$ 与 $\{Y_t^b\}$ 分别定义在 $\mathcal H_A$ 与 $\mathcal H_B$ 上. 这样的量子关联集合记为 $C_{qs}$.

  • $H_A^{(l)},H_B^{(l)}$是一族可数维度的希尔伯特空间, 两个玩家共享纠缠态 $|\psi\rangle^{(l)} \in \mathcal H_A^{(l)} \otimes \mathcal H_B^{(l)}$. 两个玩家的策略 $\{X_s^a\}^{(l)}$ 与 $\{Y_t^b\}^{(l)}$ 分别定义在 $\mathcal H_A^{(l)}$ 与 $\mathcal H_B^{(l)}$ 上. 这样的量子关联集合记为 $C_{qa}$.

    $C_{qa}$ 是 $C_{qc}$ 的闭包.

  • $\mathcal H$ 是一个无限维度的希尔伯特空间, 两个玩家共享纠缠态 $|\psi\rangle \in \mathcal H$, 两个玩家的策略 $\{X_s^a\}$ 与 $\{Y_t^b\}$ 都定义在 $\mathcal H$ 上, 并且有 $\forall a,b,s,t,[X_s^a, Y_t^b]=0$. 这样的量子关联集合记为 $C_{qc}$.

    $C_{qc}$是对易算符模型对应的量子关联.

  • 不共享纠缠的经典的问题集合记为 $C_c$.

由上述定义, 显然有:

之前已证明了:

Tsirelson问题: 究竟是否有 $C_{qa}=C_{qc}$?

MIP*=RE这篇文章解决了这一问题,解决方案是给出了最后一个真包含的反例的具体构造: 即存在一个non-local game, 它在对易算符模型下的最优获胜概率是$1$, 但是在张量积模型下的最优获胜概率至多是$1/2$.

MIP, MIP* 与 MIP$^{co}$

对于交互式证明体系: 常数个证明者 (prover), 一个验证者 (verifier), 通常验证者的能力是经典概率多项式时间的, 而证明者的能力不受限制 (尽管同时他们也不受验证者的信任), 证明者和验证者之间的通信规模是多项式的.

基于交互式证明体系的两个复杂性类:

  • 如果只有一个证明者, 这样的交互式证明系统 (IP) 完全刻画了多项式空间 (IP=PSPACE);
  • 如果有多个证明者, 这样的交互式证明系统 (MIP) 完全刻画了非确定性指数时间 (MIP=NEXP).

对于PSPACE和NEXP的定义可以任意参考关于经典计算复杂性理论的文章.

而上面的Non-local Game也是交互式证明系统. 我们再将刚才的复杂性类定义如下:

  • MIP: 当证明者之间不共享纠缠时, 判定 $C_c$ 的交互式证明系统的最大获胜概率对应的复杂性类称作MIP.
  • MIP*: 当证明者之间共享任意的纠缠时, 判定 $C_{qa}\cup C_{qs} \cup C_{qa}$量子交互式证明系统的最大获胜概率对应的复杂性类称作MIP*.
  • MIP$^{co}$: 当证明者之间共享希尔伯特空间, 且他们的策略是对易的 (称为对易算符模型, commuting operator model), 判定 $C_{qc}$ 量子交互式证明系统的最大获胜概率对应的复杂性类称作MIP$^{co}$.
  • MIP*$(c,s)$: 如果最大获胜概率至少 $s\leq 1$, 至多是 $c \geq s \geq 0$, 对应的复杂性类记作MIP*$(c,s)$. 如果 $c-s$ 是常数, 那么MIP* = MIP*$(c,s)$.

什么是RE

图灵机

图灵机是一种计算模型, 其定义省略, 可以任意参考关于经典计算复杂性理论的文章.

邱奇-图灵论题 (Church–Turing Thesis) 给出了一个重要的假说: 任何在算法上可计算的问题同样可由图灵机计算, 即任何的算法可以用一台图灵机模拟. 这个论题虽仍不能用公式证明, 但已接近完全, 可被认为是"可计算"的一个公理.

RE: 递归可枚举

而何为"递归"? 任何算法都可以被一个图灵机 $M$ 所描述. 判断图灵机是否停机的办法为: 运行一步看是否停机, 若不停机再运行一步, 若不停机再运行一步, 以此类推. 若图灵机能停机, 就总有一步会停, 但也有可能永远不停. 这样的尝试过程就是递归, 其复杂性类即为RE.

RE是递归可枚举 (Recursively Enumerate), 递归可枚举是等价于图灵可识别的.

对于集合 $X$, 若 $X$ 是递归可枚举集, 那么存在一台图灵机 $M$ 识别 $X$, 即对于 $\forall x\in X$, 若在 $ x$ 上运行 $M$, $M$ 一定在有限步内停机并接受. 对于 $\forall x \notin X$, 若在 $x$ 上运行 $M$, $M$要么在有限步内停机并拒绝, 要么不停机.

更详细的定义或性质可以任意参考关于经典计算复杂性理论的文章.

co-RE: 补递归可枚举

co-RE即为RE的补, 即对于集合 $X$, 若 $X$ 是补递归可枚举集, 那么存在一台图灵机 $M$ 识别 $X$ 的补集, 即对于 $\forall x\notin X$, 若在 $ x$ 上运行 $M$, $M$ 一定在有限步内停机并接受. 对于 $\forall x \in X$, 若在 $x$ 上运行 $M$, $M$要么在有限步内停机并拒绝, 要么不停机.

MIP*与RE

下面依次列出一些重要的引理, 并在这些引理之上, 证明RE $\subseteq$ MIP*, 进而即立刻有 MIP* = RE.

MIP $\subseteq$ NEXP

经典交互式证明系统的上界为NEXP. 这是一个平凡的上界. 注意到验证者可能的提问数量至多是指数的 (因为证明者和验证者之间的通信复杂度至多是多项式的), 对每个问题穷举可能的答案就能找到证明者们的最优策略, 即非确定性指数时间 (NEXP).

MIP* $\subseteq$ RE

张量积模型上的量子交互式证明系统的上界为RE. 这是一个平凡的上界. 注意到 $C_{qa}$ 定义在一系列可数维度 $l$ 的序列上 (Sum-of-squares hierarchy 可以给出更好的刻画), 那么我们可以设计一个图灵机, 先考虑 $l=1$ 的所有量子策略, 再考虑 $l \leq 2$ 的所有量子策略, 以此类推. 如果存在某个量子策略使得获胜概率为1的话, 那么图灵机停机并接受 (YES Case), 除此之外不做任何操作 (不停机, 不拒绝). 因此MIP*是在RE中的.

MIP$^{co}$ $\subseteq$ co-RE

对易算符模型上的量子交互式证明系统上界为co-RE. 类似 Sum-of-squares hierarchy, 这里会用到类似的"对偶"层次, 即 NPA hierarchy2 . 其大致定义如下: 考虑一个序列, 第一个量子关联的集合只涉及玩家甲和玩家乙的量子策略的对易关系中只涉及一个量子比特的, 第二个集合只涉及玩家们的策略的对易关系中至多涉及两个量子比特的, 以此类推. 如果没有用到所有的对易约束关系的玩家们的量子策略都不能使得最大获胜概率为1的话, 那么显然没有这样的量子策略, 于是这里的图灵机在 NO Case (最大获胜概率小于1) 一定会停机. 因此MIP$^{co}$是在co-RE中的.

MIP $\subsetneq$ MIP*

一篇2019年的工作3 (FOCS 2019 best paper) 证明了 NEEXP $\subseteq$ MIP, 进而即有MIP $\subsetneq$ MIP*.

NEEXP意为nondeterministic doubly exponential time. 这是一个对交互式证明系统下界的改进, 并且表明了纠缠的证明系统至少比经典的证明系统指数地更强大.

RE $\subseteq$ MIP*: 用多方量子交互式证明验证停机问题

其基本思路为: 使用间隙不变压缩 (gap-preserving compression) 过程.

首先, 如果使用普通的压缩 (套娃) 过程作用在 Non-local Game上, 会有以下的事情发生:

  • 第一次压缩: NEXP $\subseteq$ MIP*$(1,1/2)$
  • 第二次压缩: NEEXP $\subseteq$ MIP*$(1,1-\exp(-n))$
  • 第三次压缩: NEEEXP $\subseteq$ MIP*$(1,1-\exp(\exp(-n)))$
  • ...
  • 第$\infty$次压缩: RE = NEE...EXP $\subseteq$ MIP*$(1,1_{-})$, 其中$1_{-}$表示小于1且以1为极限.

但如果能保持压缩的间隙不变 (找到一个 gap-preserving compression), 做到以下的事情:

  • 第一次压缩: NEXP $\subseteq$ MIP*$(1,1/2)$
  • 第二次压缩: NEEXP $\subseteq$ MIP*$(1,1/2)$
  • 第三次压缩: NEEEXP $\subseteq$ MIP*$(1,1/2)$
  • ...
  • 第$\infty$次压缩: RE = NEE...EXP $\subseteq$ MIP*$(1,1/2)$ = MIP*

我们就能证明前面本节标题的结论.

回忆工作3 (FOCS 2019 best paper) 证明了 NEEXP $\subseteq$ MIP $\subseteq$ MIP*, 这意味着我们可以迫使两个玩家继续采样指数规模的问题, 虽然玩家和裁判有多项式规模的通信.

过去的观点认为玩家之间共享纠缠会伤害 Non-local Game 的可靠性 (soundness), 但实际上量子纠缠可以帮助到诚实 (honest) 的玩家. 而工作3的一大贡献即为给出了一个保持间隙的压缩技术 introspection. 但这个技术不能直接用在MIP*问题上. 它有一定的局限性: 仅仅对特定类似的问题分布 (如 plane-v.s.-point test 中的分布) 成立, 而迭代使用这一间隙不变压缩技术会导出更复杂的分布; 验证答案的分布也有类似的问题.

但幸运的是, introspection 其实是对一类概率分布封闭的, 所以我们可以把上述技术改进为下述步骤:

  1. 用 introspection 压缩原 non-local game 中问题的规模, 得到一个新的 non-local game.

  2. 用 PCP composition 来压缩上面的 non-local game 中回答的规模, 得到一个新的 non-local game.

    PCP 问题与 PCP composition 不再赘述, 可以任意参考关于经典计算复杂性理论的文章.

  3. 注意到诚实的玩家们的最大获胜概率, 即完备性 (completeness), 在前两步后不变, 我们只需要用 anchored parallel repetition4 来减小可靠性 (soundness).

把求解张量积模型的 non-local games 的最大获胜概率的图灵机写成一个 non-local game, 并且不断应用上述间隙不变压缩技术. 那么如果图灵机停机, 最大获胜概率是 1; 否则如果图灵机不停机, 最大获胜概率不超过 1/2. 这就证明了MIP*的下界是RE.

MIP$^{co}$与co-RE? 仍悬而未决

类似地, 我们也猜测MIP$^{co}$ = co-RE, 但这个问题仍未被完全证明.

参考文献

[1] MIP*=RE原文

[2] NPA hierarchy方法

[3] NEEXP in MIP*原文

[4] anchored parallel repetition 原文