自 2003 年 Kobayashi 和 Matsumoto 开始考虑多方量子交互式证明系统 (MIP∗\sf MIP^*) 之后, 直到十七年后的 2020 年初, 人类终于得到了 MIP∗\sf MIP^* 的完全刻画, 即 MIP∗=RE{\sf MIP^*}={\sf RE}. 从计算复杂性的角度来说, 这也意味着我们可以用多方量子交互式证明来验证停机问题, 并且量子纠缠的力量远远超过了我们的想象 (多方经典交互式证明系统的能力与非确定性指数时间相同). 更出人意料的是, 这一结果一并给出了 Tsirelson 问题的否定答案, 以及推翻了算子代数中的 Connes 嵌入猜想. 这应该是计算复杂性理论上世纪七十年代以降最为深刻的结果之一.

这篇文章会简单地解释这一结果的意义, 并描述这一结果对量子计算复杂性理论, 以及对其他领域的影响. 除此之外, 我也会非常简单地介绍如何证明这一结果, 即如何用多方量子交互式证明来验证停机问题.

更多的技术细节可以在此前的 量子交互式证明可以验证停机问题吗? 一文中找到. 譬如不同模型下的 non-local games 定义的对应的计算复杂性类, 以及对应类型的量子关联之间的联系. 因而对这些复杂性类完全刻画, 会导出量子关联和算子代数中的出人意料的结论, 如 Tsirelson 问题的否定回答, 以及推翻 Connes 嵌入猜想 (Connes embedding conjecture). 最后, 关于 Connes 嵌入猜想, 推荐阅读Thomas Vidick 去年十月份在 AMS Notices 上写的介绍, 解释了这个问题和算子代数之间的深刻联系.

值得一提的是, 季铮锋老师同时 (也是唯一一位) 参与了 QIP=PSPACE{\sf QIP}={\sf PSPACE} [1] 和 MIP∗=RE{\sf MIP^*}={\sf RE} [2] 的证明. QIP\sf QIP 的 PSPACE\sf PSPACE 上界刻画 [1:1] 的困难更多是技术层面的, 大致想法和一两年前 QRG(1)\sf QRG(1) 或者 QIP(2)\sf QIP(2) 的上界证明别无二致. 但 MIP∗\sf MIP^* 的故事则要复杂得多 (推荐阅读 Thomas Vidick 的 回忆文章), 困难不仅仅是技术层面的 (譬如如何实现 non-local games 的间隙不变的压缩过程). 时光倒流到五年之前, 我想应该没有人会觉得 MIP∗\sf MIP^* 会等于 RE\sf RE.

当我们在谈论 MIP*=RE 的时候我们在说什么

在这一节我会解释一下这一结果 [5] 的标题在说什么.

多方量子交互式证明

首先是等号的左边, MIP∗\sf MIP^*, 即多方量子交互式证明系统是什么?

如果读者对 Bell 不等式有一些了解的话, 就会知道两方的量子关联 (quantum correlation) 能取到经典关联 (classical correlation) 取不到的值. 如果从交互式证明的观点看的话, 那么这里共享纠缠的两方对应两个玩家 (即证明者), 量子关联中的局部可观测量 (local observable) 可以看成两个玩家对裁判 (即验证者) 提出的问题所采取的的策略, 并且玩家和裁判之间的通信是经典的. 这样的 non-local games 就是一个 MIP∗\sf MIP^* 协议, 其中 MIP∗\sf MIP^* 是多个证明者的量子交互式证明的复杂性类.

Non-local games: 以 CHSH game 为例 (图片来自 Quantum mechanics: The usefulness of uselessness)

如果读者不知道我上一段在说什么的话, 推荐阅读 量子 PCP 猜想浅说 (二): 量子纠缠的交互式证明验证. 第一节中的 CHSH game 就是一个具体的例子 (譬如上图), 这里的量子策略和经典策略可以看成上一段中的量子关联和经典关联.

递归可枚举 / 图灵可识别语言

那么等号的右边 RE\sf RE 是什么呢?

RE\sf RE (recursively enumerate / Turing recognizable) 是个很容易望文生义的词. 任何算法都可以被形式化的写成一个图灵机, 图灵机就是一个有控制器, 任何可以在无限长的纸带上读写的东西. 怎么判断一个图灵机能不能停机呢? 一种办法是, 先看看一步的时候会不会停, 再看看两步的时候会不会停, 以此类推, 如果图灵机能停机的话, 那么总有一步会停下来. 当然, 也可能这台图灵机多少步都停不下来.

这样的一步一步尝试的过程对应的复杂性类就是 RE\sf RE, 更多的细节可以在本科层次 (及以上) 的计算复杂性理论教材中找到.

MIP*=RE 意味着什么

为什么这个结果非常深刻呢? 至少有几个方面的影响:

量子关联: Tsirelson 问题的否定回答

从量子关联 (或者说相对物理?) 的角度说, [2:1] 给出了 Tsirelson 问题的否定回答.

回到上面的 non-local games, 把 Bell 不等式中的情形一般化得到的是张量积模型 (tensor-product model), 也就是说两个玩家的量子策略分别作用于自己拿到的那部分纠缠态所在的量子比特, 以及自己手上的那部分量子比特. 但是也可以考虑另一种一般化, 即两个玩家除了自己手上的那部分量子比特, 还有一部分量子比特是公共的, 他们的策略可以作用在公共部分和自己的部分上, 并且两个玩家选取不同策略的顺序不会影响结果 (即对易), 这称作对易算符模型 (commuting-operator model).

我在 量子交互式证明可以验证停机问题吗? 中写过更形式化一些的定义, 这里简要的重复一下记号. 张量积模型对应量子关联的集合是 Cqs\mathcal{C}_{qs} (以及它的闭包 Cqa\mathcal{C}_{qa}, 即以任意常数维度的纠缠来近似), 而对易算符模型对应的量子关联的集合是 Cqc\mathcal{C}_{qc}. 类似地, 经典的多方交互式证明对应的经典关联的集合是 Cc\mathcal{C}_c, 此外, 玩家们共享纠缠的维度为固定常数的量子关联 (譬如前文中提及的 CHSH game) 的集合是 Cq\mathcal{C}_{q}.

那么, 根据这些经典关联 / 量子关联的定义, 不难得到下述关系: Cc⊊Cq⊆Cqs⊆Cqa⊆Cqc.\mathcal{C}_{c} \subsetneq \mathcal{C}_{q} \subseteq \mathcal{C}_{qs} \subseteq \mathcal{C}_{qa} \subseteq \mathcal{C}_{qc}. 第一个真包含是 Bell 不等式 (或者说 CHSH game) 的直接推论. Boris Tsirelson 在上世纪八十年代问了这么一个问题:

这两个不同的模型 (张量积模型和对易算符模型) 定义的非局域性 (non-locality) 是否是等价的?

即 Cqa=Cqc\mathcal{C_{qa}} = \mathcal{C_{qc}} 是否成立.

最近五年的一系列进展告诉我们, 事实上 Cq⊊Cqs⊊Cqa⊊Cqc\mathcal{C}_{q} \subsetneq \mathcal{C}_{qs} \subsetneq \mathcal{C}_{qa} \subsetneq \mathcal{C}_{qc}. 这篇文章 [2:2] 给出了最后一个真包含的反例的具体构造: 即存在一个 non-local game, 它在对易算符模型下的最优获胜概率是 1, 但是在张量积模型下的最优获胜概率至多是 1/2.

算子代数: 推翻 Connes 嵌入猜想

从算子代数的角度说, [5] 推翻了 Connes 嵌入猜想.

CEC 据说是算子代数里核心的几个公开问题之一, 但是我对 C∗^*-algebra 没有太多的了解, 除了某些细枝末节但是很有用的结论. CEC 和 Kirchberg 的 QWEP 猜想等价, 而 [3] 证明了 CEC 和 Tsirelson 问题等价. 这篇文章 [2:3] 中没有给出 CEC 的直接反例构造, 这也是他们遗留的公开问题之一. Jalex Stark 在 SciRate 的评论区给了一段算子代数观点下的解释.

更多数学方面的影响推荐阅读 Gil Kalai 的博文: Amazing: Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen proved that MIP* = RE and thus disproved Connes 1976 Embedding Conjecture, and provided a negative answer to Tsirelson’s problem.

计算复杂性理论: MIP* 的完全刻画

从计算复杂性的角度说, [2:4] 给出了复杂性类 MIP∗\sf MIP^* 的完全刻画.

具体来说, 从 2012 年到 2020 年, 我们在逐渐改进 MIP∗\sf MIP^* 的下界:
MIP=NEXP⊆QMAEXP⊊NEEXP⊊RE⊆MIP∗⊆RE{\sf MIP}={\sf NEXP} \subseteq {\sf QMA_{EXP}} \subsetneq {\sf NEEXP} \subsetneq {\sf RE} \subseteq {\sf MIP^*} \subseteq {\sf RE}.

在 QIP=PSPACE=IP{\sf QIP}={\sf PSPACE}={\sf IP} [1:2] 后, 关于 MIP∗\sf MIP^* 的很自然的下界猜测是 NEXP{\sf NEXP}, 但是玩家们允许共享纠缠意味着他们哄骗裁判的方式可以花样翻新 – Ito 和 Vidick 在 2012 年 [4] 用了一些复杂的分析证明了可靠性 (soundness), 即下界是 NEXP. 进一步地改进困难重重, 直到 2018 年, Natarajan 和 Vidick 用近似群表示和低次多项式检测 [4:1][5], 把下界推进到了QMAEXP\sf QMA_{EXP}[5:1]. 我们还能做的更好吗? 去年 Natarajan 和 Wright 用间隙不变 (gap-preserving) 的方式重新实现了 [6][7] 中的压缩 (compression) 技术, 出人意料地给出了下界 NEEXP\sf NEEXP [8]. 而这篇文章 [2:5] 则说 MIP∗\sf MIP^* 甚至可以验证停机问题 (注意到停机问题是 RE\sf RE-complete 的), 用他们的技术不难推出 MIPlog∗{\sf MIP^*_{log}} 也可以验证停机问题!

这意味着之前 Fitzsimons 和 Vidick 提出的 games quantum PCP conjecture 其实并不是一个有意义的问题 – MIPlog∗{\sf MIP^*_{log}} 的 QMA\sf QMA-hard 下界 [5:2] 并没什么特别之处, 只是 MIP∗\sf MIP^* 的完全刻画的一个中间结果. 我们知道, 经典 PCP 定理可以从交互式证明和不可近似性两个角度理解, 并且两个版本的等价证明非常简单. 但是这个结果 [2:6] 意味着量子 PCP 猜想的两个版本, 即 Hamiltonian quantum PCP 和 games quantum PCP, 更像是两个完全独立的问题, 也许经典 PCP 定理的不同解释只是一个巧合.

关于量子 PCP 猜想 (特别是 games quantum PCP), 推荐阅读我之前的系列文章:

如何用多方量子交互式证明验证停机问题

这一节我会试着给出这篇文章 [2:7] 的证明思路, 并非常简要地介绍涉及的相关技术. 对此感兴趣的读者, 推荐阅读 [2:8] 的前两节 (约 20 页), 涵盖了本文涉及 (以及未涉及) 的所有内容, 可读性很好.

从"套娃"式"遛狗"过程谈起

直白地说, 间隙不变压缩 (gap-preserving compression) 过程可以看成一系列套娃过程 – 如果把两个玩家一个裁判的指数规模通信的 non-local game 看成一个俄罗斯套娃的话, 那么

  • Non-local game 的压缩技术[6:1] , 就是把这个套娃压缩成多项式规模的;
  • Non-local game 的迭代压缩技术[7:1] 确实是套娃, 因为可以不断地重复压缩 – 或者说, 套娃.

俄罗斯套娃 (图片来自网络)

哦不, 准确地说, [1,2] 做的事情应该写成这样:

  • 第一次套娃: NEXP⊆MIP∗(1,1/2){\sf NEXP} \subseteq {\sf MIP^*}(1,1/2)
  • 第二次套娃: NEEXP⊆MIP∗(1,1−exp⁡(−n)){\sf NEEXP} \subseteq {\sf MIP^*}(1,1-\exp(-n))
  • 第三次套娃: NEEEXP⊆MIP∗(1,1−exp⁡(−exp⁡(n))){\sf NEEEXP} \subseteq {\sf MIP^*}(1,1-\exp(-\exp(n)))
  • ⋮\vdots
  • "无穷"次套娃: RE=NEE⋯EEXP⊆MIP∗(1,<1){\sf RE} = {\sf NEE\cdots EEXP} \subseteq {\sf MIP^*}(1,<1)

上一段的"套娃"技术 [6:2][7:2] 告诉我们一件事, 即如何压缩一个 non-local game. 或者说的更技术一些, 对于一个指数规模问题和答案的 non-local game, 我们可以通过让证明者们共享更多纠缠来把问题和答案的规模压缩 (compression) 成多项式的, 但是 non-local game 的获胜概率需要的精度会更高 [6:3][7:3]. 也就是说 MIP∗\sf MIP^* 协议 的完备性 (completeness) 和可靠性 (soundness) 之间的间隙会被缩小 – 这样的压缩技术可以给出 RE\sf RE 的 MIP0∗\sf MIP^*_0 协议, 即判断最大获胜概率是 1 还是小于 1.

如果把一个图灵机写成 non-local game 的话, 那么图灵机的计算步骤数 nn 可以看成两个玩家之间共享的 EPR 对的数量. 而一次"压缩"过程意味着新的 non-local game 所对应的图灵机的计算步骤数被指数增加到 2n2^n, 也就是两个玩家之间共享指数多的 EPR 对. 那么如果我们考虑"套娃压缩"过程的话, 最终得到的 non-local game 所对应的图灵机可能是不会停机的, 这意味着两个玩家之间需要共享无穷多的 EPR 对 (或者说共享的纠缠态的维度是无穷大的).

那么有办法使得"压缩套娃"的过程中的完备性-可靠性间隙保持不变吗? 或者说, 我们想把上面的套娃过程变成下面这样:

  • 第一次套娃: NEXP⊆MIP∗(1,1/2){\sf NEXP} \subseteq {\sf MIP^*}(1,1/2)
  • 第二次套娃: NEEXP⊆MIP∗(1,1/2){\sf NEEXP} \subseteq {\sf MIP^*}(1,1/2)
  • 第三次套娃: NEEEXP⊆MIP∗(1,1/2){\sf NEEEXP} \subseteq {\sf MIP^*}(1,1/2)
  • ⋮\vdots
  • "无穷"次套娃: RE=NEE⋯EEXP⊆MIP∗(1,1/2){\sf RE} = {\sf NEE\cdots EEXP} \subseteq {\sf MIP^*}(1,1/2)

量子态的自检测可以在一些场景下帮助我们做到, 见 量子 PCP 猜想浅说 (二): 量子纠缠的交互式证明验证 的第二节. 具体来说, 量子态的自检测可以看成下述遛狗场景, 我们觉得他们 (狗) 之间共享"纠缠", 但是显然我们并不能学着汪汪汪一番问出来答案 – 我们只能用遛狗的绳子 (leash) 来设法测试他们之间是否真的共享"纠缠", 其实这和自检测 (self-testing) 的思路很像, 我们只用和狗之间的特定类型的通信 (绳子), 来确认他们是否满足某些性质.

Self-testing (图片来自网络)

自检测 (self-testing) 是说如果两方共享的纠缠很接近很多对 EPR 对的话, 那么对应的 non-local game 的最大获胜概率就越接近于 11 [4:2][5:3], 并且玩家们的最优量子策略满足我们想要验证的性质. 再加上合适的技术给玩家们分发"量子证明" (注意到量子态不可克隆, 并且我们不能用约化密度矩阵来区分不同量子态), 我们可以得到间隙不变 (gap-preserving) 的 MIP∗\sf MIP^* 协议, 这就是 Natarajan 和 Vidick 证明的 games quantum PCP [5:4]: QMAEXP⊆MIP∗{\sf QMA_{EXP}} \subseteq {\sf MIP^*}.

间隙不变压缩技术

看到这里, 似乎证明 MIP∗=RE{\sf MIP^*}={\sf RE} 的思路非常自然, 只需要一找到一个能够间隙不变的 non-local games 压缩技术 (gap-preserving compression)!

Natarajan 和 Wright 获得 FOCS 2019 最佳论文奖的工作 [8:1] 告诉我们这样的技术是存在的 (见 Thomas Vidick 的博文, Randomness and interaction? Entanglement ups the game!): NEEXP⊆MIP∗{\sf NEEXP} \subseteq {\sf MIP^*}! 换言之, 我们可以迫使两个玩家老老实实地采样指数规模的问题, 虽然玩家和裁判之间只有多项式规模的通信 – 只需要让诚实的玩家们仍然使用纠缠就好了! 这样的想法源自于 [6:4][7:4], 而且几乎是全新的 – 因为人们用了很长一段时间理解为什么玩家之间共享的纠缠可能会伤害 non-local game 的可靠性 (soundness), 并且最终用近似群表示理论证明了这样的事情并不会发生 [4:3][9], 但很长一段时间里人们并没有意识到量子纠缠也可以帮助老老实实的玩家们. [8:2] 中进一步证明了这样的压缩技术 (即 introspection) 也可以做到保持间隙.

同样, 尽管答案也是指数规模的, 我们可以使用经典 PCP 定理中的 composition (或者说 PCP of proximity) 来帮助裁判验证答案的正确性. 关于 PCP of proximity 可以进一步参考 Alessandro Chiesa 的讲义 中的内容及参考文献.

如果我们能够迭代使用这样的间隙不变压缩技术的话, 那么按照 [7:5] 中的逻辑, 不难推出 RE⊆MIP∗{\sf RE} \subseteq {\sf MIP^*}. 但是 [8:3]中的 introspection 有一些局限性, 譬如说仅仅对特定类似的问题分布 (如 plane-v.s.-point test 中的分布) 成立, 而迭代使用这一间隙不变压缩技术会导出更复杂的分布; 验证答案的分布也有类似的问题. 但幸运的是, introspection 其实是对一类概率分布 (即 conditionally linear distribution [2:9]) 封闭的! 所以我们可以把 [8:4] 中的间隙不变压缩技术改进为下述步骤:

  1. 用 introspection 压缩原 non-local game 中问题的规模, 得到一个新的 non-local game.
  2. 用 PCP composition 来压缩上面的 non-local game 中回答的规模, 得到一个新的 non-local game.
  3. 注意到诚实的玩家们的最大获胜概率, 即完备性 (completeness), 在前两步后不变, 我们只需要用 anchored parallel repetition [10] 来减小可靠性 (soundness).

上述步骤可以把一个指数规模的 non-local game 压缩多项式规模的, 并且保持完备性和可靠性之间的间隙不变. 这就是 [2:10] 中的间隙不变压缩 (gap-preserving compression) 技术.

终章: 停机问题的多方量子交互式证明协议

如果我们把求解张量积模型的 non-local games 的最大获胜概率的图灵机写成一个 non-local game, 并且不断应用上述间隙不变压缩技术的话. 那么如果图灵机停机, 那么最大获胜概率是 11; 否则如果图灵机不停机, 最大获胜概率不超过 1/21/2. 这就证明了 MIP∗\sf MIP^* 的 RE\sf RE 下界, 同时注意到 MIP∗\sf MIP^* 的平凡上界也是 RE\sf RE (因为枚举玩家间共享的纠缠态的维度), 从而导出 MIP∗=RE{\sf MIP^*}={\sf RE}.

此外, 为了给出 Tsirelson 问题的否定回答. 我们需要考虑对易算符模型下的 non-local game 的 SDP hierarchy (具体来说是 NPA hierarchy), 即通过逐渐增加玩家们共享的纠缠态维度来判断最大获胜概率是不是小于 11. 把求解这个 SDP hierarchy 的图灵机用上述间隙不变压缩技术不断压缩, 如果这个图灵机不会停机, 那么得到的 non-local game 在对易算符模型下的最大获胜概率是 11, 但是在张量积模型下的最大获胜概率不超过 1/21/2 (否则需要两个玩家之间共享无穷维纠缠).

故事就到此为止了吗? 尽管这篇文章 [2:11] 给出了张量积模型下的多方量子交互式证明 (MIP∗\sf MIP^*) 的完全刻画, 但是对易算符模型下的多方量子交互式证明 (MIPco\sf MIP^{co}) 仍然没有被完全解决 – 类似 MIP∗=RE{\sf MIP^*}={\sf RE}, 自然地猜测是MIPco=?coRE{\sf MIP^{co}}\overset{?}{=}{\sf coRE}, 这里的 coRE\sf coRE 意味着在 NO 情形下图灵机会在有限步内停机, 但是在 YES 情形下不会停机. 原因是刻画对易算符模型的多方量子交互式证明的 NPA hierarchy, 可以看成描述张量积模型的 SDP hierarchy 的"对偶".

尽管我们已经来到了 MIP∗\sf MIP^* 的终章, 但是故事还并没有结束.

参考文献

  1. Jain, Rahul, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. “Qip= pspace.” Journal of the ACM (JACM) 58, no. 6 (2011): 30. ↩︎ ↩︎ ↩︎

  2. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen: “MIP*=RE”, 2020; arXiv:2001.04383. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

  3. Junge, Marius, Miguel Navascues, Carlos Palazuelos, David Perez-Garcia, Volkher B. Scholz, and Reinhard F. Werner. “Connes’ embedding problem and Tsirelson’s problem.” Journal of Mathematical Physics 52, no. 1 (2011): 012102. ↩︎

  4. Natarajan, Anand, and Thomas Vidick. “Two-player entangled games are NP-hard.” In Proceedings of the 33rd Computational Complexity Conference, p. 20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. ↩︎ ↩︎ ↩︎ ↩︎

  5. Natarajan, Anand, and Thomas Vidick. “Low-degree testing for quantum states, and a quantum entangled games PCP for QMA.” In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 731-742. IEEE, 2018. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

  6. Ji, Zhengfeng. “Compression of quantum multi-prover interactive proofs.” In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 289-302. ACM, 2017. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

  7. Fitzsimons, Joseph, Zhengfeng Ji, Thomas Vidick, and Henry Yuen. “Quantum proof systems for iterated exponential time, and beyond.” InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 473-480. ACM, 2019. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

  8. Natarajan, Anand, and John Wright. "NEEXP in MIP."arXiv preprint arXiv:1904.05870(2019). ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

  9. Ito, Tsuyoshi, and Thomas Vidick. “A multi-prover interactive proof for NEXP sound against entangled provers.” In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 243-252. IEEE, 2012. ↩︎

  10. Bavarian, Mohammad, Thomas Vidick, and Henry Yuen. “Hardness amplification for entangled games via anchoring.” InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 303-316. ACM, 2017. ↩︎