量子 PCP 猜想浅说 (一): 当交互式证明遇上量子纠缠

准备写一个系列, 介绍一下量子 PCP 猜想^[1]以及今年被 Natarajan-Vidick 证明的 entangled game 版本^[2]. 之所以我仍然称之为猜想, 是因为 Hamiltonian qPCP 仍然是公开问题, 并且 game qPCP 和 Hamiltonian qPCP 之间的联系仍然不完全清楚.

写这个系列的起因是准备这学期某门课的 presentation, 主要参考 Thomas Vidick 在今年 UCSD 的 Spring School on Quantum Computation 上的 Lecture Notes^[3], Anand Natarajan 几天前在 Simons Institute 的报告, 以及相关的论文 (主要是^[2:1] 和 ^[4] 以及 ^[5]). 大致分为四篇:

• 第一篇介绍交互式证明系统的一系列结果, 以及当我们把量子纠缠引入交互式证明系统会发生什么.
• 第二篇介绍 entangled game (以 CHSH game 和 Magic Square game 为例), 自检测 (self-testing), 以及它们和近似群表示 (即 Gowers-Hatami 定理^[6]) 的联系.
• 第三篇介绍线性检测和指数规模的 PCP 定理的证明, 以及如何得到线性检测的量子对应.
• 第四篇介绍如何用前三篇的技术证明 (指数规模的) 交互式证明版本的量子 PCP 定理 (games qPCP), 以及如何使用纠错编码进一步设计效率更高 (多项式规模) 的极大纠缠态的自检测, 并简要介绍与 Hamiltonian qPCP 相关的内容与进展.

为了笔者的方便起见, 假定读者们知道一点量子信息 (Dirac 记号 / CHSH game / $\mathsf{BQP}$), 以及本科程度的计算复杂性理论 (知道 $\mathsf{NP}$ 的两种等价定义, 能说清楚 Cook-Levin 定理的内容, 并且能大致理解证明).

本篇的主要内容如下:

• 从 $\mathsf{NP}$ 开始介绍交互式证明的一系列结果, 包括多轮交互式证明, 多个证明者的多伦交互式证明, 以及导出的一系列概率可检测证明 (PCP), 但是不会涉及任何密码学相关 (比如零知识证明) 的结果. 解释 $\mathsf{PCP}$ 定理中概率可检查证明 (或者说局部可检测证明) 的意义, 以及 PCP 定理的其他表述形式 (与不可近似性的联系.
• 定义 $\mathsf{NP}$ 的量子对应 $\mathsf{QMA}$ 及其完全问题, 在此基础上介绍量子交互式证明系统相关的复杂性类的一系列定义 (一个证明者是 $\mathsf{QIP}$ 和多个证明者是 $\mathsf{MIP^*}$), 以及交互式证明版本的量子 PCP 猜想的定义. 然后介绍近年关于量子 PCP 猜想的几个弱化版本 (即 $\mathsf{MIP^*}$ 的下界) 的结果, 并简要介绍与 $\mathsf{MIP^*}$ 的可能上界有关的结果.

下面开始正文.

交互式证明: 从 NP 到 PCP 定理

回顾一下 $\mathsf{NP}$ 的定义, 说的是如果一个问题在 $\mathsf{NP}$ 中, 那么对于这个问题的解, 存在一个确定性多项式时间算法验证它的正确性. 换一个角度看, 对于 $\mathsf{NP}$ 中的问题, 这里有一个无所不能的证明者 (prover), 和一个计算能力受限 (确定性多项式时间) 的验证者 (verifier), 仅仅使用一次通信 (非交互式证明). 这里有几个地方可以放宽, 其一是我们可以允许验证者使用随机性, 其二是允许更多的通信次数(轮数).

因而, 把 $\mathsf{NP}$ 一般化意味着我们所讨论的证明系统从非交互式变成了交互式, 在我们的印象中满堂灌式教学效果往往不如师生大量交互的课堂 — 直觉上来说这样的交互会提高证明系统的计算能力, 但是能提高多少呢?

形形色色的交互式证明系统

考虑一个具有概率多项式时间的验证者, 允许多项式次轮通信 (一轮通信即验证者向证明者提问, 证明者给出答复), 这么这样的交互式证明对应的复杂性类是 $\mathsf{IP}$^[7][8]. 这里的"概率多项式时间"意味着, 如果证明是对的, 那么证明者以极高的概率 (比如 $2/3$) 接受, 称为完备性 (completeness); 否则, 证明者以极低的概率 (比如 $1/3$) 接受, 称为可靠性 (soundness); 我们可以用诸如 Chernoff bound 之类的 concentration inequality 通过多次运行交互式证明使得接受 (或拒绝) 的概率任意接近$1$ (或$0$).

于是使用代数化 (arithmetization) 和 sum-check protocol (即通过多轮交互迫使证明者不断说谎, 直到圆谎超出他的能力范围), 人们惊奇地发现 $\mathsf{P}^{\mathsf{\#P}} \subseteq \mathsf{IP}$^[9]; 对这里的代数化技术稍加改进, 则可以进一步证明 $\mathsf{IP}=\mathsf{PSPACE}$^[10] – 这样的交互式证明的计算能力竟然和多项式空间一样!

那么如果我们有不止一个证明者呢? 可以证明多个证明者的情况和两个证明者等价^[11], 并且多轮交互和单次交互的计算能力等价, 于是这样的多证明者交互式证明系统对应的复杂性类是 $\mathsf{MIP}(f(n),c,s)$, 其中 $f(n)$ 是交互者和证明者之间的通信代价 (即不能发送超过 $f(n)$ 的信息), $c$ 和 $s$ 分别是完备性 (completeness) 和可靠性 (soundness). 九十年代初的一系列结果证明了 $\mathsf{NEXP} =\mathsf{PCP}(poly(n),poly(n))=\mathsf{MIP}(poly(n),1,1/2)$^[12]], 也就是允许多项式规模通信多证明者交互式证明系统的计算能力和非确定性指数时间相同. 这里的 $\mathsf{PCP}(f(n),g(n))$ 是指在概率可检查证明中, 验证者向证明者提问的长度是 $f( n)$, 证明者给出的答案的长度是 $g(n)$, 比如说验证者问"证明"的 753-755 行是什么, 证明者给出"证明"中对应的部分. 这一系列结果使人们逐渐意识到, 交互式证明的力量比他们想象中要大得多, 关于交互式证明的系列奠基性工作荣获 1993 年的 Gödel Prize (理论计算机科学最高论文奖).

九十年代中期, 大家开始考虑如果限制这样的多证明者交互式证明系统的通信代价会发生什么, Arora 和 Safra 在 1992 年成功地把上述结果两边"取了对数"^[13] – 他们证明了 $\mathsf{NP} = \mathsf{MIP}(\log n, 1, 1-\epsilon) = \mathsf{PCP}(\log n,\log n)$. 几个月后, Arora-Lund-Motwani-Sudan-Szegedy 将这一结果进一步改进到 $\mathsf{NP}=\mathsf{PCP}(\log n, 1)$^[14], 这一结果后来被称为 PCP 定理. 当然, 这一定理的历史地位, 很大程度上与后来建立的与不可近似性 (hardness of approximation) 的联系^[15]有关, PCP 定理的建立及其与不可近似性的联系分别荣获 2001 和 2011 年的 Gödel Prize.

PCP 定理的等价描述

这里对 PCP 定理的名字稍微废话几句. PCP 定理说的是概率可检查证明 (probabilistic checkable proofs), 说的是所有$\mathsf{NP}$ 中的语言都有多项式规模的"证明", 我们可以通过某个概率多项式时间算法, 只检查"证明"中的常数个位置来验证"证明"正确与否 — 这么说从字面上是对的, 不过并不符合史实^[16]. 因为真实的原因是当年 Muli Safra 去 Berkeley 开会, 走错房间的缉毒警察来寻找毒品普斯普剂 (PCP), 其实更适合望文生义的名字是局部可检测证明 (locally testable proof).

另外, 这里对"证明"打引号的原因是, 每个证明者手上都有一份被处理过方便验证者提问的版本. 比如说对于可满足性问题 ($\mathsf{SAT}$) 某个实例的 $n$ 个变量的赋值 (即 $n$ 比特串), 为了通过检查常数个位置来判断"证明"的正确性, 我们必须对证明做一些处理 (比如使用某些性质良好的纠错编码) 使得它有某些良好性质 (比如是局部可检测的).

以上结果虽然强大, 但并不足以使得 PCP 定理在计算机复杂性理论中的地位几乎堪比 Cook-Levin 定理. 经典的 PCP 定理实际上有三种表述方式, 除了用局部可检测证明外, 也和一轮交互的多证明者的交互式证明系统等价, 等价性的证明使用交互式证明系统模拟概率可检查证明中的喻示 (oracle), 这一技术称为喻示化 (oracularization). 除此之外, PCP 定理也可以用不可近似性 (hardness of approximation)^[15:1] 来刻画, 即一些 $\mathsf{NP}\text{-complete}$ 问题的 gap 版本仍然是 $\mathsf{NP}\text{-complete}$ 的. 比如 $3\text{-}\mathsf{SAT}$, 即判断实例 $\phi$ (某类布尔表达式) 是否能被满足, 而对应的 gap 版本 $\mathsf{Gap}\text{-}3\text{-}\mathsf{SAT}$ 说的是判断实例 $\phi$ 中所有子句被满足还是仅有少于 $7/8+\epsilon$ 的子句被满足. PCP 定理和不可近似性的联系, 使得 $\mathsf{P}\neq \mathsf{NP}$ 后来成为了近似算法中证明不可近似性的主要假设之一.

当交互式证明遇上量子力学

计算机科学家开始涉足量子计算始于上世纪九十年代初, 包括广为人知的 Shor 算法和刻画量子计算机多项式时间内求解的问题的复杂性类 $\mathsf{BQP}$. 类似 $\mathsf{NP}$, Alexei Kitaev 在上世纪九十年代末定义了它的量子对应 $\mathsf{QMA}$^[17]], 即这里的验证者是一台量子计算机, 证明者和验证者之间的通信是量子态 (仅使用经典通信的复杂性类是$\mathsf{QCMA}$^[18]], 但是我们并不知道它和 $\mathsf{QMA}$ 是否等价). 这样的复杂性类的完全问题是局部哈密顿量问题 (local Hamiltonian problem), 几乎是 $\mathsf{MAX\text{-}k\text{-}SAT}$ 的直接对应:

局部哈密顿量问题 (local Hamiltonian problem)

给定哈密顿量 $H = \frac{1}{m}\sum_i H_i$, 其中 $H$ 作用在 $n$ 个量子比特上, 并且每个子项 $H_i$ 作用在 $O(1)$ 个量子比特上, 此外 $\|H_i\| \leq 1$ 且 $H$ 至多有多项式个子项. 这一问题需要判断哈密顿量的基态能量 (最小特征值) 是 $\lambda_{min}(H) \leq a$ 还是 $\lambda_{min}(H) \geq b$, 其中 $a-b \geq \Omega(1/poly(n))$. 这里的基态是最小特征值对应的特征向量.

不难看出上述问题和 $\mathsf{MAX\text{-}k\text{-}SAT}$ 的对应关系: 布尔表达式中的子句 (约束, 可以表示成对角矩阵) 对应于哈密顿量的每个子项, 计算基态能量等价于计算被违反的约束个数. 上述 $\mathsf{QMA}$ 的定义给出了仅有一个证明者的量子非交互式证明系统.

在后文我们会提到, 在量子交互式证明 (即允许多轮交互) 中, 只有量子纠缠才会带来计算能力的惊人提升, 证明者和验证者之间使用量子态通信并没有任何优势! 值得一提的是, 我们并不知道在量子非交互式证明中, 使用量子态通信能否带来计算能力提升. 常见的量子非交互式证明关于 $\mathsf{QMA}$ 的变种如下:

• 如果仅有一个证明者, 如果他和验证者的通信使用经典信息的话, 那么这样的复杂性类是 $\mathsf{QCMA}$;
• 如果有两个证明者 (多个的情况和两个等价), 但是他们之间并不允许共享纠缠态的话, 这样的复杂性类是 $\mathsf{QMA(2)}$.

至今我们仍然不知道上面两个复杂性类是否和 $\mathsf{QMA}$ 相同, 尽管根据定义我们有 $\mathsf{QCMA} \subseteq \mathsf{QMA} \subseteq \mathsf{QMA(2)}$, 但是我们并不知道后者除了 $\mathsf{NEXP}$ 以外的非平凡上界.

下面我们继续讨论允许多轮交互的情形, 这就是量子交互式证明.

量子交互式证明系统

Kitaev-Watrous 在 2000 年对 $\mathsf{QMA}$ 的定义一般化^[19], 得到了量子交互式证明系统 $\mathsf{QIP}$, 并证明了 $\mathsf{QIP(3)=QIP}$ 即三轮交互的交互式证明系统的计算能力和多项式轮相同. 如果我们禁止这里的验证者使用量子计算, 那么就会得到 $\mathsf{PSPACE}=\mathsf{IP}\subseteq \mathsf{QIP}$. 不过出乎意料的是, Jain-Ji-Upadhyay-Watrous 在 2009 年证明了$\mathsf{QIP}\subseteq \mathsf{PSPACE}$^[20], 即 $\mathsf{QIP}=\mathsf{IP}$ (STOC 2010 最佳论文奖), 即仅有一个证明者的情况下, 量子交互式证明系统没有任何优势!

那么, 如果我们有多个证明者呢? 对量子交互式证明的进一步泛化并不显然, 量子纠缠的存在使得我们有更多选择:

• 证明者之间没有量子纠缠, 但是证明者和验证者的交互使用量子态, 验证者是量子的, 这样的复杂性类记为 $\mathsf{QMIP}(poly(n),c,c-\delta)$.
• 证明者之间具有量子纠缠, 但是证明者和验证者的交互使用量子态, 验证者是量子的, 这样的复杂性类记为 $\mathsf{QMIP^*}(poly(n),c,c-\delta)$.
• 证明者之间具有量子纠缠, 但是证明者和验证者的交互使用经典通信, 验证者是经典的, 这样的复杂性类记为 $\mathsf{MIP^*}(poly(n),c,c-\delta)$.

需要说明的是, 在一些论文 (如 Rechardt-Unger-Vazirani ^[21] 中) 使用的 $\mathsf{QMIP}$ 即为这里的 $\mathsf{QMIP^*}$. 本文沿用 Thomas Vidick 在 UCSD Spring School 的 Lecture Notes^[3:1] 中使用的记号, “Q” 表示证明者和验证者之间的通信使用量子信息, “*” 则表示证明者们之间允许共享量子纠缠.

$\mathsf{QIP}=\mathsf{IP}$ 告诉我们使用量子态通信和使用量子计算验证并没有任何优势, 这样的结果同样适用于多证明者的量子交互式证明系统, 即 $\mathsf{QMIP}=\mathsf{MIP}$ 和 $\mathsf{MIP^*}(poly(n),1,1/2)=\mathsf{QMIP^*}(poly(n),1,1/2)$, 后者由 Rechardt-Unger-Vazirani 在 2013 年证明^[21:1]. 因而对于量子交互式证明而言, 似乎它在计算上可能的优势来源就是量子纠缠, 但是量子纠缠究竟能在多大程度上提升交互式证明的能力呢?

回忆一下交互式证明系统版本的 PCP 定理, 它给出的对复杂性类 $\mathsf{NP}$ 的刻画是 $\mathsf{NP} \subseteq \mathsf{MIP}(\log n,1,1/2)$ – 即如果限制多证明者的交互式证明系统能使用的通信复杂度位 $O(\log n)$ 的话, 那么它可以刻画 $\mathsf{NP}\text{-complete}$ 问题. 既然我们想要它的"量子化", 那就一方面允许非交互证明系统中的验证者使用量子计算, 另外一方面允许交互式证明系统的证明者们之间共享纠缠, 于是猜测的量子版本应该是 $\mathsf{QMA} \subseteq \mathsf{QMIP^*}(\log n,c,c-\delta)$, 这就是 Fitzsimons-Vidick 在 2014 年末^[22]给出的 Games Quantum PCP Conjecture 的定义, 其中完备性和可靠性的间隙为 $\delta$.

也就是说, 交互式证明版本的量子 PCP 猜想 (games qPCP) 可以被表述如下:

**量子 PCP 猜想的交互式证明版本 (games qPCP conjecture) **

给定共享纠缠态的多个证明者 (玩家) 的交互式证明系统 (entangled game), 以常数精度 (即 $c-s=O(1)$) 估计验证者的最大接受概率 (或者 entangled game 中玩家的最大获胜概率) 是 $\mathsf{QMA}\text{-hard}$ 的.

需要说明的是, 我们上面的叙述中没有区分 $\mathsf{QMIP^*}$ 和 $\mathsf{MIP^*}$ (即证明者和验证者的通信是否使用量子态), 这是因为 Reichardt-Unger-Vazirani ^[21:2] 和季铮锋 ^[23] 分别证明了在多项式或是对数规模的通信代价下均有 $\mathsf{QMIP^*}=\mathsf{MIP^*}$.

当交互式证明遇上量子纠缠

上面的 Games qPCP 看起来很强, 直接证明这一论断似乎并不容易. 我们可以考虑把它从证明长度, 近似的精确程度和通信代价三个方面进行弱化:

• 既然是 PCP 定理的量子版本, 那么我们大可只"量子化"右边, 即 $\mathsf{NP} \subseteq \mathsf{MIP^*}(\log n,c,c-\delta)$. 要么再不妨两边取个指数, 得到 $\mathsf{NEXP}\subseteq \mathsf{MIP^*}(poly(n),c,c-\delta)$. 这个版本说的是多证明者量子交互式证明系统的计算能力并不弱于经典交互式证明系统.
• 观察一下上面的局部哈密顿量问题, 它的基态能量的精度是逆多项式的, 那么我们自然也可以放宽 entangled game 中对获胜概率的精度要求, 即 $\mathsf{QMA} \subseteq \mathsf{MIP^*}(\log n,c,c-1/poly(n))$. 这个版本说的是多证明者量子交互式证明系统 (对数规模通信代价) 的计算能力不弱于量子非交互式证明 (多项式规模通信代价).
• 注意到右边允许的通信代价是对数规模的, 我们也可以只把右边"取个指数", 得到 $\mathsf{QMA} \subseteq \mathsf{MIP^*}(poly(n),c,c-\delta)$. 在经典 PCP 定理的系列结果中, 这里对应的是 $\mathsf{NP}\subseteq\mathsf{MIP}(poly(n),c,c-\delta)$. 这个版本给出了指数规模 PCP 定理的量子版本, 经典情形下这一定理的证明由线性检测 (linearity testing) 和二次方程可解性 (quadratic solvability) 是 $\mathsf{NP}\text{-complete}$ 给出.

事实上, 第三种弱化版本并不平凡, 尽管证明者给出的"证明" 的长度是指数的, 但是验证者只需要随机验证常数行就可以以极高的概率判断其正确性. 上面三个弱化情形几乎被完全解决:

• Ito-Vidick 在 2012 年证明^[24]了 $\mathsf{NEXP} \subseteq \mathsf{MIP^*}(poly(n),1,1-\delta)$ 和 $\mathsf{NP}\subseteq\mathsf{MIP^*}(\log n,1,1-\delta)$, 不过需要五个证明者 (FOCS 2012 最佳论文奖). 这一工作意味着多证明者的量子交互式证明并不弱于经典情形. Vidick (2013)^[25] 和 Natarajan-Vidick (2017)^[26] 分别把证明者个数减少到三个和两个.
• 季铮锋在 2015 年证明^[27]了 $\mathsf{QMA} \subseteq \mathsf{MIP^*}(\log n,c,c-1/poly(n))$, 这一工作意味着多证明者量子交互式证明并不如弱于量子非交互式证明. 如果考虑指数小的$c-s$ 间隙的话, 上述下界可以被加强^[23:1]到 $\mathsf{NEEXP} \subseteq \mathsf{MIP^*}(poly(n),1,1-2^{-n})$. 几周前, Fitzsimons-Ji-Vidick-Yuen 将这一结果进一步加强^[28]到 $\mathsf{NE^{R(n)}XP} \subseteq \mathsf{MIP^*}(poly(n),1,1-\exp(C \exp(\cdots,\exp(n))))$, 其中 $\mathsf{NE^{R(n)}XP}$ 表示非确定性 $R(n)$ 重指数时间内可判定的语言.
• Natarajan-Vidick 在 2016 年借助群表示论中的 Gowers-Hatami 定理^[6:1] 直接证明了 $\mathsf{QMA} \subseteq \mathsf{MIP^*}(poly(n),1,1-\delta)$, 这一结果给出指数规模 PCP 定理的量子版本^[4:1]. 本系列文章介绍的大部分技术均来自这篇论文. 不过如何把证明者个数从五个减少到两个仍然是公开问题, 另外需要说明的是, 这一结果可以由 $\mathsf{QMA} \subseteq \mathsf{PP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{NEXP} \subseteq \mathsf{MIP^*}(poly(n),1,1-\delta)$ 导出.

其后 Natarajan-Vidick 通过一系列改进, 在 2017 年末证明了在随机规约下 $\mathsf{QMA}\subseteq \mathsf{MIP^*}(poly\log(n),1,1-\epsilon)$, 并在 2018 年四月份进一步证明^[2:2]了在随机规约下 $\mathsf{QMA} \subseteq \mathsf{MIP^*}(\log n,1,1-\epsilon)$ , 这一结果被称 Games Quantum PCP Theorem. 至此, 多证明者交互式证明系统 (通讯代价限制在对数, 以常数精度近似获胜概率) 的下界已经有了多种不同的刻画方式, 并且在某些参数限制下几乎被完全解决.

量子纠缠的力量

自然, 另外一个问题则是 $\mathsf{MIP}^*$ 的上界, 也就是说量子纠缠的力量到底有多大? 然而我们对此一无所知.

直觉上来说我们并不知道这样的上界是什么样的, 因为我们根本不知道证明者们到底能用多少纠缠. 可能的猜测之一^[28:1]是它包括了所有可判定语言以及某些不可判定 (undeciable) 语言. 而可能的途径则是刻画可能的量子关联的可能集合, 即对于量子交互式证明系统, 给定问题,并选择合适的量子策略 (可观测量, 有可能是无穷维的) 再给出某些答案的分布的可能集合 — 这样的集合是凸的 (convex), 但是我们并不知道它们是否封闭 (closed):

• William Slofstra 在 2017 年证明^[29]了其中一类重要的量子关联的可能集合不是 closed, 这意味着判断一个 entangled game 获胜概率是否严格为 $1$ 是不可判定的!
• 如果能够证明算子代数中的 Connes Embedded Conjecture, 那么$\mathsf{MIP^*}$ 将包含所有可判定语言.

说到这里, 看起来量子纠缠的力量非常惊人: 通过把多证明者量子交互式证明系统的完备性和可靠性的间隙从常数逐渐缩小到逆多重指数, $\mathsf{MIP^*}$能够验证的语言从 $\mathsf{QMA}$ 逐渐扩大到了 $\mathsf{NE^{R(n)}XP}$; 甚至当我们把它们的间隙变得几乎无穷小的时候, $\mathsf{MIP^*}$ 包含了不可判定的语言!

目前为止, 我们仍然没有给出 $\mathsf{MIP^*}$ 的确切定义, 看起来证明者们之间共享的量子纠缠是它的计算能力的主要来源, 熟悉 Bell 不等式的读者也许会觉得这一现象很像是量子力学中的非局域性 (non-locality). 事实上由 Bell 不等式导出的 CHSH game 就是 entangled game (quantum game) 的典型例子. 而复杂性类 $\mathsf{MIP}^*$ 就是由 entangled game 所定义的^[30], 即所有的 $\mathsf{MIP}^*$ protocol 其实都是一个 entangled game, 在下一篇中我们将介绍它的严格定义及常见例子 CHSH game 和 Magic Square game.

Reference