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

在上一篇中, 我们以 CHSH game (Bell 不等式的交互式证明版本) 和 Magic Square game 为例介绍了 entangled games (quantum games / non-local games), 这也可以被看做 MIP∗\mathsf{MIP^*} 的协议 (protocol). Entangled game 通常用一个裁判 (验证者) 和多个玩家 (证明者) 来描述, 它们之间的通信使用经典信息, 但是玩家之间允许共享一个纠缠态. 玩家通过对手中的纠缠态 (根据问题) 进行合适的测量给出回答, 这会在不同程度上提升它们的获胜概率.

而从另一方面看, 如果玩家的获胜概率很接近最优值的话, 那么他们共享的纠缠态就很接近极大纠缠态 (如 CHSH game 和 EPR 对), 这称为量子态的自检测 (self-testing). 此外, 我们以 CHSH game 为例, 说明了极大纠缠态的自检测, 实际上测试了玩家们的量子策略 (测量算符) 是否满足非对易性. 从群表示论的观点来看, 上述自检测就是把近似表示"取整"到精确表示, 即有限群上的 Gowers-Hatami 定理.

这一篇会给出经典 PCP 定理的一些直觉, 即指数规模的 PCP 定理 NP⊆MIP(poly(n),1,1−ϵ)\mathsf{NP}\subseteq \mathsf{MIP}(poly(n),1,1-\epsilon): 也就是说我们有一个指数规模的"证明", 只通过检查常数行, 我们就能以极高的概率判断这一"证明"是否正确. 为了更高效地阅读证明, 我们需要对其编码得到"新证明", 于是要检查"新证明"是否正确编码, 以及编码前的"证明"是否是真的. 在指数规模 PCP 定理中, 我们可以用线性检测 (linearity testing) 来检查编码的正确性, 这也是性质检测 (property testing) 的早期结果之一.

那么为什么线性检测是对的呢, 或者说如何证明其可靠性? 通常可以用 Fourier 分析的简单性质可以证明, 不过我们会从群表示论 (特征标理论) 的角度来看待这一证明, 并设法联系 Gowers-Hatami 定理 – 因而线性检测可以被推广到矩阵值函数上, 进而证明推广后的 Pauli 矩阵的量子线性检测的可靠性 (soundness). 这也是交互式证明版本的量子 PCP 定理的证明中用到的关键技术之一.

下面开始正文.

线性检测和指数规模 PCP 定理

指数规模 PCP 定理

回顾一下概率可检查证明 (probabilistic checkable proofs) 定理, 它说的是对于每一个 NP\mathsf{NP} 中的语言, 我们都可以设法得到一个多项式规模的"证明" (witness), 使得我们只需要检查证明中的常数行, 就能以极高的概率判断证明是否正确. 既然这里的"证明"是多项式规模的, 那么如果我们给"证明"中每一行编号的话, 编号至少是对数规模的 – 证明这一结果并不容易, 想把前因后果讲清楚甚至可能需要一学期的课, 不过给出一些直觉倒是容易得多.

为了方便起见, 不妨假设"证明"中每一行的编号是多项式规模 poly(n)poly(n) 的, 那么这样的"证明"就是指数规模的. 尽管"证明"规模被放大到了指数, 但是结果仍然并不平凡 – 因为我们只能检查"证明"中的常数个位置!

下面给出指数规模 PCP 定理 NP⊆MIP(poly(n),1,1−ϵ)\mathsf{NP}\subseteq \mathsf{MIP}(poly(n),1,1-\epsilon) 的交互式证明版本:

指数规模 PCP 定理 对于每个语言 L∈NPL \in \mathsf{NP}, 存在一个高效地过程 x↦Vxx\mapsto V_x, 使得 VxV_x 描述 22-玩家 11-裁判交互式证明系统中的验证者. 在这一交互式证明系统中, 验证者的问题可以被多项式规模 poly(n)poly(n) 的比特串描述, 而问题的答案可以被常数 O(1)O(1) 长度比特串描述, 使得如果 x∈Lx\in L, 那么 w(Vx)≥2/3w(V_x) \geq 2/3; 否则如果 x∉Lx \notin L, 那么 w(Vx)≤1/3w(V_x) \leq 1/3, 其中 w(Vx)w(V_x) 是玩家的获胜概率.

不难验证上述版本和概率可检查证明版本等价, 可以把多项式规模的问题看成投掷 poly(n)poly(n) 次硬币来得到要检查的行号, 常数规模的回答看成只需要检查常数个位置. 如何证明这一定理呢? 显然我们需要一个合适的 NP-complete\mathsf{NP}\text{-complete} 问题, 用以设计多证明者的交互式证明协议 (protocol). 除此之外, 我们还需要对"证明"做一些处理:

  • "证明"可以被分发到多个玩家 (证明者) 手上, 并且"证明"可以很方便地按照"行号"查阅.
  • "证明"的处理 (即编码) 过程可以通过回答一系列问题验证, 确保"证明"被正确地编码.

第一个问题可以被纠错编码解决. 对于第二个问题, 我们退而求其次, 设法保证**“证明"中的大部分**被正确地编码即可. 由于这里的"行号"是多项式规模的, 而 NP\mathsf{NP} 中语言的 “证明” (witness) xx 也是多项式规模的 (比如说线性长度 nn), 那么一个简单暴力的方法, 就是把"证明"和所有可能的 nn-比特串 vv 的内积 x⋅vx \cdot v 算出来, 作为编码后的指数规模的"新证明” (πv)v∈{0,1}n=(x⋅v)v∈{0,1}n(\pi_v)_{v\in\{0,1\}^n}=(x\cdot v)_{v\in\{0,1\}^n}. 不难看出, "新证明"的每一行只有一个比特, 并且"行号"是多项式规模的.

注意到 x⋅u+x⋅v=x⋅(u+v)x\cdot u + x\cdot v=x\cdot (u+v), 也就是说这样简单暴力的编码是线性的, 那么验证"证明"是否被正确地编码, 可以通过验证编码后的"新证明"中的各项是否有线性关系成立. 如果"新证明"中的大部分都被正确地编码的话, 那么不难验证对于随机选择的"行号", 这样的线性关系会以极高的概率成立 — 这一检测过程称为线性检测 (linearity testing 或 BLR linearity test), 具体介绍暂不展开. 这一部分主要参考 Thomas Vidick 的讲义[3]中与指数规模经典 PCP 定理相关的部分.

再说几句这里用到的 NP-complete\mathsf{NP}\text{-complete} 问题, 即判定布尔变量的二次方程组的可解性 (Quadratic Solvability 或 Quadratic Equations). 这一问题表述如下:

布尔二次方程组可解性问题 (QS) 的实例 ψ\psi 由 nn 个布尔变量 xix_i 上的 mm 个约束给出:

Cj:∑iαi(j)xi+∑i,kβi,k(j)xixk≡r(j) over Z2,C_j: \sum_i\alpha_i^{(j)}x_i+\sum_{i,k}\beta^{(j)}_{i,k} x_ix_k \equiv r^{(j)}\text{ over }\mathbb{Z}_2,

或者等价地描述为 α(j)⋅x+β(j)⋅(x⊗x)≡r(j) mod 2\alpha^{(j)}\cdot x+\beta^{(j)} \cdot (x\otimes x) \equiv r^{(j)}\text{ mod }2, 其中 α(j)\alpha^{(j)} 和 xx 为 nn-比特串, β(j)\beta^{(j)} 为 n2n^2-比特串, r(j)∈{0,1}r^{(j)}\in\{0,1\}. 那么 ψ∈QS\psi\in\mathsf{QS} 当且仅当存在一个赋值 xx 满足所有约束.

这一问题的"证明"可以被概率可检查证明验证, 考虑均匀随机选择的系数 a=(ai)i=1,⋯,m∈{0,1}a=(a_i)_{i=1,\cdots,m} \in\{0,1\}, 那么有

E(a):∑jaj(α(j)⋅x+β(j)⋅(x⊗x))=∑jajγ(j).E(a) : \sum_j a_j (\alpha^{(j)}\cdot x+\beta^{(j)}\cdot (x\otimes x)) = \sum_j a_j \gamma^{(j)}.

显然, xx 满足所有约束时, 当且仅当 xx 满足 E(a)E(a), 这给出了完备性 (completeness). 而当 xx 没有满足所有约束时, 当且仅当 xx 满足 E(a)E(a) 的概率 ≤1/2\leq 1/2, 这是可靠性 (soundness). 后者不难看做原有约束 ej:=α(j)⋅x+β(j)⋅(x⊗x)−γ(j)e_j:={\alpha}^{(j)}\cdot x+\beta^{(j)} \cdot (x \otimes x) - \gamma^{(j)} 对应的向量和 aja_j 对应的向量的内积, 前者不被满足而后者以均匀分布随机猜测, 那么两者内积 ∑jejaj=0\sum_j e_j a_j=0 的概率不会好于直接瞎猜 (即 1/21/2).

使用我们在上一段提到的简单暴力编码, 不难给出"新证明" (Π1)α=α⋅x(\Pi^1)_{\alpha}=\alpha\cdot x 和 (Π2)β=β(x⊗x)(\Pi^2)_{\beta} = \beta (x\otimes x), 只需要验证 (Π1)α+(Π2)β=?γ(\Pi^1)_{\alpha}+(\Pi^2)_{\beta} \overset{?}{=}\gamma 是否成立即可. 这样的"简单暴力编码"通常被称为 (Walsh-)Hadamard code, 为了验证"新证明"的编码是否正确, 我们需要检查编码后的"新证明"的各行之间线性关系是否近似成立, 这就引出了线性检测.

此外, 我们在第一篇中提及了经典 PCP 定理与不可近似性有关, 其实我们也可以证明上述问题的 gap 版本仍然是 NP-hard\mathsf{NP}\text{-hard} 的, 下面简单说几句. 证明布尔变量的二次方程组的可解性是 NP-complete\mathsf{NP}\text{-complete} 中主要使用的技术是代数化 (arithmetization), 即设法把每个 3-SAT3\text{-}\mathsf{SAT} 实例 (布尔表达式) 都对应到一个布尔变量二次函数上, 那么布尔表达式的可满足性对应于布尔变量二次函数可解性.

对这一证明稍作修改可以证明它的 gap 版本, 即区分布尔变量二次方程组中所有等式被满足, 还是只有不超过 ε\varepsilon 的等式被满足, 仍然是 NP-hard\mathsf{NP}\text{-hard} 的. 证明的关键技术在于, 利用纠错编码 (如 Reed-Solomon code) 从方程组可解 (白色) 和方程组不可解 (黑色) 中撕扯出一块灰色地带 (gap) — 方程组中只有占比 (ε,1)(\varepsilon,1) 的等式被满足, gap-QS\mathrm{gap}\text{-}\mathrm{QS} 保证输入中这样的实例不存在. 尽管证明多项式规模的 PCP 定理 (gap 版本) 做的是类似的事情, 但是撕扯出灰色地带要用到的技术则复杂得多.

线性检测与近似群表示

所谓 Blum-Luby-Rubinfeld 线性检测说的是如何检测某个函数否几乎是线性的, 也就是说对于随机选取的 α,α′∈{0,1}n\alpha,\alpha'\in\{0,1\}^n, 检测线性性质 g(α)+g(α′)=g(α+α′)g(\alpha)+g(\alpha')=g(\alpha+\alpha') 是否几乎总是成立, 即

BLR 线性检测定理 给定"新证明" Π∈{0,1}2n\Pi\in\{0,1\}^{2^n}, 使得对于所有 u,v∈{0,1}nu,v\in\{0,1\}^n, Πu+Πv=Πu+vmod2\Pi_u+\Pi_v=\Pi_{u+v} \mod 2 成立的概率 ≥1−ϵ\geq 1-\epsilon. 那么, 存在"证明" x∈{0,1}nx \in \{0,1\}^n 使得对于所有均匀随机选取的 vv, Πv=v⋅x\Pi_v=v\cdot x 成立的概率 ≥1−O(ϵ)\geq 1-O(\epsilon).

回忆一下上一篇中提到的量子态的自检测 (self-testing): 如果 CHSH game 的获胜概率几乎是最优获胜概率的话, 那么玩家们共享的量子态几乎是极大纠缠态. 这一 entangled game 的 rigidity 可以通过 Gowers-Hatami 定理证明, 即通过 Weyl-Heisenberg 群的近似群表示导出它的精确群表示. 这一思路其实同样适用于线性检测的证明, 实质上和常见的 Fourier 分析版本的证明如出一辙 (需要说明的是, 这一证明跟用到 majority decoding / expander 的证明不同, 见 Irit Dinur 的讲义).

通常情况下 Fourier 分析讨论的是线性函数 f:{0,1}n→{±1}f:\{0,1\}^n\rightarrow \{\pm 1\} 构成的线性空间. 这里对**“线性函数”**一词稍作说明, 为了偏于后文联系群表示, 这里的线性函数是说 ff 的指数部分是线性的 (以 −1-1 为底), 即考虑线性函数 g(x)g(x),

f(x)f(y)=(−1)g(x)(−1)g(y)=(−1)g(x)⊕g(y)=(−1)g(x⊕y)=f(x⊕y), ∀x,y∈{0,1}n.f(x)f(y)=(-1)^{g(x)}(-1)^{g(y)}=(-1)^{g(x)\oplus g(y)}=(-1)^{g(x\oplus y)}=f(x\oplus y),~\forall x,y\in\{0,1\}^n.

可以验证上面的线性函数具有下述性质:

  • 内积被定义为 ⟨f,g⟩=Ex∈{0,1}nf(x)g(x)=12n∑x∈{0,1}nf(x)g(x)\langle f,g\rangle = \mathbb{E}_{x\in\{0,1\}^n} f(x)g(x)=\frac{1}{2^n}\sum_{x\in\{0,1\}^n}f(x)g(x).
  • χr(x):=(−1)r⋅x\chi_{r}(x):=(-1)^{r \cdot x} 是上述线性空间的一组标准正交基, 其中 r,x∈{0,1}n{r},{x}\in\{0,1\}^n.
  • Fourier 变换 f(x)=∑r∈{0,1}nf^(r)⋅(−1)r⋅xf(x) = \sum_{r\in\{0,1\}^n} \hat{f}(r)\cdot (-1)^{r\cdot x}, 其中 Fourier 系数 f^(r)=Ex∈{0,1}nf(r)⋅(−1)r⋅x=⟨f,χr⟩\hat{f}(r)=\mathbb{E}_{x\in\{0,1\}^n} f(r)\cdot (-1)^{r \cdot x }= \langle f,\chi_{r}\rangle.

因而, 使用上述 Fourier 分析的语言, 线性检测定理可以重述如下:

BLR 线性检测定理 考虑布尔函数 f:{0,1}n→{±1}f:\{0,1\}^n \rightarrow \{\pm 1\}, 如果它满足 Ex,y∈{0,1}nI[f(x)f(y)=f(x⊕y)]≥1−ϵ\mathbb{E}_{x,y\in \{0,1\}^n} I[f(x)f(y) = f(x \oplus y)] \geq 1-\epsilon, 那么存在 u∈{0,1}nu\in\{0,1\}^n 使得 Ex∈{0,1}nI[f(x)=(−1)u⋅x]≥1−ϵ\mathbb{E}_{x\in\{0,1\}^n} I[f(x)=(-1)^{u\cdot x}] \geq 1-\epsilon.

上面的 I[⋅]I[\cdot] 表示 indicator, 即 I[⋅]=1I[\cdot]=1如果事件成立, 否则 I[⋅]=0I[\cdot]=0. 这一定理的证明并不复杂, 只需要用上述性质做一些简单的推导. 注意到如果f(x)f(y)=f(x⊕y)f(x)f(y)=f(x\oplus y), 那么 f(x)f(y)f(x⊕y)=1f(x)f(y)f(x\oplus y) = 1, 反之 f(x)f(y)f(x⊕y)=−1f(x)f(y)f(x\oplus y) = -1. 于是我们可以用 f(x)f(y)f(x⊕y)f(x)f(y)f(x\oplus y) 来替代 f(x)f(y)=f(x⊕y)f(x)f(y)=f(x\oplus y), 具体证明如下:

1−2ϵ≤Ex,y∈{0,1}nf(x)f(y)f(x⊕y)=Ex,y(∑sf^(s)χs(x))(∑tf^(t)χt(y))(∑uf^(u)χu(x⊕y))(Fourier 变换)=Ex,y∑s,t,uf^(s)f^(t)f^(u)χs(x)χt(y)χu(x)χu(y)(线性)=∑s,t,uf^(s)f^(t)f^(u)Ex∈{0,1}n(χs(x)χu(x))Ey∈{0,1}n(χt(y)χu(y))=∑s,t,uf^(s)f^(t)f^(u)⟨χs,χu⟩⟨χt,χu⟩(内积)=∑uf^(u)3≤max⁡wf^(w)∑uf^(u)2(Parseval 恒等式)=max⁡wf^(w)=f^(s0)\begin{aligned} 1-2\epsilon &\leq \mathop{\mathbb{E}}_{x,y\in \{0,1\}^n} f(x)f(y)f(x \oplus y) \\ &= \mathop{\mathbb{E}}_{x,y} \left(\sum_{s} \hat{f}(s) \chi_s(x) \right) \left(\sum_{t} \hat{f}(t) \chi_t(y) \right) \left(\sum_{u} \hat{f}(u) \chi_u(x\oplus y) \right) & (\text{Fourier 变换})\\ &= \mathop{\mathbb{E}}_{x,y} \sum_{s,t,u} \hat{f}(s)\hat{f}(t)\hat{f}(u)\chi_s(x)\chi_t(y)\chi_u(x)\chi_u(y) & (\text{线性}) \\ &= \sum_{s,t,u} \hat{f}(s)\hat{f}(t)\hat{f}(u) \mathop{\mathbb{E}}_{x\in \{0,1\}^n} \left(\chi_s(x)\chi_u(x)\right) \mathop{\mathbb{E}}_{y\in \{0,1\}^n} (\chi_t(y) \chi_u(y)) \\ &= \sum_{s,t,u} \hat{f}(s)\hat{f}(t)\hat{f}(u) \langle \chi_s,\chi_u\rangle \langle \chi_t,\chi_u\rangle & (\text{内积})\\&= \sum_{u} \hat{f}(u)^3 \leq \max_w \hat{f}(w) \sum_u \hat{f}(u)^2 & (\text{Parseval 恒等式})\\ &= \max_w \hat{f}(w) = \hat{f}(s_0)\\ \end{aligned}

最后一行中 s0=argmaxsf^(s)∈{0,1}ns_0=\mathop{\mathrm{argmax}}_s \hat{f}(s) \in \{0,1\}^n. 因为 f^(s0)=Ex[f(s0)χs0(x)]\hat{f}(s_0) =\mathbb{E}_x [f(s_0)\chi_{s_0} (x)], 所以 ExI[f(s0)=χs0(x)]≥1−ϵ\mathbb{E}_xI[f(s_0) = \chi_{s_0}(x)] \geq 1-\epsilon. 注意到 χs0(x)=(−1)s0⋅x=(−1)gx(s0)=f(s0)\chi_{s_0}(x)=(-1)^{s_0\cdot x}=(-1)^{g_x(s_0)}=f(s_0), 由于 s0⋅xs_0\cdot x 是线性的, 从而我们知道 f(x)f(x) 是线性函数 (按照 Fourier 分析中的定义). 从而给出了线性检测定理的可靠性 (soundness) 证明. 这一定理的完备性 (completeness) 对于 ff 是线性函数的情况是显然的, 不再赘述.

为了对上面的线性检测定理做进一步的推广, 我们需要介绍一点有限群表示论.

不妨对上面的 Fourier 分析的性质做一些观察, 注意到如果 x,y∈{0,1}nx,y \in \{0,1\}^n, 那么 x⊕y∈{0,1}nx\oplus y \in \{0,1\}^n, 即对按位模二加法封闭. 此外显然 0∈{0,1}n\mathbf{0}\in\{0,1\}^n, 并且对于任何 xx, 我们可以找到 xˉ\bar{x} 使得 x+xˉ=0x+\bar{x}=\mathbb{0}. 也就是说, 这里讨论的实际上是 Z2n\mathbb{Z}_2^n 上的加法群. 自然地, 我们也可以考虑它的表示 ff, 即 ff 满足同态关系 f(x)f(y)=f(xy)f(x)f(y)=f(xy) – 由于我们讨论的是 Z2n\mathbb{Z}_2^n 上的加法群, 因而 xyxy 其实就是 x⊕yx\oplus y. 那么如何刻画它的表示呢?

由于我们考虑得是有限交换群 (finite Abelian group), 我们可以用 Schur 引理证明它的表示维度是 11, 即它的表示对应所有线性函数 f:{0,1}n→Cf:\{0,1\}^n\rightarrow \mathbb{C} 构成的线性空间. 特征标 (character) 理论可以刻画有限群的表示, 比如说对于 Z2n\mathbb{Z}_2^n, 我们知道 χr(x):=(−1)r⋅x\chi_{r}(x):=(-1)^{r\cdot x} 是它的特征标. 不过对于一般的 (非交换) 有限群 GG, 它的特征标和表示通常并不一样:

  • 有限群 GG 的表示和分别为 ρ:G→GL(V)\rho: G \rightarrow \mathrm{GL}(V), VV 是 F\mathbb{F} 上的线性空间.
  • 有限群 GG 的特征标是 χρ:G→F\chi_{\rho}: G \rightarrow \mathbb{F}, 并且 ∀g∈G,χρ(g)=Tr(ρ(g))\forall g \in G, \chi_{\rho}(g)=\mathrm{Tr}(\rho(g)), 即特征标是表示取迹 (trace).

特征标理论可以用来刻画不同的有限群, 即以群元共轭类为行, 特征标为列的特征标表, 满足下述性质:

  • 列正交性: 对于所有非平凡特征标 χ\chi, ∑a∈Gχ(a)=0\sum_{a\in G} \chi(a) = 0.
  • 行正交性: 对于所有不同特征标 χ1,χ2:G→C\chi_1,\chi_2: G \rightarrow \mathbb{C}, 满足正交关系 ⟨χ1,χ2⟩=0\langle\chi_1,\chi_2\rangle = 0, 其中内积定义为 ⟨f,g⟩=1∣G∣∑a∈Gf(a)g∗(a)\langle f,g\rangle = \frac{1}{|G|} \sum_{a\in G} f(a)g^*(a).

上面的列正交性意味着对于有限交换群 GG, 它的特征标个数为 ∣G∣|G|. 而行正交性意味着特征标构成了线性空间 VV 的一组正交基, 也就是为什么上文中 Z2n\mathbb{Z}_2^n 上的线性函数的标准正交基恰巧是特征标 (由于有限交换群的表示维度为 11). 回顾一下上面的线性检测定理, 注意到条件和结论分别对应下述两式:

Ex,y[∥f(x)f(y)−f(x⊕y)∥2]≤Ex,yI[f(x)f(y)≠f(x⊕y)]≤ϵ,Ex[∥f(x)−χs0(x)∥2]≤ExI[f(x)≠χs0(x)]≤ϵ.\begin{aligned}\mathbb{E}_{x,y} [\|f(x)f(y)-f(x\oplus y)\|_2] & \leq \mathbb{E}_{x,y} I[f(x)f(y) \neq f(x \oplus y)] \leq \epsilon,\\\mathbb{E}_x[\|f(x)-\chi_{s_0}(x)\|_2] &\leq \mathbb{E}_x I[f(x) \neq \chi_{s_0}(x)] \leq \epsilon.\\\end{aligned}

第一个式子说的是 ff 近似满足群 Z2n\mathbb{Z}_2^n 的线性性质 (或称关系), 即它是近似群表示. 第二个式子则说 ff 可以被"取整"到一个精确群表示. 看起来似乎很眼熟, 回忆一下上一篇中介绍的 Gowers-Hatami 定理:

考虑有限群 GG 和 Hilbert 空间 HA⊗HB\mathcal{H}_A\otimes \mathcal{H}_B上的量子态 ρ\rho, 假定 f:G→U(HA)f:G\rightarrow \mathrm{U}(\mathcal{H}_A) 是一个关于 ρ\rho 的 ϵ\epsilon-近似表示, 即 Ex,y∈G∥(f(x)f(y)⊗IB−f(xy)⊗IB)ρ∥≤ϵ\mathbb{E}_{x,y\in G} \|(f(x)f(y) \otimes I_B-f(xy)\otimes I_B)\sqrt{\rho}\| \leq \epsilon. 那么存在一个等距 (isometry) 变换 V:HA→HA′V: \mathcal{H}_A\rightarrow \mathcal{H}_{A'} 和精确表示 τ:G→U(HA′)\tau: G\rightarrow \mathrm{U}(\mathcal{H}_{A'}) 使得 Ex∈G∥f(x)⊗IB−V†τ(x)V⊗IB∥2≤ϵ\mathbb{E}_{x\in G}\|f(x)\otimes I_B-V^{\dagger}\tau(x)V\otimes I_B\|^2 \leq \epsilon.

注意到这里的线性函数和特征标 (群表示) 都是一维的, 因而上面的等距变换是平凡的, 即 BLR 线性检测定理实际上是 Z2n\mathbb{Z}_2^n 上的 Gowers-Hatami 定理!

鉴于二者的定价性, BLR 线性检测的可靠性是被类似地从近似群表示"取整"到精确群表示的结果保证的, 这一结果也可以理解为关于线性函数的线性性质的性质检测 (property testing). 看起来适用于所有有限群的 Gowers-Hatami 定理给了我们设计更多性质检测的机会, 下面我们会介绍如何把上述测试用到矩阵值线性函数 (matrix-value function) 和 Pauli 矩阵 (即 Weyl-Hensenberg 群) 上.

Pauli 矩阵的线性检测

如何把线性检测"量子化"

在本系列的第一篇对量子交互式证明的介绍中, 我们提及了几种 games qPCP 定理的弱化版本, 其中之一是只将右边换成共享纠缠态的证明者们, 比如 NP⊆MIP∗(log⁡(n),c,c−δ)\mathsf{NP} \subseteq \mathsf{MIP^*}(\log (n),c,c-\delta) 或者 NEXP⊆MIP∗(poly(n),c,c−δ)\mathsf{NEXP} \subseteq \mathsf{MIP^*}(poly(n),c,c-\delta).

如何证明这些结果呢? 我们需要考虑的是一个完全经典的问题 (如 NP-complete\mathsf{NP}\text{-complete} 或者 NEXP-complete\mathsf{NEXP}\text{-complete} 的问题), 但是证明者之间却共享纠缠. 完备性 (completeness) 很好证明, 诚实的证明者们不用纠缠即可. 但是可靠性 (soundness) 呢, 证明者们有办法用他们共享的纠缠欺骗证者吗?

答案是肯定的, 回忆一下上一篇提及的 Magic Square game, 我们可以定义一个类似的 3-SAT3\text{-SAT} game, 即让玩家甲的问题是六个行或列其中之一, 而玩家乙的问题则是该行 (或列) 的三个格子其中之一, 获胜仅当被选中的格子两个玩家回答相同. 不难验证这是一个 99-变量的 3-SAT3\text{-}\mathsf{SAT} 实例, 而且是永假式 (因为矛盾方程), 所以经典的证明者们永远无法通过测试. 但是我们知道 Magic Square game 有算子解, 也就是说共享纠缠的证明者们是有办法总是通过测试的, 即使这是一个永假式 – 这意味着经典交互式证明系统的可靠性证明, 对共享纠缠的证明者们有可能不成立!

于是, 为了对于经典"证明" (witness) 设计一个证明者之间共享纠缠的验证协议, 我们需要解决下面两个问题:

  • 如何重新编码"证明", 使得其可以被局部检测 (locally testable). 上一节中的 Hadamard code 是否仍然适用?
  • 如果适用的话, 那么线性检测推广到证明者之间共享纠缠的情况? 并且需要保证新的"量子线性检测"此时仍然是可靠的.

第一个问题的答案是肯定的, 但是我们需要分析一下如何推广线性检测. 线性检测考虑的是函数 fi:F2n→{±1}f_i: \mathbb{F}_2^n \rightarrow \{\pm 1\} 是否足够接近某些线性函数. 但是如果证明者们可以使用量子策略的话, 我们并不知道我需要处理的函数是什么样的 – 便宜起见, 我们可以假设他们的量子策略都是投影测量 {Axa}\{A_x^a\} 并且共享纠缠态 ρ\rho, 但是这些量子态在投影测量下足够接近某些线性函数是什么意思呢?

我们可以考虑一个量子策略 {Mα}\{M^{\alpha}\}, 其中测量结果取决于 α∈F2n\alpha\in\mathbb{F}_2^n, 或者说测量结果可以被线性函数 χa\chi_a 刻画. 也就是说, 如果玩家先使用"线性"的量子策略 {Mα}\{M^{\alpha}\} 并给出结果 α⋅x\alpha\cdot x, 然后再使用量子策略 {Axa}\{A_x^a\} 并回答 a⋅xa\cdot x. 如果我们想要测试的量子策略 {Axa}\{A_x^a\} 足够"线性"的话, 那么使用这两个量子策略的输出结果也应该非常接近.

把上述想法数学化, 我们需要的考虑的是矩阵值函数 FF, 即它的输出是特征值为 {±1}\{\pm 1\} 的矩阵. 一个例子是所有正交矩阵 OO, 因为 OTO=IO^T O=I, 于是我们有 F:Z2n→Od(C)F: \mathbb{Z}_2^n \rightarrow O_d(\mathbb{C}). 在上一节中对特征标理论的简单介绍中, 我们提到特征标就是对可能的群表示取迹. 那么如何表示 "FF 几乎是线性的" 这句话呢? 我们同样可以用迹来刻画距离, 也就是说

如果 FF 几乎是线性的, 那么有 Ex,y1dReTr(F(x)F(y)F(x⊕y))≥1−O(ϵ)\mathbb{E}_{x,y} \frac{1}{d} \mathrm{Re}\mathrm{Tr}(F(x)F(y)F(x\oplus y)) \geq 1- O(\epsilon).

为了叙述便宜起见, 我们可以定义新的内积 ⟨A,B⟩f=d−1Tr(AB†)\langle A,B\rangle _f = d^{-1} \mathrm{Tr}(AB^{\dagger}). 对照上一节中的 BLR 定理, 我们可以写出相应的矩阵值函数 (matrix-valued function) 版本:

矩阵值函数的线性检测定理 给定线性矩阵函数 F:Z2n→Od(C)F:\mathbb{Z}_2^n\rightarrow O_d(\mathbb{C}) . 如果它满足 Ex,yRe⟨F(x)F(y),F(x+y)⟩f≥1−ϵ\mathbb{E}_{x,y} \mathrm{Re} \langle F(x)F(y), F(x+y)\rangle_f \geq 1-\epsilon, 那么存在 d′≥dd'\geq d, 以及线性等距 (isometry) V:Cd→Cd′V:\mathbb{C}^d\rightarrow \mathbb{C}^{d'} 和线性矩阵函数 G:Z2n→Od′(C)G:\mathbb{Z}_2^n\rightarrow O_{d'}(\mathbb{C}), 使得 Ex∥F(x)−V†G(x)V∥f2≤2ϵ\mathbb{E}_x \|F(x)-V^{\dagger}G(x) V\|_f^2 \leq 2\epsilon.

尽管我们仍然讨论的是有限交换群, 但是由于这里涉及的是矩阵值函数, 所以在比较已知的"线性"量子策略和被检查的量子策略的时候, 需要把后者投影到前者所在的线性空间上. 而"量子线性检测"的协议如下:

矩阵值函数的线性检测

(1) 裁判均匀地随机选择 a,a′,b∈{0,1}na,a',b\in\{0,1\}^n, 他把 aa 和 a′a' 作为问题发送给玩家甲, a+a′a+a' 和 bb 作为问题发送给玩家乙.

(2) 玩家甲给出 F(a),F(a′)F(a),F(a') 对应的测量结果, 玩家乙给出 F(a+a′),F(c)F(a+a'), F(c) 对应的测量结果. 玩家们获胜当且仅当他们的答案互相吻合.

上述结果可以用类似 Fourier 分析 (用有限群表示论的语言推广到矩阵值函数上) 的技术直接证明, 或者用 Gowers-Hatami 定理导出, 这就是在 Ito-Vidick 在 NEXP⊆MIP∗\mathsf{NEXP} \subseteq \mathsf{MIP^*} 的证明 (FOCS 2012 最佳论文奖[4]) 中的"量子线性检测"的核心想法. 更多的细节见季铮锋老师的讲义[5], 或 Thomas Vidick 博客上关于 Pauli Braiding test 的介绍的第一部分[6].

线性检测的"二次量子化": Pauli braiding test

回忆一下我们想证明的指数规模量子 PCP 定理, 即 QMA⊆MIP∗(poly,c,c−δ)\mathsf{QMA}\subseteq \mathsf{MIP^*}(\mathrm{poly},c,c-\delta). 类似上面指数规模 PCP 定理的证明, 我们需要考虑一个 QMA-complete\mathsf{QMA}\text{-complete} 问题, 设法把它的"证明"编码使得"新证明"更方便查阅, 再设法把"新证明"分发给所有证明者, 验证者通过证明者对一系列问题的回答判断"证明"的正确性. 上述流程的每一步都有一些困难, 不过在这一篇中我们只讨论如何判断"证明"的正确性.

在本系列的第一篇文章中, 我们曾提及局部哈密顿量问题 (local Hamiltonian problem) 是 QMA-complete\mathsf{QMA}\text{-complete} 的, 这一问题说的是以逆多项式的精度计算哈密顿量的基态能量, 自然这一问题的"证明"就是基态. 如何验证"证明"是某一量子态呢? 在一般情形下这一问题显然并不容易, 不过在上一篇文章中, 我们曾经提及量子态自检测 (self-testing) 这一概念 – 即如果获胜概率很接近最优值的话, 那么玩家们贡献的量子态很接近极大纠缠态. 对于一对 EPR 对和两对 EPR 对, 我们提及的例子分别是 CHSH game 和 Magic Square game. 不妨假设我们需要验证的"证明"就是极大纠缠态, 我们应该怎么做呢?

注意到极大纠缠态是用纠缠熵定义的, 并且在允许局部操作的情况下, 极大纠缠态是唯一的. 比如说考虑 EPR 对 ∣Ψ2⟩=12(∣00⟩+∣11⟩)|\Psi_2\rangle = \frac{1}{\sqrt{2}}(|00\rangle+|11\rangle) , 不难验证 X⊗Z∣Ψ2⟩=12(∣10⟩−∣01⟩)X\otimes Z|\Psi_2\rangle = \frac{1}{\sqrt{2}}(|10\rangle-|01\rangle) 也是极大纠缠态. 既然如此, 那么如果我们需要检测 nn-量子比特的极大纠缠态的话, 我们只需要验证它的维度是否是 2n2^n 即可!

回忆一下 CHSH game, 玩家甲的最优量子策略其实就是 Pauli 矩阵 XX 和 ZZ, 也就是说, 为了验证玩家们是否共享了 EPR 对, 我们只需要验证他们的量子策略是否为对应的 Pauli 矩阵即可, 这是因为 X⊗X∣Ψ2⟩=Z⊗Z∣Ψ2⟩=∣Ψ2⟩X\otimes X|\Psi_2\rangle=Z\otimes Z|\Psi_2\rangle=|\Psi_2\rangle.

对于单个量子比特的情形, Pauli 矩阵满足下述关系 X2=IX^2=I, Z2=IZ^2=I, XZ=−ZXXZ=-ZX, 实际上它是对应的 Weyl-Hensenberg 群的非平凡表示 – 虽然名字看着吓人, 但是只是 Pauli 矩阵构成的群模掉了复因子. 即考虑只有两个生成元 e1,e2e_1,e_2 的群, 他们满足关系 e12=0e_1^2=0, e22=0e_2^2 =0, e1e2+e2e1=0e_1e_2+e_2e_1=0.

而我们想测试的是 nn 个量子比特, 一个自然的想法就是考虑 transversal gate, 即把 nn 个量子比特看成一个维度 d=2nd=2^n 的 qudit. 比如说, 如果我们想测试五个量子比特的话, 那么需要考虑 X(11010)=X⊗X⊗I⊗X⊗IX(11010)=X\otimes X\otimes I\otimes X\otimes I. 于是 Pauli 矩阵 X(a),Z(b),∀a,b∈Z2nX(a),Z(b), \forall a,b\in\mathbb{Z}_2^n 满足下述关系:

  • 线性性质: X(a)X(b)=X(a⊕b)X(a)X(b)=X(a\oplus b), Z(a)Z(b)=Z(a⊕b)Z(a)Z(b)=Z(a\oplus b)
  • 反对易性质: X(a)Z(b)=(−1)a⋅bZ(b)X(a)X(a)Z(b)=(-1)^{a\cdot b} Z(b)X(a)

类似的, 2n2n-量子比特极大纠缠态 ∣Ψ⟩|\Psi\rangle (这里姑且认为是 nn 个 EPR 对的张量积) 也是 X(a)⊗X(a)X(a)\otimes X(a) 和 Z(b)⊗Z(b)Z(b)\otimes Z(b) 的特征值为 11 的特征向量, 这一性质对所有 a,ba,b 成立. 如果读者熟悉稳定化子编码 (stabilizer code) 的话, 实际上 {X(a)⊗X(a),Z(b)⊗Z(b):a,b∈Z2n}\{X(a)\otimes X(a),Z(b)\otimes Z(b): a,b\in \mathbb{Z}_2^n\} 就是一个稳定化子编码, 编码空间 (code space) 中唯一的量子态就是 ∣Ψ⟩|\Psi\rangle. 为什么这一节的标题仍然是"线性检测"呢? 注意 a,ba,b 的可能取值范围都是 Z2n\mathbb{Z}_2^n, 也就是说这里用了 Hadamard code! 此外, 不难看出, 如果我们想得到效率更高的自检测协议, 我们应该选择性质更好的经典纠错编码 — 这是交互式证明版本的量子 PCP 定理证明中的关键技术之一, 我们将在后文做进一步介绍.

综合一下我们在本节想做的事情, 这就是 Natarajan-Vidick 提出的 Pauli braiding test[7]:

Pauli braiding test 对于 nn 个 EPR 对的张量积 (即 2n2n-量子比特极大纠缠态), 我们有两个证明者的量子态自检测协议, 使得在允许误差为常数 ϵ\epsilon 的情况下, 只需要 O(n)O(n)-比特的问题和 O(1)O(1)-比特的回答, 可以达到完备性 c=1c=1, 可靠性 s=1−Ω(ϵ1/32)s=1-\Omega(\epsilon^{1/32}).

这是第一个常数完备性-可靠性间隙的 nn EPR 对的自检测协议, 即 c−sc-s 与 nn 无关. 这一技术在指数规模量子 PCP 定理的证明中扮演了关键角色, 因为这里的间隙与 nn 无关, 我们以此设计的规约是保持间隙不变的 (gap-preserving). 在下一节中, 我们将简要介绍这一协议, 并提及证明思路, 更多的技术细节见 Thomas Vidick 的博文[6:1] 或原始论文.

Gowers-Hatami 定理的应用

在上一节中, 我们把对玩家们共享的量子态是否为极大纠缠态的测试, 转化为玩家们使用的量子策略是否用 Pauli 矩阵描述的测试. 而描述 Pauli 矩阵的 Weyl-Heisenberg 群的生成关系包括两部分, 即线性性质和反对易性质. 事实上到目前为止, 我们已经分别介绍了这两类性质检测应该如何进行:

  • 线性性质的检测 (“一次量子化”) 可以使用这一部分第一节中矩阵值函数的线性检测, 是 Z2n\mathbb{Z}_2^n 上的BLR 线性检测的直接推广.
  • 反对易性质的检测 (“二次量子化”) 则可以使用广义 Magic Square game, 即推广到 qudit 删 — 我们在上一篇文章中以 CHSH game 为例, 给出了 CHSH game 导出的自检测协议和反对易性质的检测之间的关系.

因此, Pauli braiding test 的协议分为四部分, 包括

  • 对 X(a)X(a) 和 Z(b)Z(b) 的线性性质的测试, 使用矩阵值函数的线性检测.
  • 对 X(a)X(a) 和 Z(b)Z(b) 的反对易性质的测试, 使用广义 Magic Square game.
  • 相容性测试, 即询问两个玩家同样的问题, 检测答案是否相同.

上述协议的证明思路其实和 BLR 线性检测类似, 协议要求被检测的函数是某个有限群的近似表示, 那么对于被检测函数是群表示的情形, 完备性显然. 对于可靠性, 我们需要设法把近似群表示"取整"到群表示上, 这就需要用到 Gowers-Hatami 定理. 证明思路如下:

  • 考虑玩家通过测试的情形, 即他们的答案 (记作 X(a)X(a), Z(b)Z(b)) 近似满足 Weyl-Heisenberg 群的生成关系:
    • 线性性质: X(a)X(b)≈ϵX(a⊕b)X(a)X(b)\approx_{\epsilon}X(a\oplus b), Z(a)Z(b)≈ϵZ(a⊕b)Z(a)Z(b) \approx_{\epsilon} Z(a\oplus b)
    • 反对易性质: X(a)Z(b)≈ϵ(−1)a⋅bZ(b)X(a)X(a)Z(b) \approx_{\epsilon} (-1)^{a\cdot b} Z(b)X(a)
  • 使用 Gowers-Hatami 定理, 我们知道上述近似群表示 X(a),Z(b)X(a), Z(b) 可以找到对应的群表示 X(a),Z(b)\mathcal{X}(a), \mathcal{Z}(b), 并且这里的误差 ϵ\epsilon 是与 nn 无关的常数.

注意到 Stone-von Neumann 定理保证了 Weyl-Heisenberg 群的非平凡群表示是唯一的, 我们证明了 Pauli braiding test 的正确性, 即下述维度检测定理 (完整证明见 Thomas Vidick 的介绍[6:2]):

维度检测定理 考虑一组可观测量 W(a)W(a), 其中 W∈{X,Z}W\in\{X,Z\} 并且 a∈{0,1}na\in \{0,1\}^n. 对于量子态 ψ∈Cd⊗Cd\psi \in \mathbb{C}^d\otimes \mathbb{C}^d, 如果相应的测量结果通过 nn-量子比特 Pauli braiding test 的概率至少为 1−ϵ1-\epsilon, 那么量子态 ψ\psi 是维度 d=(1−O(ϵ))2nd=(1-O(\sqrt{\epsilon}))2^n 的极大纠缠态.

至此, 我们给出了检测 Weyl-Heisenberg 群的生成关系的 Pauli braiding test, 并指出这一自检测协议的可靠性由 Gowers-Hatami 定理保证, 这是后文证明交互式证明版本的量子 PCP 定理中所用的核心技术之一.

这一篇我们介绍了如何证明指数规模的经典 PCP 定理. 事实上即使从证明布尔二次方程组可解性 (quadratic solvability) 是 NP-complete\mathsf{NP}\text{-complete} 开始, 一步一步证明它的 gap 版本也是 NP-complete\mathsf{NP}\text{-complete} 的 (不可近似性), 然后在介绍线性检测 (包括证明), 并最终从两个角度证明指数规模 PCP 定理, 所需要的也不过是三四个小时而已 (假设听众只有本科计算理论基础).

但是证明指数规模的量子 PCP 定理则复杂得多, 通过上一篇和这一篇我们终于介绍了证明中所需要的大部分技术. 但是仍然有一些细节没有解决, 比如说

  • 在经典情形中"证明"可以直接分发给证明者们, 但是在量子情形中这一做法并不奏效, 因为量子不可克隆定理. 而如果把"证明"中的量子比特分奇偶发给不同的证明者呢? 这也不行, 因为同一约化密度矩阵可能对应不止一个量子态, 我们并不知道这一片"证明"到底是从哪来的.
  • Pauli braiding test 只能检测极大纠缠态, 我们并不知道如何处理一般的量子态 – 而到目前位置, 我们只介绍了一般的局部哈密顿量问题 (local Hamiltonian problem) 是 QMA-complete\mathsf{QMA}\text{-complete} 的, 于是我们可以找到满足我们要求 (基态是极大纠缠态) 的特殊情形的哈密顿量吗?

如果上述问题都被解决的话, 那么我们可以从一类特定的 QMA-complete\mathsf{QMA}\text{-complete} 问题出发, 构造一个 entangled game (MIP∗\mathsf{MIP^*} protocol): 如果玩家们的获胜概率在某个范围内的话, 那么对应的哈密顿量基态能量满足问题要求. 由于裁判和玩家之间的通信代价是多项式规模的, 上述构造证明了指数规模的 games qPCP theorem.

在下一篇中, 我们将会一一介绍上述问题被如何解决, 并最终给出指数规模的量子 PCP 定理. 并可能会提及一些 Hamiltonian qPCP (量子纠缠的不可近似性) 的简单介绍, 以及在 SIGACT News 那篇关于量子 PCP 猜想的著名综述[2:1] 之后的一些进展.

Reference

  1. [1801.03821] Low-degree testing for quantum states, and a quantum entangled games PCP for QMA ↩︎

  2. Aharonov, Dorit, Itai Arad, and Thomas Vidick. “Guest column: the quantum PCP conjecture.” Acm sigact news 44.2 (2013): 47-79. ↩︎ ↩︎

  3. CS286 Seminar in Computer Science: Around the quantum PCP conjecture ↩︎

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

  5. Zhengfeng Ji. Lecture Notes on Quantum Games ↩︎

  6. Thomas Vidick. Pauli Braiding Test ↩︎ ↩︎ ↩︎

  7. 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. ↩︎