这是关于交互式证明版本的量子 PCP 定理[1]和量子 PCP 猜想[2]的系列文章的第二篇, 这一篇会用到一点有限群表示论.

在上一篇中, 我们介绍了上世纪八十年代中期以来, 关于刻画交互式证明系统的计算能力的一系列结果, 我们发现交互式证明的计算能力比我们想象中要强大的多, 甚至可以导出 PCP 定理这样的惊人结果 — 只需要在"证明"中看上几眼, 就能以极高的概率判断"证明"是否正确. 而关于量子交互式证明系统, 十年前我们知道了 QIP=PSPACE=IP\mathsf{QIP}=\mathsf{PSPACE}=\mathsf{IP}, 这意味着(单一)证明者和验证者使用量子态通信不会对计算能力有任何提升, 这一结果也被推广到了多个证明者的情形. 因此, 我们出人意料地发现计算能力的提升竟然全部来自量子纠缠!

不过我们并没有给出刻画 MIP∗\mathsf{MIP^*} 的协议 (protocol) 的方式, 事实上它们通常被称为 entangled games (quantum games / non-local games). 这样的协议通常用一个裁判 (验证者) 和多个玩家 (证明者) 来描述, 由于而这通信使用量子态并不会提升计算能力, 我们只考虑它们之间传送经典信息的情况; 除此之外, 玩家之间会共享一个纠缠态, 这是量子交互式证明系统中的惊人计算能力提升的主要原因. 这一篇会从两个方面介绍 entangled games:

  • 一是从 entangled games 的视角介绍量子策略和获胜概率, 以及量子策略带来的关于获胜概率的优势的来源.
  • 二是从证明者们共享的纠缠态的视角介绍量子态的自检测 (self-testing), 即如果玩家们的获胜概率几乎最优的话, 那么他们共享的量子态几乎是极大纠缠态.

有趣的是, 如果从群表示论的观点 (Gowers-Hatami 定理[3]) 来看, 极大纠缠态的自检测实际上关于 Pauli 矩阵非对易性的性质检测 (property testing)! 这一联系也是 games qPCP theorem 证明中的关键技术之一.

下面开始正文.

交互式证明和 Entangled Games

下面介绍著名的 CHSH game 和 Magic Square game, 前者就是 Bell 不等式在 entangled games 下的版本.

CHSH game 和"量子优越性"

CHSH game 上的是这么一件事, 有两个玩家 (证明者) 和一个裁判 (验证者), 裁判分别把问题 s,t∈{0,1}s,t\in\{0,1\} 发给玩家甲和乙, 甲乙分别回复答案 a,b∈{0,1}a,b \in \{0,1\}, 当 a⊕b=s∧ta\oplus b=s\wedge t 的时候玩家们获胜, 如下图所示.

CHSH game (图片来自 [*Quantum mechanics: The usefulness of uselessness*](https://www.nature.com/articles/4661053a))

自然, 我们想问玩家们的最大获胜概率是多少? 不难验证,

  • 如果甲乙之间没有纠缠的话, 那么他们的获胜概率是 3/43/4 (就是瞎猜).
  • 但是出人意料的是, 如果甲和乙之间共享 EPR 对 (∣0⟩+∣1⟩)/2(|0\rangle+|1\rangle)/\sqrt{2}的话, 他们的获胜概率提高到 1/2+2/4≈0.851/2+\sqrt{2}/4 \approx 0.85 !

于是, 如果玩家们的获胜概率超过某个阈值的话, 我们就可以认为他们之间存在量子纠缠; 如果达到了最大获胜概率的话, 那么他们之间共享的量子纠缠是极大纠缠态 (maximally entangled state). 对于第二种情形, 考虑玩家们使用的量子策略, 不难转化到 Bell 不等式.

把上面关于 CHSH game 的描述形式化一下, 给出两个玩家一个裁判的 entangled game 的定义:

两个玩家一个裁判的 entangled game GG 可以用 G=(V,π)G=(V,\pi) 刻画, 其中

  • 裁判对玩家们的提问 (s,t)∈S×T(s,t) \in S\times T, SS 和 TT 分别是裁判对玩家甲和乙可能的提问.
  • 玩家们的回答 a∈A,b∈Ba \in A, b\in B, 其中 AA 和 BB 分别是玩家甲和玩家乙可能的回答.
  • 可能的提问 S×TS \times T 满足概率分布 π\pi.
  • 玩家们胜利与否由谓词 V(a,b∣s,t)∈{0,1}V(a,b|s,t) \in \{0,1\} 表示.

对应于上一节的多证明者交互式证明系统, 验证者接受证明者的回答即这里的 entangled game 中玩家取胜. 那么, 对于经典情形, 玩家们的最大获胜概率为 ωc(G(V,π))=max⁡a,b∑s,tπ(s,t)V(a(s),b(t)∣s,t).\omega_c(G(V,\pi)) = \max_{a,b} \sum_{s,t} \pi (s,t) V(a(s),b(t)|s,t). 注意到 π\pi 的可能集合为凸集, 所以最优解只可能是确定性策略 (deterministic strategy).

而对于量子情形, 鉴于玩家们之间共享了纠缠态 ∣ψ⟩|\psi\rangle, 而玩家们的答案是经典信息, 我们必须根据裁判的提问选择合适的可观测量测量 ∣ψ⟩|\psi\rangle 来得到答案. 量子策略可以使用正算子值测量 (positive operator-value measurement) 描述, 即玩家甲的策略为 {Xsa:s∈S,a∈A;∑a∈AXsa=I,∀s∈S}\{X_s^a: s\in S, a\in A; \sum_{a\in A}X_s^a=\mathbb{I}, \forall s\in S\}, 玩家乙的策略为 {Ytb:t∈T,b∈B;∑b∈BYtb=I,∀t∈T}\{Y_t^b: t\in T, b\in B; \sum_{b\in B} Y_t^b=\mathbb{I}, \forall t\in T\}. 于是他们的最大获胜概率为 ω∗(G)=∑(s,t)∈S×Tπ(s,t)∑a,b∈A×B⟨ψ∣Xsa⊗Ytb∣ψ⟩V(a,b∣s,t).\omega^*(G)=\sum_{(s,t)\in S\times T} \pi (s,t) \sum_{a,b\in A\times B} \langle\psi |X_s^a \otimes Y_t^b|\psi\rangle V(a,b|s,t).

不过量子策略通常会被写成可观测量的形式. 如果上面的 XsaX_s^a 和 YtbY_t^b 都是投影算符的话, 那么对于给定满足 ∑i=1kΠk=I\sum_{i=1}^k \Pi_k=\mathbb{I} 的投影算符 {Π1,⋯,Πk}\{\Pi_1,\cdots,\Pi_k\}, 以及它们对应的特征值 {λ1,⋯,λk}\{\lambda_1,\cdots,\lambda_k\}, 量子策略对应的可观测量可以写成 ∑j=1kλjΠj\sum_{j=1}^k \lambda_j\Pi_j. 比如说 CHSH game 的量子策略的可观测量可以写成 A0⊗B0+A0⊗B1+A1⊗B0−A1⊗B1A_0\otimes B_0+A_0\otimes B_1+A_1\otimes B_0-A_1\otimes B_1, AA和BB 分别表示甲乙, {0,1}\{0,1\} 表示他们的回答, 不难验证 A0=Z,A1=X,B0=H,B1=H~A_0=Z, A_1=X, B_0=H, B_1= \tilde{H} 是量子最优策略.

值得一提的是, 注意到 CHSH game 的谓词 V(a,b∣s,t)=(a⊗b=s∧t)V(a,b|s,t)=(a \otimes b=s\wedge t), 其实 CHSH game 是 XOR game 的特殊情形. XOR game 是少数被完全刻画的 entangled games 之一, Tsirelson 定理保证了计算使用量子策略时的最优获胜概率可以被半正定规划 (SDP) 刻画, 而半正定规划是有关于规模 nn 和误差 1/ϵ1/\epsilon 的多项式时间算法的. 而如上一节所说, 对于一般的 entangled games, 计算最优获胜概率是不可判定的, 可见 XOR game 的特殊之处. 关于 XOR game 和 Tsirelson 定理的更多介绍见 Thomas Vidick[4] 或季铮锋老师[5]的讲义, 这里不再展开.

Magic Square game 和完美量子策略

尽管上面的 CHSH game 使用量子纠缠会提高获胜概率, 不过仍然不是总会获胜. 有没有 entangled games 能使得量子情形的获胜概率为 11 呢? 答案是 Pseudo-telepathy game[6], 常用的例子是 Magic Square game. 考虑下面的 3×33\times 3 方格, 格子里的九个数 {e1,⋯,e9}\{e_1,\cdots,e_9\} 只能填 {0,1}\{0,1\}, 我们想找到一种填法使得实线行(列)的和为 00, 而虚线列的和为 1 (均为mod2\mod 2). Magic Square game 说的是, 裁判从六个行或者列中选一个, 要求玩家甲给出三个格子的填法; 然后从选定行(列)中选一个格子, 要玩家乙给出填法, 玩家们获胜即玩家甲和乙的答案吻合.

e1−e2−e3∣⋮∣e4−e5−e6∣⋮∣e7−e8−e9\begin{aligned}e_1 & - & e_2 & - & e_3\\| && \vdots && |\\e_4 & - & e_5 & - & e_6\\| && \vdots && |\\e_7 & - & e_8 & - & e_9\\\end{aligned}

注意到行和列的六条约束中, 不论九个格子如何取值, 总有一个约束不被满足, 那么任何经典策略都至多能做到 17/1817/18 的获胜概率. 但是 Magic Square game 有完美的量子策略! 玩家甲和玩家乙共享极大纠缠态 ∣EPR⟩⊗∣EPR⟩|\text{EPR}\rangle\otimes |\text{EPR}\rangle, 即对于每个 EPR 对, 一半在甲手上一半在乙手上. 下面我们给每个格子填上一个可观测量, 使得玩家甲只需要测量对应行 (列) 上的三个可观测量 (且测量顺序无关), 玩家乙只需要策略被选中的格子上的可观测量. 那么我们可以给出下述算子解 (operator solution):

I⊗Z−Z⊗Z−Z⊗I∣⋮∣X⊗Z−ZX⊗XZ−Z⊗X∣⋮∣X⊗I−X⊗X−I⊗X\begin{aligned} I\otimes Z & - & Z\otimes Z & - & Z\otimes I\\| && \vdots && |\\X\otimes Z & - & ZX \otimes XZ & - & Z\otimes X\\| && \vdots && |\\X\otimes I & - & X\otimes X & - & I\otimes X \\\end{aligned}

不难验证, 所有实线行(列)的三个格子乘积为 I⊗II\otimes I, 虚线列的为 −I⊗I-I\otimes I, 且每一行(列) 上的三个格子互相对易. 因为互相对易的可观测量有共同本征态, 而甲乙共享两对 EPR 对, 因而他们对于被选中格子的测量结果一样的, 所以我们得到了完美的量子策略.

如果读者熟悉 3-SAT3\text{-}\mathsf{SAT} 问题的话, 那么上述 Magic Square game 给出的约束也可以看成这一问题的一个实例. 有趣的是, 尽管这一实例对应的布尔表达式是永假式 (不管各变量如何取值都不能被满足), 但是如果量子证明者们总是能通过测试! 这意味着在经典交互式证明中关于可靠性 (soundness) 的分析, 在量子交互式证明中很可能不成立 – 量子纠缠使得量子证明者们有更多的办法欺骗验证者, 进而通过测试.

注意到 Magic Square game 实际上给出了一系列的线性约束 (加法形式) 以及关于可对易性的要求, 而算子解考虑的则是乘积形式的约束. 玩家甲处理的是线性约束, 而玩家乙要处理的则是变量, 实际是 Magic Square game 是 linear constraint system game 的例子之一. 此外, 量子力学中关于角动量的一个常用数学事实是, 可以用指数映射对应李代数 su(2)\mathfrak{su}(2) 和李群SU(2)\mathrm{SU}(2). 对群表示论有一些了解的读者, 不妨停下来想一想, 这和本节的 Magic Square game 有什么可类比之处?

量子最优策略的群表示论解释

在 entangled game 中, 玩家们用共享的纠缠态来测量量子策略对应的可观测量, 所以玩家对裁判的提问的回应跟对应的投影算符的特征值相对应, 因而上面的算子解关于行(列)的约束都是乘积形式. 那么我们所说的算子解究竟是什么呢?

  • 一方面, 算子解需要保证对应行(列)的线性约束总是被满足.
  • 另一方面, 算子解需要保证玩家们共享的纠缠态是算子解的共同本征态, 即算子解行(列)内部的对易关系.

在 Magic Square game 中, 后者的对易关系被 Pauli 矩阵的张量积满足, 即描述 Pauli 矩阵的反对易关系 {X,Z}=XZ+ZX=0\{X,Z\}=XZ+ZX=0 需要被满足. 于是, 给定集合 S={e1,⋯,e9}S=\{e_1,\cdots,e_9\}, Magic Square game 的算子解可以被下述代数关系刻画 (d=2d=2):

  • Requation={e1e2e3=1,⋯,e1e4e7=1,e2e5e8=−1,e3e6e9=1;e1d=1,⋯,e9d=1}R_{equation}=\{e_1e_2e_3=1,\cdots,e_1e_4e_7=1,e_2e_5e_8=-1,e_3e_6e_9=1;e_1^d=1,\cdots,e_9^d=1\}
  • Rcommutation={[e1,e2]=1,[e1,e3]=1,[e2,e3]=1,⋯}R_{commutation}=\{[e_1,e_2]=1,[e_1,e_3]=1,[e_2,e_3]=1,\cdots\}

如果把 SS 当成生成元, RequationR_{equation} 和 RcommutationR_{commutation} 当成约束关系的话, 那么 Magic Square game 的 solution group Γ=⟨S∣Requation∪Rcommunication⟩\Gamma=\langle S|R_{equation} \cup R_{communication}\rangle 是一个自由群 (free). 自由群中的每一个元素称为 word, 即由生成元 eie_i 和生成元的逆 ei−1e_i^{-1} 作为字母表描述的有限长度字符串.

因而, 我们所说的 Magic Square game 的算子解, 就是上述 solution group 的在 Hilbert 空间上的非平凡群表示. 群表示 τ\tau 说的是保持同态关系的映射 τ:G→U(V)\tau: G\rightarrow \mathrm{U}(V), VV 是作为群 GG 的表示的酉群所在的线性空间 (这里为 Hilbert 空间), 同态的意思是 ∀x,y∈G,τ(x−1y)=τ(x)†τ(y)\forall x,y \in G, \tau(x^{-1}y)=\tau(x)^{\dagger}\tau(y). 我们说一个群表示是平凡 (trivial) 的, 即群表示为恒等映射. 进一步地, 对于任何 linear constraint system games, 我们都可以将线性约束相对应的 solution group 在 Hilbert 空间上的非平凡群表示视作量子策略, 并且这样的量子策略使得 entangled games 的获胜概率最大[7].

自检测: 量子态的量子证明

如果有人声称他手上的若干台终端构成了量子网络的话, 我们应该怎么验证他说的是不是真的呢?

比如说下述遛狗场景, 我们觉得他们 (狗) 之间共享"纠缠", 但是显然我们并不能学着汪汪汪一番问出来答案 – 我们只能用遛狗的绳子 (leash) 来设法测试他们之间是否真的共享"纠缠", 其实这和自检测 (self-testing) 的思路很像, 我们只用和狗之间的特定类型的通信 (绳子), 来确认他们是否满足某些性质.

Self-testing (图片来自网络)

本节考虑这一问题的简化版本, 如果我们需要检测两台终端, 并且我们被告知终端之间共享了多个 EPR 对 (极大纠缠态), 我们怎么判断这是不是几乎是真的呢? 我们只能接触这两台终端 (自检测的"自"), 并不能使用其他 (已验证的) 量子设备, 就像我们只能用绳子来遛狗一样.

什么是自检测 (self-testing)

回忆一下上一节的 CHSH game, 当玩家甲和乙之间共享 EPR 对的时候, 我们可以选择合适的量子策略达到最优获胜概率. 那么如果玩家甲乙之间共享的量子态不是 EPR 对呢? 如果是乘积态的话, 那显然和经典情形一样. 如果是其他纠缠态的话, 那应该多少还有一点"量子优势". 如果是跟 EPR 对很接近的量子态呢? 那应该最优获胜概率也很接近吧, 这么看起来玩家们之间共享的极大纠缠态在 local unitary 下是唯一的 – 最后这个猜测是对的, 上一段给出的问题称为自检测 (self-testing), 我们可以设计一套检测流程 (protocol), 使得只有两台终端之间共享的纠缠态非常接近极大纠缠态 (在 local unitary 下) 的时候, 才能通过测试.

这里通过测试的概率 cc 就是上一节的 entangled games 的获胜概率 cc, 或者说是多证明者交互式证明系统中"证明"被接受的概率 cc. 自检测意味着, 如果通过测试的概率高于 c−ϵc-\epsilon, 那么这里的纠缠态 ∣ϕ⟩|\phi\rangle (允许 local unitary 操作) 和极大纠缠态 ∣ψ⟩|\psi\rangle 的距离是 ϵ\epsilon (最好是常数), 即 ∃U,V,∥(U⊗V)∣ϕ⟩−∣ψ⟩∥≤ϵ\exists U,V, \|(U\otimes V) |\phi\rangle - |\psi\rangle\| \leq \epsilon. 这样的性质也称为 rigidity.

下面以 EPR 对和 CHSH game 为例[8]说明. 我们知道 CHSH game 的最优量子策略是 A0=Z,A1=X,B0=H,B1=H~A_0=Z, A_1=X, B_0=H,B_1=\tilde{H}, 如果玩家甲乙共享的是极大纠缠态的话, 可以达到最优获胜概率 c=1/2+2/4c=1/2+\sqrt{2}/4, 因而我们可以把 CHSH game 作为验证 EPR 对的自检测流程. 如果考虑两台终端共享纠缠态 ∣ϕ⟩∈Cd⊗Cd|\phi\rangle \in \mathbb{C}^d\otimes \mathbb{C}^d , 且他们通过自检测的概率为 c−ϵc-\epsilon, 那么存在分别作用在终端甲和终端乙上的 local unitary U,VU,V满足下述关系 (A1A_1 和 B1B_1 有对应的约束):

∥(U⊗V∣ϕ⟩−∣EPR⟩⊗∣AUX⟩)∥≤O(ϵ)∥(U⊗V)(A0⊗Id)∣ϕ⟩−(σz⊗Id)∣EPR⟩⊗∣AUX⟩∥2≤O(ϵ)∥(U⊗V)(Id⊗B0)∣ϕ⟩−(Id⊗H)∣AUX⟩⊗∣EPR⟩∥2≤O(ϵ)\begin{aligned}\|(U\otimes V |\phi\rangle - |\text{EPR}\rangle\otimes|AUX\rangle)\| &\leq O(\sqrt{\epsilon})\\\|(U\otimes V)(A_0\otimes I_d)|\phi\rangle - (\sigma_z \otimes I_d) |\text{EPR}\rangle\otimes |AUX\rangle\|^2 & \leq O(\sqrt{\epsilon})\\\|(U\otimes V)(I_d\otimes B_0)|\phi\rangle - (I_d \otimes H) |AUX\rangle\otimes |\text{EPR}\rangle\|^2 & \leq O(\sqrt{\epsilon})\\\end{aligned}

如果要验证两对 EPR 对呢? 我们也可以证明 Magic Square game 就是对应的自检测流程[9]. 如果是要验证三对 EPR 对呢? 我们仍然可以设计一个类似的 entangled game, 不过这次是在五角星上[7:1], 共有五条约束四个变量 (其中一条乘积为 −1-1, 其余为 11). 这个方程没有经典解, 但是有算子解 (需要作用在三个量子比特上). 那么如果要验证 nn 对 EPR 对呢? 来来来, 我们再画个奇怪的图对应奇怪的矛盾方程组, 并且使得这里的约束有算子解…想法不错, 不过画图还是免了. 实际上我们可以用 d=2nd=2^n 的 qudit 上的 Pauli 矩阵替换 CHSH game 或者 Magic Square game 中的可观测量, 再结合合适的纠错编码即可, 这里先留个悬念.

自检测与近似群表示

上一段我们介绍了自检测 (self-testing), 但是如何证明某一 entangled game 是极大纠缠态的自检测 (self-test) 协议呢? 上一节提及了一个重要事实, 对于 linear constraint system games, 最优量子策略是描述线性约束的 solution group 的非平凡表示[7:2]. 那么如果要考虑接近最优的量子策略呢? 我们需要一个和最优策略很接近的"群表示", "很接近"意味着我们可以对这个近似的"群表示"进行**“取整”**得到真正的群表示. 比如说 solution group 其中一个关系是 e1e2e3=1e_1e_2e_3=1, 它的非平凡群表示是 A1A2A3=IA_1A_2A_3 = I, 而它的近似群表示看起来应该满足类似 ∥A~1A~2A~3−I∥≤ϵ\|\tilde{A}_1\tilde{A}_2\tilde{A}_3-I\| \leq \epsilon 的形式. 下一个问题自然是, 这样的"取整"操作对于哪些群存在呢?

Gowers-Hatami 在 2015 年证明了下述定理[3:1], 即这样的"取整"操作对任意有限群均存在:

考虑有限群 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.

比如单量子比特的 Pauli 矩阵构成的群 (即 Weyl-Heisenberg 群) G={I,X,Z,XZ,−I,−X,−Z,−XZ}G=\{I,X,Z,XZ,-I,-X,-Z,-XZ\}, 如果有 X~,Z~\tilde{X},\tilde{Z} 满足 X~2≈ϵI\tilde{X}^2\approx_\epsilon I, Z~2≈ϵI\tilde{Z}^2\approx_\epsilon I, [X~,Z~]=X~Z~X~†Z~†=−I[\tilde{X},\tilde{Z}]=\tilde{X}\tilde{Z}\tilde{X}^{\dagger}\tilde{Z}^{\dagger}=-I, 那么由 Gowers-Hatami 定理, 我们可以定义一个嵌入 f:G→U(Cd)f:G\rightarrow\mathrm{U}(\mathbb{C}^d) 满足 f(I)=If(I)=I, f(X)=X~f(X)=\tilde{X} 和 f(Z)=Z~f(Z)=\tilde{Z}. 进而可以验证, ∀x,y∈G\forall x,y\in G, f(x)f(y)≈ηf(xy)f(x)f(y)\approx_{\eta}f(xy) 成立, 其中 η≤16ϵ\eta \leq 16\epsilon.

事实上, 我们还可以用上面的例子进一步证明 CHSH game 是 EPR 对的自检测 (完整推导见[4:1]). 注意到 V†τ(x)VV^{\dagger} \tau(x)V 对于 ∀x∈G\forall x \in G 可以被 f(x)f(x) 近似, 考虑近似最优的量子策略 {A0,A1,B0,B1}\{A_0,A_1,B_0,B_1\}, 不难得到

14⟨ψ∣A0⊗B0+A0⊗B1+A1⊗B0−A1⊗B1∣ψ⟩≥22−ϵ⇒14⟨ψ∣(VA⊗VB)†(X⊗H+Z⊗H+X⊗H~−Z⊗H~)(VA⊗VB)∣ψ⟩≥12−O(ϵ)⇔12⟨ψ∣(VA⊗VB)†(X⊗X+Z⊗Z)(VA⊗VB)∣ψ⟩≥1−O(ϵ).\begin{aligned}& \frac{1}{4} \langle \psi | A_0\otimes B_0 + A_0\otimes B_1 + A_1\otimes B_0 - A_1\otimes B_1 | \psi \rangle \geq \frac{\sqrt{2}}{2}-\epsilon\\ \Rightarrow & \frac{1}{4} \langle \psi| (V_A\otimes V_B)^{\dagger} (X\otimes H+Z\otimes H+X\otimes \tilde{H}-Z\otimes\tilde{H})(V_A\otimes V_B)|\psi\rangle \geq \frac{1}{2}-O(\sqrt{\epsilon})\\ \Leftrightarrow & \frac{1}{2} \langle \psi|(V_A\otimes V_B)^{\dagger} (X\otimes X+Z\otimes Z) (V_A\otimes V_B)|\psi\rangle \geq 1-O(\sqrt{\epsilon}). \end{aligned}

上式用到了 H+H~=2XH+\tilde{H}=2X 和 H−H~=2ZH-\tilde{H}=2Z. 由于 (X⊗X+Z⊗Z)/2∣EPR⟩=∣EPR⟩(X\otimes X+Z\otimes Z)/2|\text{EPR}\rangle=|\text{EPR}\rangle, 对于能够通过测试的 ∣ψ⟩|\psi\rangle, 我们知道 ∣ψ⟩|\psi\rangle 和 ∣EPR⟩|\text{EPR}\rangle 非常接近. 即 CHSH game 是 22-量子比特极大纠缠态的自检测协议.

另外, 如果读者熟悉稳定化子编码 (stabilizer code) 的话, 考虑 {∣EPR⟩}\{|\text{EPR}\rangle\} 稳定化子 S=⟨{X⊗X,Z⊗Z}⟩S = \langle \{X\otimes X,Z\otimes Z\}\rangle, 这一关系也可能看成稳定化子编码的一个平凡例子. 注意到这里的生成元可以分成只跟 XX 有关的部分和只跟 ZZ 有关的部分, 这个例子也能看成 CSS code (Calderbank-Shor-Steane), XX 和 ZZ 分别对应的 (相同的) 线性编码 (linear code) 的生成矩阵 (generating matrix) 为 (11)\begin{pmatrix}1\\1\end{pmatrix}. 这也是后文中对 2n2n-量子比特设计的自检测协议中的关键想法之一, 通过使用性质更好的经典纠错编码, 我们可以在保证自检测协议的误差 ϵ\epsilon 与 nn 无关的同时, 进一步减少通信代价.

自检测与 entangled game

上一段说道, CHSH game 是 22-量子比特的自检测协议. 如果我们能够证明 Weyl-Heisenberg 群中的反对易关系 {X,Z}=XZ+ZX=0\{X,Z\}=XZ+ZX=0 近似成立的话, 那么由 Gowers-Hatami 定理结论得证, 不过我们没有提及证明. 实际上, 当这样的协议的获胜概率接近最优值的时候, 我们可以推出反对易关系近似成立, 下面对 CHSH game 的获胜概率稍作些计算 (完整推导见[4:2]). 考虑甲乙共享量子态 ρ=∣ψ⟩⟨ψ∣\rho=|\psi\rangle\langle\psi|, 并用近似最优的量子策略 {A0,A1,B0,B1}\{A_0,A_1,B_0,B_1\}使得通过测试的概率 ≥1−ϵ\geq1-\epsilon, 可以得到

4(1−ϵ)2≤∣⟨ψ∣A0⊗B0+A0⊗B1+A1⊗B0−A1⊗B1∣ψ⟩∣2≤⟨ψ∣(A0⊗B0+A0⊗B1+A1⊗B0−A1⊗B1)2∣ψ⟩=Tr((A0⊗B0+A0⊗B1+A1⊗B0−A1⊗B1)2ρ)=Tr[4(Id⊗Id)ρ]+Tr[(A1A0−A0A1)⊗(B0B1−B1B0)ρ]≤4+Tr[(1+1)(A1A0+A0A1)2⊗(1+1)(B0B1+B1B0)2ρ]\begin{aligned}4(1-\epsilon)^2 & \leq |\langle \psi | A_0\otimes B_0 + A_0\otimes B_1 + A_1\otimes B_0 - A_1\otimes B_1 | \psi \rangle|^2\\& \leq \langle \psi | (A_0\otimes B_0 + A_0\otimes B_1 + A_1\otimes B_0 - A_1\otimes B_1)^2 | \psi\rangle\\& = \mathrm{Tr}( (A_0\otimes B_0 + A_0\otimes B_1 + A_1\otimes B_0 - A_1\otimes B_1)^2 \rho)\\&= \mathrm{Tr}[4 (I_d\otimes I_d)\rho] + \mathrm{Tr}[(A_1A_0-A_0A_1)\otimes (B_0B_1-B_1B_0) \rho]\\&\leq 4 + \mathrm{Tr}\left[\sqrt{(1+1)(A_1A_0+A_0A_1)^2}\otimes \sqrt{(1+1)(B_0B_1+B_1B_0)^2} \rho\right]\end{aligned}

上述计算中最后一步是 Cauchy-Swartz 不等式, 由其取等条件, 我们可以得到

Tr((A1A0+A0A1)2ρA)=∥A1A0+A0A1∥ρA2=O(ϵ)Tr((B1B0+B0B1)2ρB)=∥B1B0+B0B1∥ρB2=O(ϵ)\begin{aligned}\mathrm{Tr}((A_1A_0+A_0A_1)^2 \rho_A) &= \|A_1A_0+A_0A_1\|^2_{\rho_A} = O(\sqrt{\epsilon})\\\mathrm{Tr}((B_1B_0+B_0B_1)^2 \rho_B) &= \|B_1B_0+B_0B_1\|^2_{\rho_B} = O(\sqrt{\epsilon})\\\end{aligned}

其中 ρA\rho_A 和 ρB\rho_B 分别是共享的量子态 ∣ψ⟩|\psi\rangle 关于甲和乙的约化密度矩阵 (reduced density matrix). 因而, 我们从 CHSH game 的 rigidity 中推出了反对易关系近似成立 {A0,A1}=O(ϵ)\{A_0,A_1\}=O(\sqrt{\epsilon}), 对于 Magic Square game 我们也可以导出类似的结果.

更一般地, 我们可以对任意 2n2n-量子比特的自检测协议定义下述 anti-commutation game (这用使用量子线性检测[10]中的定义) 来检测 Weyl-Heisenberg 群中的反对易性质. 考虑两玩家 entangled game, 并且裁判对第二个玩家有一系列答案为 {±1}\{\pm1\} 的问题 qX,qZ∈Z2nq_X, q_Z \in \mathbb{Z}_2^n (答案由 fX(⋅),fZ(⋅)f_X(\cdot), f_Z(\cdot) 给出). 那么我们需要考虑两个方面, 一是真的反对易的可观测量能通过测试 (称为完备性), 二是几乎通过测试意味着量子策略几乎就是反对易的 (称为可靠性):

  • 完备性 (completeness): 如果两个玩家共享极大纠缠态的话, 那么他们可以找到一个量子策略达到最优获胜概率, 并且第二个玩家的量子策略对应的可观测量满足性质 (问题 fZf_Z 要求类似):
    • 问题 fXf_X 对应的可观测量是 ∑afX(a)AqXa=X⊗I\sum_{a} f_X(a)A_{q_X}^a = X\otimes I, 即相当于在第一对 EPR 对上玩家甲用 XX 测量,
    • 问题 aa 和回答 qXq_X 对应的量子策略是 XX 的特征空间上的投影算符.
  • 可靠性 (soundness): 如果两个玩家共享某个量子态 ∣ψ⟩|\psi\rangle, 使得他们的获胜概率非常接近最优获胜概率, 那么
    • 量子策略的可观测量 X~=∑afX(a)AqXa\tilde{X} = \sum_a f_X(a) A_{q_X}^a 和 Z~=∑afZ(a)AqZa\tilde{Z}=\sum_a f_Z(a) A_{q_Z}^a 是 XX 和 ZZ 的近似表示.
    • 通过在他们共享量子态 ∣ψ⟩|\psi\rangle 上的局部操作, 我们可以使得 ∣ψ⟩|\psi\rangle 和 ∣EPR⟩⊗∣AUX⟩|\text{EPR}\rangle \otimes |AUX\rangle 非常接近.

这里的玩家甲和乙也可以看做证明者, 那么如果他们使用的策略如可靠性定义中所描述的话, 他们是诚实的 (honest). 由于上述 anti-commutation game 和极大纠缠态的自检测协议等价, 在上一段中我们证明了 CHSH game 是 (1/2+2/4,O(ϵ))(1/2+\sqrt{2}/4,O(\sqrt{\epsilon})) anti-commutation game, 类似地可以证明 Magic Square game 是 (1,O(ϵ))(1,O(\sqrt{\epsilon})) anti-commutation game.

Anti-commutation game 给出了 Weyl-Heisenberg 群中的反对易关系的性质检测 (property testing) 方法, 这在后文中给出 ∣EPR⟩⊗n|\text{EPR}\rangle^{\otimes n} 的自检测协议中非常重要, 也是后文中 entangled game 版本的指数规模量子 PCP 定理 QMA⊆MIP∗(poly(n),1,1/2)\mathsf{QMA} \subseteq \mathrm{MIP^*}(poly(n),1,1/2) 的证明中的核心技术之一.

在下一篇文章中, 我们介绍如何用线性检测 (linearity test) 来证明指数规模的经典 PCP 定理, 即给出 NP-complete\mathsf{NP}\text{-complete} 问题有限域二次方程可解性 (quadratic solvability) 的通信代价 poly(n)poly(n) 的常数 c−sc-s 间隙的多证明者交互式证明系统协议. 并用 Z2n\mathbb{Z}_2^n 的近似群表示来重新理解线性检测, 以及如何给出对应的量子版本, 本段的 anti-commutation game 是量子线性检测的重要部分之一.

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. Gowers, William Timothy, and Omid Hatami. “Inverse and stability theorems for approximate representations of finite groups.” Sbornik: Mathematics 208, no. 12 (2017): 1784. ↩︎ ↩︎

  4. https://cseweb.ucsd.edu/~slovett/workshops/quantum-computation-2018/material.html ↩︎ ↩︎ ↩︎

  5. https://uwaterloo.ca/institute-for-quantum-computing/sites/ca.institute-for-quantum-computing/files/uploads/files/lecture-1_0.pdf ↩︎

  6. Brassard, Gilles, Anne Broadbent, and Alain Tapp. “Quantum pseudo-telepathy.” Foundations of Physics 35, no. 11 (2005): 1877-1907. ↩︎

  7. Coladangelo, Andrea, and Jalex Stark. “Robust self-testing for linear constraint system games.” arXiv preprint arXiv:1709.09267 (2017). ↩︎ ↩︎ ↩︎

  8. McKague, Matthew, Tzyh Haur Yang, and Valerio Scarani. “Robust self-testing of the singlet.” Journal of Physics A: Mathematical and Theoretical 45, no. 45 (2012): 455304. ↩︎

  9. Wu, Xingyao, Jean-Daniel Bancal, Matthew McKague, and Valerio Scarani. “Device-independent parallel self-testing of two singlets.” Physical Review A 93, no. 6 (2016): 062121. ↩︎

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