目前的答案是, 如果有一个非常精确的量子交互式证明的话, 那么我们可以用量子交互式证明来验证停机问题 [1]. 除此之外, 我们甚至还能找到一个具有完美零知识证明 (perfect zero-knowledge proof) 性质的量子交互式证明系统 [2].

那么如果用正常的量子交互式证明, 即要么玩家们一定获胜, 要么玩家们获胜概率小于 1/3), 它能够验证停机问题 (Halting) 吗?

注意到停机问题是 RE\mathsf{RE}-complete 的 (recursively enumerable), 这意味我们需要证明 RE⊆MIP∗\mathsf{RE} \subseteq \mathsf{MIP^*}. 然而这一结果会推翻算子代数中的 Connes’ embedding conjecture. 如果想知道更多细节的话, Thomas Vidick 写的 科普文 是个很好的介绍.

在本文的剩余章节, 我会分别简单解释标题中的 “量子”, “交互式证明” 和 “验证” 是在说什么.

从量子非局域性说起

通常当我们提及量子非局域性的时候, 通常都会提及 Bell 不等式. 如果用 non-local games 的形式 [3] 来写的话, 就是

Non-local game. 考虑两个玩家和一个裁判的 non-local game GG , 裁判分别把问题 (s,t)∈S×T(s,t)\in S\times T 发给而玩家甲和乙, 甲和乙分别回复答案 (a,b)∈A×B(a,b)\in A\times B, 这里取S=T=A=B={0,1}S=T=A=B=\{0,1\}, 当 V(a,b∣s,t)=(a⊕b=s∧t)V(a,b|s,t) = (a\oplus b = s\wedge t) 的时候玩家们获胜. 当然, 玩家们和裁判的问答的规模是多项式的. 对于裁判和玩家之间的具体问题, 玩家们胜利与否用谓词 V(a,b∣s,t)∈{0,1}V(a,b|s,t)\in\{0,1\} 表示. 可能的提问 S×TS\times T 满足分布 π\pi.

那么玩家们的最大获胜概率刻画如下:

  • 玩家之间不能共享纠缠: ωc(G)=max⁡a,b∑s,tπ(s,t)V(a(s),b(t)∣s,t)\omega_c(G) = \max_{a,b}\sum_{s,t} \pi(s,t) V(a(s),b(t)|s,t).
  • 玩家之间共享纠缠态 ∣ψ⟩|\psi\rangle, 玩家甲和玩家乙的策略分别为投影算符集合 {Xsa}a∈A,s∈S\{ X_s^a \}_{a\in A,s\in S} 和 {Ytb}t∈T,b∈B\{Y_t^b\}_{t\in T,b\in B}, 并且使得 ∑aXsa=I,∑bYtb=I:ωq(G)=∑(s,t)∈S×Tπ(s,t)∑(a,b)∈A×B⟨ψ∣Xsa⊗Ytb∣ψ⟩V(a,b∣s,t)\sum_a X_s^a = I, \sum_b Y_t^b = I: \omega_q(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).

对于 CHSH game, 不难证明 ωc(G)=34<2+24=ωq(G)\omega_c(G) = \frac{3}{4} < \frac{2+\sqrt{2}}{4} = \omega_q(G). 这里的量子策略的优越性, 通常被称为违反 Bell 不等式. 进一步介绍 (譬如 selt-testing), 见 量子 PCP 猜想浅说 (二): 量子纠缠的交互式证明验证.

更一般地, 考虑满足某些结构的$ (|\psi\rangle, {X_s^a}{s\in S, a\in A}, {Y_t^b}{t\in T, b\in B}), 可以定义对应的量子关联的集合\mathcal{C}{q}, \mathcal{C}{qs}, \mathcal{C}{qa}, \mathcal{C}{qc}$:

  • 玩家甲和玩家乙分别有一个有限固定维度的 Hilbert space H1,H2,{Xsa},{Ytb}\mathcal{H}_1, \mathcal{H}_2, \{X_s^a\}, \{Y_t^b\} 分别定义在 H1,H2\mathcal{H}_1, \mathcal{H}_2 上, ∣ψ⟩∈H1⊗H2|\psi\rangle \in \mathcal{H}_1\otimes \mathcal{H}_2, 那么这样的量子关联的集合记作 Cq\mathcal{C}_q.
  • 玩家甲和玩家乙分别有一个无限维度的 Hilbert space H1,H2,{Xsa},{Ytb}\mathcal{H}_1, \mathcal{H}_2, \{X_s^a\}, \{Y_t^b\} 分别定义在 H1,H2\mathcal{H}_1, \mathcal{H}_2 上, ∣ψ⟩∈H1⊗H2|\psi\rangle \in \mathcal{H}_1\otimes \mathcal{H}_2, 那么这样的量子关联的集合记作 Cqs\mathcal{C}_{qs}.
  • 对于一系列可数维度的 Hilbert space H1(l),H2(l)\mathcal{H}_1^{(l)}, \mathcal{H}_2^{(l)}, 玩家甲和玩家乙均有分别定义在 H1(l),H2(l)\mathcal{H}_1^{(l)}, \mathcal{H}_2 ^{(l)} 上的策略{Xsa}(l),{Ytb}(l)\{X_s^a\}^{(l)}, \{Y_t^b\}^{(l)}, 共享的纠缠态 ∣ψ(l)⟩∈H1(l)⊗H2(l)|\psi^{(l)}\rangle \in \mathcal{H}_1^{(l)}\otimes \mathcal{H}_2^{(l)}, 那么这样的量子关联的集合记作 Cqa\mathcal{C}_{qa}.
  • 玩家甲和玩家乙共享一个无限维度的 Hilbert space H,{Xsa},{Ytb}\mathcal{H}, \{X_s^a\}, \{Y_t^b\}和 ∣ψ⟩|\psi\rangle 都定义在 H\mathcal{H} 上, 并且满足 ∀a,b,s,t,[Xsa,Ytb]=0\forall a,b,s,t, [X_s^a,Y_t^b]=0, 这样的量子关联的集合记作 Cqc\mathcal{C}_{qc}.

根据上述定义, 不难看出 Cq⊆Cqs⊆Cqa⊆Cqc\mathcal{C}_{q}\subseteq \mathcal{C}_{qs} \subseteq \mathcal{C}_{qa} \subseteq \mathcal{C}_{qc}. 除此之外, 也不难定义经典关联构成的集合 Cc\mathcal{C}_{c}, 玩家甲和玩家乙之间不共享纠缠态即可. Boris Tsirelson 在上世纪八十年代提出的问题 (和 Connes’ embedding conjecture 等价) 可以表述为下述形式:

Tsirelson 问题. Cqa\mathcal{C}_{qa} 和 Cqc\mathcal{C}_{qc} 是否相等?

这一问题在最近五年有了一系列进展, 即 Cq⊊Cqs⊊Cqa⊆Cqc\mathcal{C}_{q} \subsetneq \mathcal{C}_{qs} \subsetneq \mathcal{C}_{qa} \subseteq \mathcal{C}_{qc}:

  • William Slofstra 在 2016 年证明了 Cqs≠Cqc\mathcal{C}_{qs} \neq \mathcal{C}_{qc} [4] (即弱 Tsirelson 问题的否定答案), 并在次年改进到了 Cqs≠Cqa\mathcal{C}_{qs} \neq \mathcal{C}_{qa} [1:1].
  • 而 Jalex Stark 和 Andrea Coldangelo 在 2018 年证明了 Cq≠Cqs\mathcal{C}_{q} \neq \mathcal{C}_{qs} [5].

目前仍然悬而未决的是 Tsirelson 问题. 而这一问题的肯定答案, 即 Cqa=Cqc\mathcal{C}_{qa}=\mathcal{C}_{qc}, 会在量子计算复杂性理论中导出令人惊讶的结果.

不同模型上的量子交互式证明

为什么上面关于量子关联的刻画和计算复杂性有关呢? 这里需要稍费些笔墨介绍交互式证明, 量子 PCP 猜想浅说 (一): 当交互式证明遇上量子纠缠 中介绍了相关的历史, 这里只简单提及相关的部分.

交互式证明说的是这么一个东西, 这里有常数个证明者 (prover), 还有一个验证者 (verifier), 通常验证者的能力是经典概率多项式时间的, 而证明者的能力不受限制 (尽管同时他们也不受验证者的信任), 证明者和验证者之间的通信规模是多项式的.

交互式证明系统的能力与时间/空间复杂性的联系, 可能是计算复杂性理论在上世纪八十年代末最大的观念上的革新 – 如果只有一个证明者, 这样的交互式证明系统 (IP) 完全刻画了多项式空间 (IP=PSPACE); 如果有多个证明者, 这样的交互式证明系统 (MIP) 完全刻画了非确定性指数时间 (MIP=NEXP).

上述的 non-local games 可以看做交互式证明系统, 于是我们可以定义三个对应的复杂性类:

MIP\mathsf{MIP}. 如果证明者之间没有共享纠缠的话, 即上一节中的集合 Cc\mathcal{C}_c 那么判定这样的交互式证明系统的最大获胜概率对应的复杂性类称作 MIP\mathsf{MIP}. MIP*. 上一节中在张量积 模型 (tensor product model) 上定义的三个集合 Cq,Cqs,Cqa\mathcal{C}_{q},\mathcal{C}_{qs},\mathcal{C}_{qa}, 即证明者之间可以共享任意的纠缠态, 那么判定这样的量子交互式证明系统的最大获胜概率的问题对应的复杂性类称作 MIP∗\mathsf{MIP^*}.

如果最大获胜概率至少是 c≤1c \leq 1, 或者至多是 c≥s≥0c \geq s \geq 0 的话, 对应的复杂性类记作 MIP∗(c,s)\mathsf{MIP^*}(c,s); 如果 c−sc-s 是常数, 那么 MIP∗=MIP∗(c,s)\mathsf{MIP^*}=\mathsf{MIP^*}(c,s). Anand Natarajan 和 John Wright 今年的工作 (FOCS 2019 最佳论文奖) 证明了 NEEXP⊆MIP∗\mathsf{NEEXP} \subseteq \mathsf{MIP^*}[6], 这意味着 MIP⊊MIP∗\mathsf{MIP} \subsetneq \mathsf{MIP^*}.

MIPco\mathsf{MIP}^{co}. 上一节中在对易算符模型 (commuting operator model) 上定义了 Cqc\mathcal{C}_{qc}, 对应的复杂性类记作 MIPco\mathsf{MIP}^{co}, 即证明者们共享同一个 Hilbert space, 但是他们的策略是可对易的.

上述三个复杂性类的平凡 (?) 上界分别是 MIP⊆NEXP,MIP∗⊆RE\mathsf{MIP}\subseteq \mathsf{NEXP}, \mathsf{MIP^*}\subseteq \mathsf{RE} 和 MIPco⊆co-RE\mathsf{MIP}^{co}\subseteq \mathsf{co\text{-}RE}. 这里的复杂性类 RE 是递归可枚举 (recursively enumerable, 或称为 Turing recognizable), 即解决这些问题的图灵机会在接受情形 (YES case) 的时候停机, 但是在拒绝情形 (NO case) 下则不一定会停机. 停机问题 (Halting) 是 RE\mathsf{RE}-complete 的. 类似地, 考虑能够被只在 NO case 下保证一定停机的图灵机解决的问题, 这样的复杂性类记作 co-RE\mathsf{co\text{-}RE}.

首先给出经典交互式证明系统上界 MIP⊆NEXP\mathsf{MIP}\subseteq \mathsf{NEXP} 的证明. 注意到验证者可能的提问数量至多是指数的 (因为证明者和验证者之间的通信复杂度至多是多项式的), 对每个问题穷举可能的答案就能找到证明者们的最优策略, 即非确定性指数时间 (NEXP).

然后给出张量积模型 (tensor-product model) 上的量子交互式证明系统的上界 MIP∗⊆RE\mathsf{MIP^*} \subseteq \mathsf{RE} 的证明. 注意到 Cqa\mathcal{C}_{qa} 定义在一系列可数维度 l 的序列上 (Sum-of-squares hierarchy 可以给出更好的刻画), 那么我们可以设计一个图灵机, 先考虑 l=1 的所有量子策略, 再考虑 l≤2l\leq 2 的所有量子策略, 以此类推. 如果存在某个量子策略使得获胜概率为 1 的话 (YES case), 那么图灵机停机并输出接受, 除此之外没有任何保证, 所以在 RE 里.

最后是对易算符模型 (commuting operator model) 上的量子交互式证明系统上界 MIPco⊆co-RE\mathsf{MIP}^{co} \subseteq \mathsf{co\text{-}RE} 的证明. 类似上一段中提到的 Sum-of-squares hierarchy, 这里会用到类似的"对偶"层次, 即 NPA hierarchy [7]. NPA hierarchy 大致定义如下, 即考虑一个序列, 第一个量子关联的集合只涉及玩家甲和玩家乙的量子策略的对易关系中只涉及一个量子比特的, 第二个集合只涉及玩家们的策略的对易关系中至多涉及两个量子比特的, 以此类推. 更详细的介绍可以参考 Jamie Sikora 的关于半正定规划在量子信息中的应用的讲义[8]. 如果没有用到所有的对易约束关系的玩家们的量子策略都不能使得最大获胜概率为 1 的话, 那么显然没有这样的量子策略, 于是这里的图灵机在 NO case (最大获胜概率小于 1) 一定会停机, 即在 co-RE\mathsf{co\text{-}RE} 里.

Tsirelson 问题对计算复杂性理论意味着什么?

如果 Connes’ embedding conjecture 是正确的 (即 Tsirelson 问题的肯定答案), 那么 Cqa=Cqc\mathcal{C}_{qa}=\mathcal{C}_{qc}, 这会导出 MIP∗=MIPco⊆RE∩co-RE=R\mathsf{MIP^*}=\mathsf{MIP}^{co}\subseteq \mathsf{RE}\cap\mathsf{co\text{-}RE}=\mathsf{R}. 这意味着什么呢?

由于 MIP∗\mathsf{MIP^*} 的间隙 c−sc-s 是常数的, 即我们只需要判断最大接受概率至少是 cc, 还是至多是 ss. 上界 co-RE\mathsf{co\text{-}RE} 意味着存在保证停机的图灵机, 可以逐步减少系统可用的纠缠, 找到对应的 cc; 上界 RE\mathsf{RE} 则意味着存在保证停机的图灵机, 可以逐步增加系统可用的纠缠, 找到对应的 ss. 因而可以看出R\mathsf{R} (recursive) 是可判定 (decidable) 语言对应的复杂性类.

于是 Connes’ embedding conjecture 正确会导出 MIP∗\mathsf{MIP^*} 是可判定的. 反之, undecidable 在 MIP∗\mathsf{MIP^*} 中会推翻 Connes’ embedding conjecture. 那么如何证明 undecidable is in MIP∗\mathsf{MIP^*} 呢?

季铮锋在 2016 证明了 MIP* 的 compression theorem, 即 NEEXP⊆MIP∗(c,c−1/exp⁡(n))\mathsf{NEEXP} \subseteq \mathsf{MIP^*}(c,c-1/\exp(n)) [9], 不过"压缩"过程需要两个额外的证明者; 这一工作的后续的改进, 使得在证明者数量保持不变的情况下, 仍然可以完成上述"压缩"过程 [10] – 通过迭代使用 compression theorem, 可以将 NEf(n)XP\mathsf{NE^{f(n)}XP} 放在 c−sc-s 间隙 MIP∗\mathsf{MIP}^* 中, 也就是说 Halting∈MIP∗(1,<1)\mathsf{Halting}\in \mathsf{MIP^*}(1,<1) (William Slofstra 的 Cqa≠Cqs\mathsf{C}_{qa}\neq \mathsf{C}_{qs} 证明 [1:2] 中同样给出了这一结果).

对上述 compression theorem 的进一步改进, 比如说在"压缩"过程中能保持 c-s 间隙不变的话, 那么可以证明 Halting∈MIP∗\mathsf{Halting} \in \mathsf{MIP^*}. 值得一提的是, compression theorem 的证明与 Natarajan-Vidick 在 2018 年证明的 games quantum PCP theorem [11] 毫无关系. 但是 Natarajan-Wright 今年四月份证明的 NEEXP⊆MIP∗\mathsf{NEEXP} \subseteq \mathsf{MIP^*}[6:1] 中用到了

看起来 Natarajan-Wright 给出了证明 gap-preserving compression theorem 的一线曙光, 如果 MIP∗\mathsf{MIP^*} 现有的一系列技术整合的起来的话, 那么就能够证明 RE⊆MIP∗\mathsf{RE} \subseteq \mathsf{MIP^*}, 即推翻 Connes embedding conjecture (并给出对 Tsirelson 问题的否定回答), 进而可以用量子交互式证明系统来验证停机问题.

参考文献

  1. Slofstra, William. “The set of quantum correlations is not closed.” InForum of Mathematics, Pi, vol. 7. Cambridge University Press, 2019. ↩︎ ↩︎ ↩︎

  2. Grilo, Alex B., William Slofstra, and Henry Yuen. “Perfect zero knowledge for quantum multiprover interactive proofs.” arXiv preprint arXiv:1905.11280 (2019). ↩︎

  3. Cleve, Richard, Peter Hoyer, Benjamin Toner, and John Watrous. “Consequences and limits of nonlocal strategies.” In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., pp. 236-249. IEEE, 2004. ↩︎

  4. Slofstra, William. “Tsirelson’s problem and an embedding theorem for groups arising from non-local games.” Journal of the American Mathematical Society (2019). ↩︎

  5. Coladangelo, Andrea, and Jalex Stark. "Unconditional separation of finite and infinite-dimensional quantum correlations."arXiv preprint arXiv:1804.05116(2018). ↩︎

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

  7. Navascués, Miguel, Stefano Pironio, and Antonio Acín. "A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations."New Journal of Physics10, no. 7 (2008): 073013. ↩︎

  8. Jamie Sikora. Semidefinite Programming in Quantum Theory (Lecture Series) ↩︎

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

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

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