量子 PCP 猜想浅说 (四): 量子 PCP 定理及其他

本文是关于交互式证明版本的量子 PCP 定理^[1] 和量子 PCP 猜想^[2]的系列文章的最后一篇.

在上一篇中, 我们给出了经典 PCP 定理的一些直觉, 即如何通过线性检测 (linearity testing) 等技术, 证明指数规模的 PCP 定理. 为了证明上述协议的可靠性, 我们通常可以使用 Fourier 分析的简单性质 – 如果我们从群表示论 (特征标理论) 的角度重新审视这一证明的话, 那么我们就可以用 Gowers-Hatami 定理把它推广到矩阵值函数上, 这就是交互式证明版本的量子 PCP 定理中用到的核心技术, 称为 Pauli braiding test. 它也是整个证明过程中唯一与"量子"相关的部分.

这一篇会带领读者补全指数规模量子 PCP 定理的证明过程. 首先需要解决的问题是, 我们需要什么样的 $\mathsf{QMA}\text{-complete}$ 问题, 尽管自然的选择是局部哈密顿量问题, 但是借助纠错编码分发"证明"的过程会把我们限制在某些哈密顿量上. 其次, 我们需要的量子交互式证明协议的完备性-可靠性间隙是和输入规模无关的常数, 这意味着我们必须设法把局部哈密顿量问题的精度间隙从逆多项式放大到常数 – 对于指数规模的"证明", 问题已经顺利解决; 但是当我们试图寻找更高效的"证明"的时候, 我们必须借助随机性, 简单直接的解决方式不再直接奏效. 此外, 为了得到更高效的规约过程, 我们还需要借助经典 PCP 定理证明中的一系列技术, 比如低次多项式检测 (low-degree testing) 来设计更高效的 Pauli braiding testing.

看起来到了这里这系列文章已经尘埃落定了, 可为什么标题仍然是"猜想"而非"定理"呢? 这是因为我们对哈密顿量版本的量子 PCP 猜想 (或者说 robust entanglement) 知之甚少, 这一问题早已并不局限在量子计算复杂性理论本身, 也与凝聚态物理具有深刻联系 (比如拓扑序和纠缠的不可近似性) – 尽管我们并不知道这一猜想正确与否, 如果它不是对的, 那么隐藏在这一系列令人惊讶的事实背后的深层原因又会是什么呢?

下面开始正文.

如何证明交互式证明版的量子 PCP 猜想

首先回顾一下什么是交互式证明版本的量子 PCP 猜想, 我们曾在本系列第一篇文章中给出 Fitzsimons-Vidick 的定义^[3], 在此之前量子 PCP 猜想通常指代 Hamiltonian qPCP:

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

给定共享纠缠态的多个证明者 (玩家) 的交互式证明系统 (entangled game), 并且证明者和验证者之间的只允许使用对数规模的信息通信, 那么以常数精度 (即 $c-s=O(1)$ ) 估计验证者的最大接受概率 (或者 entangled game 中玩家的最大获胜概率) 是 $\mathsf{QMA}\text{-hard}$ 的.

这里的 $\mathsf{QMA}$ 是 $\mathsf{NP}$ 的量子对应, $c-s$ 是完备性和可靠性的间隙. 此外, Fitzsimons-Vidick 讨论的上下文是证明者们和验证者之间的通信使用量子态, 后来我们知道使用量子态通信并不会在计算能力上给量子交互式证明系统帮助 (即 Reichardt-Unger-Vazirani ^[4] 证明的 $\mathsf{QMIP}=\mathsf{MIP^*}$ ), 于是自然只考虑经典信息通信, 而这正是以 CHSH game 为代表的 entangled games 所关注的上下文.

于是为了证明上述猜想, 我们需要给一个合适的 $\mathsf{QMA}\text{-complete}$ 问题设计多证明者的量子交互式证明 ( $\mathsf{MIP}^*$ ) 协议. 最为自然的备选方案当然是局部哈密顿量问题 (local Hamiltonian problem), 原因在于一方面它是可满足性问题 ( $\mathsf{SAT}$ ) 的自然对应, 而另一方面我们知道 $\mathsf{QMA}\text{-complete}$ 问题仍然不够多 — 譬如说在经典 PCP 定理的证明中, 我们使用的是布尔二次方程可解性 (quadratic solvability) 问题; 但是由于我们不知道某类关于 Pauli X 和 Z 的哈密顿量问题 (不一定是局部的) 是否是 $\mathsf{QMA}\text{-complete}$ 的, Natarajan-Vidick^[1:1] 的证明中使用的是随机规约 (randomized reduction). 需要说明的是, 这并不意味这 Natarajan-Vidick 的证明不能使用退随机化 (derandomization) 技术得到确定性规约 (deterministic reduction), 只不过他们并没有尝试过而已.

下面重新回忆一下局部哈密顿量问题的定义:

局部哈密顿量问题 (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))$ . 这里的基态是最小特征值对应的特征向量.

需要关注的是关于 $\lambda_{min}(H)$ 的精度间隙 (precision gap), 以及所需要的哈密顿量的类型 – 由于在 games qPCP 中我们需要的是和输入规模无关的完备性-可靠性间隙 $c-s$ 为常数, 那么我们需要设法进行间隙放大 (gap amplification); 此外, 由于我们并不能直接向证明者们分发"证明", 对应的"证明"分发协议也会对允许的哈密顿量作一些限制.

用纠错编码分发"证明"

鉴于我们这里讨论的是局部哈密顿量问题 (local Hamiltonian problem), 需要计算的是基态能量 – 即将哈密顿量中的项作为局部可观测量 (local observables), 然后计算这些局部可观测量的期望值, 那么用以说服验证者的"证明"自然就是哈密顿量的基态 (矩阵的最小特征值对应的特征向量).

但是如何把这样的量子态分发给多个证明者呢? 看起来这个问题不太容易. 因为一方面, 对于量子态有不可克隆定理 (No-cloning theorem), 直接分发任意量子态自然是不可行的. 而另一方面, 注意到不同的量子态事实上可以有完全相同的约化密度矩阵, 想把量子态分成多个部分从而给多个证明者也不可行. 事情似乎陷入了僵局.

回忆一下我们在什么场景才会需要直接把需要发送的信息复制很多份呢? 纠错编码! Repetition codes 就是十分简单的例子, 而在量子纠错编码的一系列理论中, 类似的对应物是 Shor 9-qubit code. 如果我们想把这一过程做的稍微高效一些, 那么在经典情形我们需要使用线性编码 (linear code), 而它的量子对应是稳定化子编码 (stabilizer code). 具体来说, 为了方便起见, 我们可以考虑稳定化子编码的生成元中只有 X 或 Z 矩阵的情形, 不难验证这样的稳定化子编码也是 CSS 编码 (Calderbank-Shor-Steane code). 形式化地说, 考虑下述 $k$ -量子比特的 CSS 编码, 对应的哈密顿量为

H=\frac{1}{m} \sum_{i=1}^m H_i, H_i = \alpha_i X(a_i) Z(b_i),

其中 $\alpha_i \in [-1,1], a_i,b_i \in \{0,1\}^n, a_i\wedge b_i = 0$ . 譬如 Steane 编码 ( $k=7$ ), 作为稳定化子编码的生成元是 $0001111$ , $0110011$ , $1010101$ , 分别写成 $X$ 和 $Z$ 的形式即 $IIIXXXX$ , $IXXIIXX$ , $XIXIXIX$ , $IIIZZZZ$ , $IZZIIZZ$ , $ZIZIZIZ$ . 如此这般把 $7$ 个物理量子比特编码成 $1$ 个逻辑量子比特, 那么对应的逻辑操作为 $1111111$ (称为 transversal operations), 即 $XXXXXXX$ 和 $ZZZZZZZ$ . 那么对于任何 $X$ 或 $Z$ 操作, 如果我们选中一个证明者, 它的行为可以被其余六个证明者模拟 (视为一个"证明者"), 譬如 $XIIIIII~\text{Enc}(|\psi\rangle) = IIXIXIX ~\text{Enc}(|\psi\rangle)$ .

上述想法来自 Fitzsimons-Vidick 提出量子 PCP 猜想的交互式证明变种的同一篇论文^[3:1], 在季铮锋证明 $\mathsf{QMA} \subseteq \mathsf{MIP^*}(c,c-\delta,1/poly(n))$ 的后续工作^[5]中被称为 stabilizer games – 由于这里考虑的是证明者和验证者之间使用经典信息通信, 在技术处理上稍有不同. 考虑生成元 $\{g_1,g_2\}=\{XX,ZZ\}$ , 不难验证对应的稳定化子态 $|\Phi\rangle=(|00\rangle+|11\rangle)/\sqrt{2}$ . 下面我们将设法联系这一纠错编码和 CHSH game. 注意到 $g_1'+g_2'=X\otimes H+Z\otimes \tilde{H}=X\otimes R(\pi/4) X+Z\otimes R(\pi/4) Z$ , 那么可以看到量子策略的优势

\langle \Phi|(I\otimes R(\pi/4)) (g_1'+g_2') (I\otimes R(\pi/4)) |\Phi\rangle = 2\sqrt{2} > 2 = \langle \Phi|g_1+g_2|\Phi\rangle.

上面的量子策略和稳定化子之间的联系在于, 选定每个生成元中的一个 Pauli 矩阵, 并作用一个 $\pi/4$ 的旋转算符. 对于任何稳定化子编码, 我们都可以使用上述技术设计协议如下:

选择稳定化子编码的一个生成元.
将其中每个位置的 (如果不是 I 的话) 的 Pauli 矩阵对应的编号发送给对应的证明者, 如果是 I 则不进行任何操作.
我们会从这些证明者收到一系列反馈比特, 对这些比特进行异或操作判断奇偶性即可.

不难验证此时的最大获胜概率和 CHSH game 相同. 此外, 我们也可以证明类似的量子态自检测的鲁棒性的结果, 即如果获胜概率和最大获胜概率非常接近的话, 那么这里的量子态和稳定化子态 (stabilizer state) 一定非常接近. 将上述分析用于 Magic Square game, 就得到了 Natarajan-Vidick ^[1:2] 中所使用的"证明"分发协议. 此外, 通过选择合适的纠错编码, 我们可以进一步减少证明者的数量, 尽管我们目前并不知道如何将证明者的数目减少到 2.

保持间隙的规约: 如何设计协议估计哈密顿量的能量

协议包括两部分, 分别以 $1/2$ 的概率随机选择:

其一是对 $7$ 个证明者进行随机划分, 选择一个特殊的证明者, 然后将其余六个证明者视为一个"证明者", 在此基础上模拟两个证明者的 Pauli braiding test.
其二是要求所有证明者根据哈密顿量测量逻辑算符 $X(a)$ 或 $Z(b)$ .

不难看出为什么这里的"证明"规模是指数的. 因为协议的第二部分需要测量所有可能的字符串, 而在第一部分的 Pauli braiding test 也做了类似的事情. 为了得到准多项式规模甚至多项式规模的"证明", 自然而然的选择就是找到更高效的局部可检测编码 (比如 Reed-Muller code) 来替代 Hadamard code.

在本文的下一部分中会对此稍作介绍, 包括具有良好性质的纠错编码, 以及远比线性检测 (linearity testing) 高效地多的低次多项式检测 (low-degree testing). Pauli braiding test 中线性检测的部分也可以被低次多项式检测替代, 并通过类似的手段分析, 这就是 Natarajan-Vidick^[1:3] 在今年的第一版 weak games qPCP 的证明中使用的技术 – 为了进一步改进参数, 他们使用了 Eli Ben-Sasson 等人提出的 PCP of Proximity 结合低次多项式检测, 这里限于篇幅和作者水平不再展开.

关于 PCP of Proximity 推荐阅读 Eli Ben-Sasson 关于 PCP 定理的讲义^[6], 同时这一技术近年来也在不同领域有一系列应用:

和比特币相关的场景, 即利用 PCP 定理的变种来完成比特币协议 (Zerocash) 中的某些验证计算.
近两年 Dinur-Khot-Kindler-Minzer-Safra 关于 Unique Games Conjecture 的弱化版本即 2-to-2 game (见说点 Unique Games Conjecture, 这一系列工作的最后一篇荣膺 FOCS 2018 最佳论文奖) 的证明中使用的 assignment test 实际上就是 PCP of Proximity, 并且和 high-dimension expander 有一系列联系 (因为 linearity testing 和 low-degree testing 的可靠性证明可以看成某种 expander).

关于局部哈密顿量问题的评注

在上文关于如何将"证明"分发给一系列证明者的讨论中, 我们用到了稳定化子编码 (stabilizer code), 具体来说是 CSS-type stabilizer code. 那么显然, 能使用这一系列基于稳定化子编码的协议的哈密顿量的局部项中仅有 X 和 Z – 幸运的是, 我们可以证明这样的局部哈密顿量对应的局部哈密顿量问题是 $\mathsf{QMA}\text{-complete}$ 的, Cubitt 和 Montarano 在 2014 年证明了关于局部哈密顿量问题 (与哈密顿量的类型相关) 的分类定理^[7].

于是, 对于指数规模的 games qPCP, 间隙放大 (gap amplification) 可以直接通过简单地张量积来完成, 即新的哈密顿量 $H'=I^{\otimes a}-(I-(H-a^{-1}I))^{\otimes a}$ , 这里的 $a$ 是某个关于 $n$ 的多项式, 使得得到的 $H'$ 对应的局部哈密顿量问题的间隙是与 $n$ 无关的常数. 因而我们得到的 $H'$ 是个非局部哈密顿量 (non-local Hamiltonian), 并且它有关于 $n$ 的指数多个局部项, 那么每一项自然可以用 $\text{poly}(n)$ 规模的字符串编码. 结合上一节中的协议, 以及上一篇中关于 Pauli braiding test 的分析, 我们可以证明指数规模的交互式证明版本的量子 PCP 定理^[8].

如果我们想证明(准)多项式规模的交互式证明版本的量子 PCP 定理呢? 我们可以用同样的间隙放大技术得到常数间隙, 但是显然哈密顿量中的每一项不能用 $\log(n)$ 规模的字符串编码. 怎么办呢? 我们需要随机性, 也就是说每次只随机选择多项式规模的哈密顿量的局部项 (local terms). 借助矩阵 Chernoff 界 (matrix Chernoff bound), 可以证明这样的新的哈密顿量以极高的概率 (with high probability) 保持原来的谱隙 (spectral gap). 这就是在 Natarajan-Vidick^[1:4] 中随机规约的来源.

那么, 如何得到确定性规约呢? Natarajan 和 Vidick 给出了两种选择.

其一是证明 Hamiltonian qPCP 的变种, 即常数精度间隙 (constant precision gap) 的没有 $Y$ 的局部哈密顿量 (Y-free local Hamiltonians) 是 $\mathsf{QMA}\text{-hard}$ . 这一问题很可能比交互式证明版本的量子 PCP 定理还困难的多, 但建立了量子 PCP 定理的两种表述间一个方向的联系.
其二是证明估计无阻挫 (frustration-free) 的非局域哈密顿量的基态能量是 $\mathsf{QMA}\text{-hard}$ 的, 其中这类哈密顿量的每一项都是广义 Pauli X 矩阵和 Z 矩阵的张量积. 然而我们对这样的哈密顿量问题的复杂性一无所知, 稀疏哈密顿量在这里也远远不够 – 我们知道可分稀疏哈密顿量问题 (separable sparse Hamiltonian problem) 是 $\mathsf{QMA(2)}\text{-complete}$ 的, 即有两个证明者而不是一个证明者, 有一些迹象表明 $\mathsf{QMA} \subseteq \mathsf{QMA(2)}$ 可能是真包含.

到此为止, 我们对交互式证明版本的量子 PCP 定理的证明的介绍告一段落. 本文的下一部分会介绍如何使用经典 PCP 定理证明中的一系列技术 (即低次多项式检测), 来改进指数规模量子 PCP 定理的协议, 并试图帮助读者建立一些直觉.

量子 PCP 定理中的"证明"规模: 从指数到多项式

写到这里, 似乎有一些必要再次回顾一下经典 PCP 定理证明的历史. 在 $\mathsf{IP}=\mathsf{PSPACE}$ 和 $\mathsf{MIP}=\mathsf{NEXP}$ 被证明之后, 人们使用后者的证明中的线性检测技术证明了指数规模 PCP 定理, 在此基础上选择更好的纠错编码 (low-degree extension) 证明了准多项式规模的 PCP 定理, 并在最后用 composition 进一步改进到了多项式规模 – 尽管这里这需要阅读证明中的常数个位置, 不过常数却是 $10^6$ .

而关于交互式证明版本的量子 PCP 定理, 既然我们已经知道了指数规模的版本应该如何证明, 那么自然的想法当然是设法把低次多项式检测融入 Pauli braiding test, 这一部分将会试着帮助读者建立一些直觉.

如何设计更高效的自检测

我们说 Pauli braiding test 是第一个鲁棒的量子态自检测协议, 这是因为这里的完备性-可靠性间隙与 $n$ 无关, 只需要询问常数个问题即可. 这是怎么做到的呢? 我们提到 $n$ 个 EPR 对的张量积在稳定化子编码 $\{X(a)\otimes X(a),Z(b)\otimes Z(b): a,b\in \mathbb{Z}_2^n\}$ 的编码空间中, 实际上 $X$ 和 $Z$ 相关的算符分别对应同样的经典纠错编码, 即 Hadamard code – 只需要询问常数个问题, 这意味着这一纠错编码是局部可检测的 (locally testable).

我们知道纠错编码通常说的是这么件事, 我们有一个长度为 $k$ 的字符串, 可以通过某种编码把它们编码成长度为 $n$ 的字符串. 此外, 由于纠错编码意味着编码前的字符串, 对应于编码后多个字符串 (即冗余), 因而我们想知道编码前两个不同的字符串"离得有多远", 这一距离记作 $d$ . 比如说对于 Hadamard code, 考虑两个仅有一位不同的 $k$ -比特串, 编码后得到的 $2^k$ 个字符串中至少有 $2^{k-1}$ 个不同, 所以 Hadamard code 可以被记作 $[2^k,k,2^{k-1}]$ 经典纠错编码.

除了距离, 还有一个重要指标是码率 (rate), 即 $k/n$ . 如果码率很小的话, 这意味着我们需要一个非常长的字符串来编码一个本来很短的串, 这样的编码方式是非常低效的 – 比如 Hadamard code. 除此之外, 在 (量子) PCP 定理系列结果的第一版证明中, 还需要用到纠错编码的另外两个重要性质 – 局部可检测性和局部可解码性, 下面稍作介绍. 这一节主要参考 Thomas Vidick 的讲义^[9].

为了方便起见, 我们暂时把讨论局限在经典 PCP 定理上. 考虑某个 $\mathsf{NP}\text{-complete}$ 问题的实例 $\phi$ , 对应的"证明" (witness) 记作 $x$ , 将编码后得到的"新证明"记作 $\Pi=(\Pi^1,\Pi^2)$ . 回忆一下第一部分中提到的二次方程可解性问题 (quadratic solvability) 的话, 把证明分别对应 $(\Pi^1)_{\alpha} = \alpha\cdot x$ 和 $(\Pi^2)_{\beta}=\beta\cdot (x\otimes x)$ , 那么我们需要对每条约束 $C_j$ 验证下式是否成立:

C_j: \alpha^{(j)}\cdot x~\oplus~\beta^{(j)}\cdot (x \otimes x) = \gamma^{(i)}.

不难看到 Hadamard code 具有下述性质:

局部可检测性 (local testability): 如果我们想验证对于某个"证明" $x$ , 编码后的"新证明"是否满足 $(\Pi^1)_{\alpha} = \alpha\cdot x$ 和 $(\Pi^2)_{\beta}=\beta\cdot (x\otimes x)$ 的话, 我们只需要对"新证明"进行常数次查询. 直觉上看, 如果纠错编码的距离 $d$ 比较大的话, 那么发现错误也就容易得多 (因为编码后有大量的"错误串"), 因而局部可检测性意味着足够大的纠错编码距离 $d$ .
局部可解码性 (local decodability): 如果我们想知道"证明" $x$ 中的某一行 $x_i$ 的话, 我们只需要对"新证明"进行常数次随机均匀分布查询即可. 对于 Hamdard code, 下述对所有 $\alpha \in \{0,1\}^n$ 成立: $$x_i = x\cdot e_i= x\cdot (e_i+\alpha)+x\cdot \alpha = (\Pi^{1)_{e_i+\alpha}+(\Pi}1)_{\alpha}.$$

在指数规模 PCP 定理的证明中, 局部可检测性意味着编码"证明"得到的"新证明"的编码过程是正确的 (尽管"证明"有可能是伪造的), 而局部可解码性意味着"新证明"是由真的"证明"编码得到的. 而在 Pauli braiding test 中, Hadamard code 的局部可检测性保证了这一自检测协议是鲁棒的 (robust), 而从另一方面它极低的码率 $k/2^k$ 意味着指数规模的证明 $2^n$ .

如果我们想找到更高效的证明的话, 那么我们有需要找到更高效地纠错编码, 即足够大的距离 $d$ 和足够高的码率 $k/n$ . 是否存在具有这些性质的纠错编码呢? 幸运的是, 我们有限域 $\mathbb{Z}_p$ 上的多元低次多项式构造的 Reed-Muller code 满足上述性质, 我们甚至能直接用它得到准多项式规模 (quasi-polynomial size) 的证明!

经典低次多项式检测

尽管 Hadamard code 是局部可检测的和局部可解码的, 但是问题在于它不是高效的. 为了得到高效且鲁棒的纠错编码, 我们需要考虑有限域上的多项式. 这一节主要参考 Irit Dinur 关于低次检测 (low-degree testing) 的讲义^[10].

考虑有限域 $\mathbb{F}_p$ ( $p$ 是足够大的素数) 上的 $k$ 次多项式 $f( x)=a_0+a_1x+\cdots+a_kx^k$ . 我们知道 $k$ 次多项式至多有 $k$ 个根, 那么依靠随机猜测找到满足 $f(x)=0$ 的 $x$ 的概率是 $k/p$ — 这是一个常数! 如果把上述从多项式系数到 $|\mathbb{F}_p|$ 个取值 (即 $f(0),\cdots,f(p-1)$ ) 的过程看成纠错编码的话, 那么这就是 Reed-Solomon code, 这一编码的距离是 $p-k+1$ . 我们很容易想到一个 $O(k)$ 通信代价的检测方式: 询问 $k+1$ 个点的取值, 构造出对应的 $f(x)$ , 然后问第 $k+2$ 个点的取值. 尽管这一编码不是局部可检测的, 但是它是高效的 — 假设证明长度为 $n$ , 如果取 $k=\log(n)$ 的话, 那么得到的证明规模不会比准多项式更糟糕! 这就是经典低次多项式检测 (low-degree testing) 依赖的主要想法, 下面我们把它变得更精巧一些.

考虑有限域 $\mathbb{F}=\mathbb{F}_p$ 上的 $m$ -变量 $d$ 次多项式, 其中 $p=\mathrm{poly}(n)$ 是一个足够大的素数, 而"证明"的长度为 $n$ , 我们需要把它变成一个"新证明". 那么这样的多元多项式是 $f_d: \mathbb{F}^m \rightarrow \mathbb{F}\in\mathbb{F}_d[x_1,\cdots,x_m]$ , 即 $f(x) = \sum_{i_1,\cdots,i_m} c_{i_1,\cdots,i_m} x_1^{i_1}\cdots x_m^{i_m},$ 编码后得到其中 $f$ 的次数为 $\mathrm{deg}(f)=\max\{i_1+\cdots+i_m\}$ 且对应项的系数 $c_{i_1,\cdots,i_m} \neq 0$ , 比如说 $\deg(x_1^3x_2^7)=10$ . 那么次数不超过 $d$ 的 $m$ 变量多项式中可能有多少项呢? 通过简单的计数可以得到 $\binom{d+m}{d}$ , 这也是线性空间 $\mathbb{F}_d[x_1,\cdots,x_m]$ 中所有的基. 于是 Reed-Muller code 就是把上述多元多项式 $\mathbb{F}^{\binom{d+m}{d}}$ 编码到 $\mathbb{F}^m$ (所有可能的取值), 如果考虑多元多项式 $f$ 的话, 那么编码后的集合就是 $\{f(x): x\in\mathbb{F}^m\}$ .

由于我们想把"新证明"的规模从指数降到多项式, 那么需要把 Reed-Muller code 中的多项式次数限制为 $d = O(\log n)$ . 于是 $n=\binom{m+d}{d}=\binom{m+d}{m}\approx m^m$ , 也就是说取 $m=O(\log n/\log\log n)$ . 由 Schwarz-Zippel 定理可知, 有限域 $\mathbb{F}_p$ 上的 $m$ 变量 $d$ 次多项式至多有 $dp^{m-1}$ 个根, 类似地, Reed-Muller code 的距离为 $p^m-dp^{m-1}$ , 也就是说它的距离足够大.

为什么我们要考虑 Reed-Muller code 呢? 因为它吸收了 Reed-Solomon code 和 Hadamard code 的长处, 通过选择合适的参数, 我们甚至可以直接得到这两种纠错编码:

Reed-Solomon code: 只考虑一个变量, 即 $m=1$ , $d=k$ , $|\mathbb{F}|=n$ .
Hadamard code: $d=1$ , $\mathbb{F}=2$ , 也就是说只考虑线性的比特串.

下面说说为什么是低次多项式. 为了让 Reed-Muller code 变得局部可检测性, 我们希望编码空间中只有很小的一部分是从"证明"中得到的. 考虑一个更小的有限域 $\mathbb{F}_q$ , 其中素数 $q\approx \log(n)$ 使得 $|\{0,\cdots,q-1\}|^m=q^m > n$ . 再由从 $\{1,\cdots,n\}$ 到 $\{0,\cdots,q-1\}^m$ 的任意单射 $\tau$ , 定义函数 $\tilde{f}: \mathbb{F}_q^m\rightarrow \mathbb{R}$ 使得 $\tilde{f}(\tau(k))=x_k,~\forall k\in\{1,\cdots,n\}$ . 考虑注意到 $q=\log(n) < \mathrm{poly}(n) = p$ , 即 $f$ 是定义在 $\mathbb{F}_p^m$ 上的, 我们可以把 $\tilde{f}$ 扩展到 $f$ (称为低次扩展, low-degree extension), 并且每个变量的次数至多为 $q$ , 那么低次扩展后的新多项式的总次数 $d \leq qm= \mathrm{poly}\log(n)$ .

Reed-Muller code 就是把低次扩展后的 $f$ 看做 $x$ 的编码, 完全描述 $f$ 需要 $p^m=\mathrm{poly}(n)^{\log(n)}=2^{\mathrm{poly}\log(n)}$ 个值, 也就是我们用 Reed-Muller 编码得到了准多项式 (quasi-polynomial) 规模的"新证明"! 尽管这一结果可以被进一步改进到多项式规模, 但是它已经远远好于 Hadamard code 的指数规模"新证明".

那么这样的 $f$ 是否是局部可检测性和局部可解码性的呢? 一个自然的想法是点-线检测 (point-vs-line test), 考虑任何多项式 (线) $\ell \subset \mathbb{F}_p^m$ , 然后询问 $f$ 上的 $d+1$ 个点的值. 如果 $\mathrm{deg}(f)=d$ , 那么任何线上的 $f_{|\ell}$ 的次数至多是 $d$ , $d+1$ 个点的值足够恢复单变量多项式 $f_{|\ell}$ . 然后我们可以再询问 $f$ 上第 $d+2$ 个点的值, 检查它是否跟用前 $d+1$ 个点的值得到的多项式相同.

问题在于查询次数 $d+2 = O(\mathrm{poly}\log(n))$ 太多了, 我们需要一个只需要常数次询问的纠错编码. 解决方案是增加更多冗余: 为了列出 $f$ 所有可能的值, "新证明"会列出所有的 $f_{|\ell}$ ( $\ell$ 是对应的线). 也就是说编码后的"新证明"形如 $\Pi = (\Pi^1, \Pi^2)$ , 其中 $\Pi^1\in(\mathbb{F}_p)^{p^m}$ 使得 $(\Pi^1)_x=f(x)$ , $\Pi^2\in(\mathbb{F}_p)^{(p^m)^2}$ 使得 $(\Pi^2)_{\ell}=f_{|\ell}$ . 现在的"新证明"仍然是准多项式规模的, 对应的测试如下:

局部可检测性: 随机选择一条线 $\ell\in \mathbb{F}_p^m$ 和一个点 $x \in \ell$ , 检查 $(\Pi^1)_x=((\Pi^2)_{|\ell})(x)$ 是否成立.
局部可解码性: 给定我们所知的 $f(x)$ 上的点 $z$ , 随机选择一条线 $\ell\in\mathbb{F}_p^m$ 使得 $z\in\ell$ , 询问 $(\Pi^2)_{\ell}$ 并用它恢复 $f(z)$ .

这就是我们想要的低次检测 (low-degree testing), 叙述如下:

(低次检测定理) 存在常数 $\delta,\gamma,\gamma'$ 使得函数 $f: \mathbb{F}^m \rightarrow \mathbb{F}$ (用一个表格描述) 和次数 $d\leq \delta|\mathbb{F}|$ , 我们有关于论题 $\mathrm{deg}(f) \leq d$ 的概率验证协议. 验证者可以查询 $f$ , 对应的"新证明"满足下述条件:

完备性 (completeness): 如果 $\mathrm{deg}(f) \leq d$ , 那么"新证明"总会被验证者接受.

可靠性 (soundness): 如果 $(1-\gamma)d \leq \deg(f) \leq (1+\gamma) d$ , 那么对于任何"新证明", 它被验证者拒绝的概率至少是 $\gamma'$ .

验证者使用 $O(\log(|\mathbb{F}|^m))$ 个随机比特, 它对 $f$ 查询了 $|\mathbb{F}|^{O(1)}$ 次.

为了将上述过程变得更高效, 我们不仅可以考虑线-点测试, 还可以考虑面-点测试, 进一步介绍见 Dana Moshkovitz 关于低次检测 (low-degree testing) 的讲义^[11].

上述低次检测协议的通信代价仍然是准多项式规模的, 为了进一步降到多项式规模, 我们必须在设计协议时更加精细 – 在第一代经典 PCP 定理的证明中, 从 $\mathsf{NP} \subseteq \mathsf{MIP}(\mathrm{poly}\log(n),c,c-\delta)$ 到 $\mathsf{NP} \subseteq \mathsf{MIP}(\log(n),c,c-\delta)$ 中用到的技术是 composition, 我们需要以某种方式迭代地使用低次检测协议, 这里不再展开.

当然, 如果想把上述低次检测用在量子交互式证明系统中, 我们还需要证明这样的检测协议的可靠性对量子证明者仍然是有效的. 类似上面的 BLR 线性检测和量子线性检测的关系, 我们需要设计低次检测的矩阵值函数版本, 然后用 Gowers-Hatami 定理证明检测协议的可靠性 – 这就是给出二次方程可解性 (quadratic solvability) 这一 $\mathsf{NP}\text{-complete}$ 问题的两证明者 $\mathsf{MIP^*}(\log(n),c,c-\delta)$ 协议的 Natarajan-Vidick^[12] 中的主要技术, 也被用于证明量子交互式证明版本的量子 PCP 定理^[1:5].

重新思考交互式证明和 PCP 定理

从某种角度说, 这一系列文章介绍的 games qPCP 的证明其实是"半经典"的 – 除了 Gowers-Hatami 定理导出的一系列 entangled games 的 self-testing 的鲁棒性 (即rigidity) 的结果, 所有技术均来自经典 PCP 定理的证明中所用的技术, 诸如线性检测和低次多项式检测.

那么是否可能用其他的技术来给出证明呢? 比如用迹 (trace) 和延迟选择 (post-selection) 来替代 sum-check protocol, 进而给出 $\mathsf{P}^{\mathsf{\#P}}=\mathsf{P}^{\mathsf{PostBQP}}\subseteq \mathsf{IP}$ 的新证明^[13].

这件事情应该怎么理解呢? 封闭系统的量子力学要求演化算符必须是酉矩阵, 也就是说我们考虑的一系列量子复杂性类, 诸如 $\mathsf{BQP}$ , $\mathsf{QMA}$ , 其实都是矩阵值复杂性类 (matrix-valued complexity classes), 并且这里的矩阵是酉矩阵. 而可以证明, 允许延迟选择后得到的 $\mathsf{PostBQP}$ 其实是线性矩阵对应的矩阵值复杂性类. 从另一方面看, sum-check protocol 是证明 $\mathsf{IP}=\mathsf{PSPACE}$ 的核心技术, 那么上述量子启发的 $\mathsf{\#P}$ 的交互式证明协议是否能拓展到整个 $\mathsf{PSPACE}$ 呢?

关于延迟选择的另外两个有趣结果是 $\mathsf{PostQMA}=\mathsf{PreciseQMA}=\mathsf{PSPACE}$ 和 $\mathsf{PostQMA(2)}=\mathsf{NEXP}$ , 上述复杂性类的等价性直到两年前才被完全建立. 如果我们设法联系交互式证明系统来理解这些事实的话, 就会发现 $\mathsf{PostQMA}=\mathsf{IP}$ 和 $\mathsf{PostQMA(2)}=\mathsf{MIP}$ , 也就是说延迟选择似乎可以帮助我们把多项式轮的经典通信应答过程压缩到一个量子态里, 再通过延迟选择测量来提取信息. 而另一方面, 上述关于迹的技术, 意味着我们可以设法设计 $\mathsf{PostQMA}(k)$ 的交互式证明协议, 进而也许我们有机会得到一个量子启发的经典 PCP 定理的证明! 而这样的技术很可能也可以被用在 games qPCP 中, 那么我们很可能会从这样的"纯量子"证明中学到更多的东西.

关于交互式证明版本的量子 PCP 猜想和它的证明的介绍到此为止, 本文的最后一部分会简单的介绍 Hamiltonian qPCP 以及近年进展.

关于哈密顿量版的量子 PCP 猜想的只言片语

严格来说, 这个系列的标题是标题党, 因为和经典 PCP 定理的不可近似性 (hardness of approximation) 不同, 目前为止仍然没人建立能导出关于量子纠缠的不可近似性的量子 PCP 定理:

不仅仅计算基态 (ground state) 对于量子计算机是困难的, 计算低能态 (low-energy state) 对于量子计算机也是困难的, 即所谓"高温"情形下的 hardness result. 这里的困难指形式化之后的问题是 QMA-hard 的, QMA 相当于量子 NP.

下面我试着对 Hamiltonian qPCP 做一些简单的介绍, 包括 NLTS 猜想 (robust entanglement), 以及和拓扑序等概念的联系.

量子纠缠的不可近似性和 NLTS 猜想

众所周知的是 Hamiltonian 版本的量子 PCP 猜想 (Hamiltonian qPCP) 的推论, 即 Matthew Hasting 提出的 NLTS 猜想 (No Low-energy Trivial State), 这一系列问题也称为 robust entanglement. 一个量子态是平凡态 (trivial state) 说的是这个量子态能够被常数深度量子线路从乘积态制备, 这么定义的原因有二:

一是具有全局纠缠性质 (拓扑序)的量子态不是 trivial state, 比如 Toric code 的基态;
二是凝聚态语境下量子相 (quantum phase) 的等价性用常数深度量子线路定义.

需要说明的是这里的定义和凝聚态物理中关于拓扑序的传统定义, 即基态兼并 (ground-state degeneracy) 和边缘激发 (boundary excitation) 并不相同, 这里的定义只和量子态本身有关 (唯一和哈密顿量相关的部分是, 它是某个哈密顿量的基态). 为什么需要新的定义呢? 这是因为诸如 Toric code (即 Kitaev code) 的 homological codes 的基态兼并的产生和物理系统所在的流形 (或者说表面) 的亏格数 (genus) 有关, 而球面上的 Kitaev code 具有全局纠缠 (global entanglement) 性质却没有基态兼并.

此外, 注意到不是平凡态意味着这个量子态不能被常数深度量子线路制备, 那么对于足够大的量子系统, 通过随机噪声来消除系统的纠缠的概率非常小 – 因为只有当随机噪声恰好符合这一系列量子线路才能发生. 如此说来, 似乎纠错编码也不再重要了, 因为与我们的常识相反, 足够大的量子系统的纠缠是鲁棒的! 事实并非如此, 因为尽管纠缠通常不会被消除, 但是量子态却很可能不是原来的量子态, 因而我们依然不能在没有纠错编码的情形下以此进行量子计算 – 作为对比的是拓扑量子计算, 事实上这里的物理系统本身自带了纠错编码, 这也就是为什么我们说拓扑量子计算能在"硬件层面容错"的原因.

在 2013 年关于量子 PCP 猜想的综述 ^[2:1], 最大的进展是 Eldar-Harrow 证明的 NLETS 定理 ^[14] (NTLS 猜想的弱化版本), 以及几个月前 Nirkhe-Vazirani-Yuen 的简化证明 ^[15]. 笔者并不打算展开, 不过 NLETS 定理的简化证明相较于涉及 high-dimension expander 的原始证明, 涉及的事实要简单得多 – 仅与 $k\text{-}\mathsf{LHP}$ 是 $\mathsf{QMA}\text{-complete}$ 的证明中的构造和近似纠错编码有关, 有兴趣的读者可以先看一看随机行走与 Cook-Levin 定理的“量子化” (或者关于 Feynman-Kitaev 构造的其他介绍性文章, 如 ^[16]), 然后再阅读他们的证明.

Hamiltonian qPCP 与 PCP 定理的历史

既然说到了 Hamiltonians qPCP, 那就再次重新回顾一些 PCP 定理的历史吧. 其实我们所知的经典 PCP 定理的证明技术大致分为两条线 (暂且忽略 parallel repetition theorem 相关的结果, 另外我们并不知道这一定理的 $\mathsf{MIP^*}$ 版本应该如何证明):

上世纪八十年代建立交互式证明的概念以来的一系列技术, 包括线性检测 (Hadamard code), 低次多项式检测 (Reed-Muller code), Composition, 以及后来的升级版 PCP of Proximity (或者称为 assignment test, 后被用在 DKKMS 的弱化版本 UGC 的证明里). 所证明的结果是多证明者交互式证明系统 (或者考虑概率可检查证明), 如果证明者和验证者的通信只使用对数规模的信息的话, 那么这样的交互式证明可以验证任何 $\mathsf{NP}\text{-complete}$ 问题.
2005 年 Irit Dinur 用 gap amplification 给出的新证明, 使用 expander 相关的一系列技术, 所证明的结果是某些常见 $\mathsf{NP}\text{-complete}$ 问题的 gap 版本仍然是 $\mathsf{NP}\text{-complete}$ 的. 比如说 $\text{3-}\mathsf{SAT}$ , 本来是判断所有子句都被满足, 还是并没有都被满足, gap 版本是判断超过 99% 的子句被满足还是只有不到 1% 的子句被满足. 后者看起来似乎要容易一些, 但是 PCP 定理告诉我们这是一样困难的.

和量子 PCP 猜想不同, 经典情形下 $\mathsf{NP}\text{-complete}$ 问题的概率可检查证明刻画和这些问题的 gap 版本还是 $\mathsf{NP}\text{-complete}$ 的等价性并不难证明, 因而上世纪九十年代初的交互式证明版本 PCP 定理可以直接导出不可近似性. 也就是说, 交互式证明版本的 PCP 定理证明了十多年后, 我们才知道如何直接证明哈密顿量版本的 PCP 定理.

而对于量子 PCP 猜想而言, 这两者的等价性要困难得多, 时至今日我们只知道 Hamiltonians qPCP 可以推出 games qPCP – 反过来的话, 我们则完全不知道应该如何构造 Hamiltonians. 当然, 我们现在确实知道量子交互式证明版本的量子 PCP 定理如何证明, 但是它并不能推出 Hamiltonians qPCP 的正确性, 所以这个系列仍然谓之"猜想", 而非"定理" – 量子 PCP 定理当然得说不可近似性, 而且刻画的是纠缠的不可近似性, 这一问题很可能比 games qPCP 要困难得多, 甚至可能不是正确的.

回忆一下本系列文章所提到的技术, 除了刻画有限群近似群表示的 Gowers-Hatami 定理 (2015), 其余的技术都来自经典 PCP 定理 (低秩检测的出现早在上世纪九十年代初, PCP of Proximity 在十余年前被提出). 也就是说, 在 2016 年之后我们就有了解决这一问题的所有必要的技术储备 – 那么看起来两年后有人给出证明似乎也不算离奇, 尽管这事并不容易, 但至少在那之后证明的出现只是时间问题.

可对于 Hamiltonian qPCP 却可能是完全不同的图景. 如果这一猜想是对的, 那么我们可以导出看似离奇的 robust entanglement 现象, 因为物理系统的纠缠随着系统的增大将变得愈发稳定. 而如果这一猜想是错误, 那么支配这一切令人匪夷所思的事实的深层原因会是什么呢?

Reference

[1801.03821] Low-degree testing for quantum states, and a quantum entangled games PCP for QMA ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Aharonov, Dorit, Itai Arad, and Thomas Vidick. “Guest column: the quantum PCP conjecture.” Acm sigact news 44.2 (2013): 47-79. ↩︎ ↩︎
Fitzsimons, Joseph, and Thomas Vidick. “A multiprover interactive proof system for the local Hamiltonian problem.” Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science. ACM, 2015. ↩︎ ↩︎
Reichardt, Ben W., Falk Unger, and Umesh Vazirani. “Classical command of quantum systems.” Nature 496.7446 (2013): 456. ↩︎
Ji, Zhengfeng. “Classical verification of quantum proofs.” Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. ACM, 2016. ↩︎
Lecture Notes on Probability Checkable Proofs by Eli Ben-Sasson ↩︎
Cubitt, Toby, and Ashley Montanaro. “Complexity classification of local Hamiltonian problems.” SIAM Journal on Computing45, no. 2 (2016): 268-316. ↩︎
Natarajan, Anand, and Thomas Vidick. “A quantum linearity test for robustly verifying entanglement.” In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1003-1015. ACM, 2017. ↩︎
CS286 Seminar in Computer Science: Around the quantum PCP conjecture ↩︎
67611 - Advanced Topics in Complexity: PCP Theory (Fall 2004) by Irit Dinur ↩︎
Notes on Probabilistically Checkable Proofs and Hardness of Approximation by Dana Moshkovitz ↩︎
Natarajan, Anand, and Thomas Vidick. “Two-player entangled games are NP-hard.” arXiv preprint arXiv:1710.03062 (2017). ↩︎
Aharonov, Dorit, and Ayal Green. “A Quantum inspired proof of $P^{\# P}\subseteq IP$ .” arXiv preprint arXiv:1710.09078(2017). ↩︎
Eldar, Lior, and Aram W. Harrow. “Local Hamiltonians whose ground states are hard to approximate.” Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on. IEEE, 2017. ↩︎
[1802.07419] Approximate low-weight check codes and circuit lower bounds for noisy ground states ↩︎
Aharonov, Dorit, and Tomer Naveh. “Quantum NP-a survey.” arXiv preprint quant-ph/0210077 (2002). ↩︎

Contents