在本文中, 我会简要解释 randomness extractor 的定义, 再以有限空间中退随机化的例子来引出 classical-proof extractor 的定义, 此后以有限空间量子计算中消除中间测量为例引出 quantum-proof extractor 的定义. 最后我会列举一些有代表性的 seeded extractor 构造, 并指出哪些可以证明是 quantum-proof 的.

这篇打算简单叙述量子算法近年的主要进展 (之一), 即量子奇异值变换 (quantum singular value transform) ^[1]. 故事的起点是这么一件事: 给定某个随机算法, 我们总是可以通过多次重复运行它来提高成功概率. 那么, 我们能尽可能少的重复吗? 量子算法中著名的振幅放大 (amplitude amplification) 技术 ^[2] 可以提供平方时间加速, 这里技术的例子之一就是 Grover 算法 (或者说"无结构搜索"算法).

这个技术做得事情就是在某个圆周上做多次固定角度逆时针旋转, 以期在若干次后到达圆周的顶点. 但这么做有个问题, 就是如果我们并不知道"固定角度"到底是多少的话, 我们并不能直接通过连续多次旋转到达顶点附近 – 直到量子奇异值变换 (quantum singular value transform) 相关技术 ^[3] 的出现解决了这一问题, 方案有些出人意料: 只需要把圆周"撑成"球面, 然后在上面绕着某两个轴交替旋转, 可以证明这样的旋转会在球面的极点附近收敛. 这即是不动点振幅放大 (fixed-point amplitude amplification) ^[4] 技术.

本文介绍了指数时间假设 (ETH) 及其变种 SETH 的两个非典型应用, 一个是说 ETH 可以推出 (近似地) 判断一个量子态是否纠缠没有比准多项式时间更好的算法, 另一个则是说 SETH 可以推出最近格矢量问题 (CVP) 的精确版本没有亚指数时间算法. 说是非典型, 是因为这两个结果都不像通常的 fine-grained complexity 的结果给出问题的低次多项式时间复杂度下界.

本文介绍了对数空间复杂性的一系列基本结果 (Immerman-Szelepcsényi 定理),以及一些对数空间完全问题, 如图论中常见的连通性判断和寻找强连通分量, 还有 2-SAT. 此外, 空间复杂性也和条件数良好的整数矩阵的行列式计算有关. 尽管对于经典多数空间复杂性, 我们只有对数平方空间的算法, 但是这一问题却有量子对数空间算法. 我们有可能证明 NL=L 吗?

自 2003 年 Kobayashi 和 Matsumoto 开始考虑多方量子交互式证明系统 (MIP*) 之后, 直到十七年后的 2020 年初, 人类终于得到了 MIP* 的完全刻画, 即 MIP*=RE. 从计算复杂性的角度来说, 这也意味着我们可以用多方量子交互式证明来验证停机问题, 并且量子纠缠的力量远远超过了我们的想象 (多方经典交互式证明系统的能力与非确定性指数时间相同). 更出人意料的是, 这一结果一并给出了 Tsirelson 问题的否定答案, 即玩家可以共享无穷维纠缠的对易算符模型要比张量积模型强, 以及推翻了算子代数中的 Connes 嵌入猜想. 这应该是计算复杂性理论上世纪七十年代以降最为深刻的结果之一.

William Slofstra 对弱 Tsirelson 问题的否定回答的证明, 出人意料地导出了量子计算复杂性理论的一个令人惊讶的结果: 如果有一个非常精确的量子交互式证明系统, 那么我们可以用它来验证停机问题, 甚至这样的量子交互式证明还可以具有完美零知识证明性质. 那么如果考虑正常的量子交互式证明系统呢, 它能验证停机问题吗? 间隙保持的 MIP* 的压缩定理可以导出这样的结果, 然而它却会推翻算子代数中的 Connes' embedding conjecture (与 Tsirelson 问题等价). 本文会简单地介绍这一量子计算复杂性和算子代数中的深刻联系是如何建立的.

这篇说的是一个关于线路复杂性的结果, 给出了一个问题使得, 量子计算机只需要常数深度量子线路, 而经典计算机至少需要对数深度经典线路. 前者的构造非常简单, 并且有很漂亮的解释 (制备 graph state 并按某种方式测量); 后者是与前者问题中的图相关的下界. 这里的量子优越性的来源是量子非局域性, 换而言之, 对于任何常数深度量子线路, 求解这一问题意味着对应的 GHZ game 的量子策略最大获胜概率为 1 (而经典策略的最大获胜概率则小于 1).

本文是量子 PCP 猜想的系列介绍的最后一篇. 这一篇会带领读者补全指数规模量子 PCP 定理的证明过程. 首先需要解决的问题是, 我们需要什么样的 QMA-complete 问题, 尽管自然的选择是局部哈密顿量问题, 但是借助纠错编码分发"证明"的过程会把我们限制在某些哈密顿量上. 其次, 我们需要的量子交互式证明协议的完备性-可靠性间隙是和输入规模无关的常数, 这意味着我们必须设法把局部哈密顿量问题的精度间隙从逆多项式放大到常数. 此外, 为了得到更高效的规约过程, 我们还需要借助经典 PCP 定理证明中的一系列技术, 比如低次多项式检测来设计更高效的 Pauli braiding testing. 看起来到了这里这系列文章已经尘埃落定了, 可为什么标题仍然是"猜想"而非"定理"呢? 这是因为我们对哈密顿量版本的量子 PCP 猜想 (或者说 robust entanglement) 知之甚少, 这一问题早已并不局限在量子计算复杂性理论本身, 也与凝聚态物理具有深刻联系 (比如拓扑序) -- 尽管我们并不知道这一猜想正确与否, 如果它不是对的, 那么隐藏在这一系列令人惊讶的事实背后的深层原因又会是什么呢?

本文说的是如何用随机行走 (random walk) 和谱图论 (spectral graph theory) 来计算哈密顿量的谱隙 (spectral gap). 谱隙和凝聚态物理中的一系列性质相关, 比如说

• 无谱隙 (gapless) 系统和临界 (critical) 现象, 比如说 ^[1] 中的无阻挫 (frustration-free) 系统;
• 大家猜测某些有谱隙 (gapped) 系统满足面积定律 (area law), 这和哈密顿量基态的纠缠直接相关.
  而从理论计算机科学的观点来看, 谱隙也可以视作下界 (lower bound), 使用纯组合工具来证明似乎也在情理之中. 严格来说, 下文所需的数学基础仅有线性代数和离散数学 (一点图论), 以及熟悉量子信息中的记号 (如 Dirac 符号) 和基本概念 (如哈密顿量和基态).

本文是量子 PCP 猜想的系列介绍的第三篇. 这一篇会给出经典 PCP 定理的一些直觉, 即指数规模的 PCP 定理 -- 也就是说我们有一个指数规模的"证明", 只通过检查常数行, 我们就能以极高的概率判断这一"证明"是否正确. 为了更高效地阅读证明, 我们需要对其编码得到"新证明", 于是要检查"新证明"是否正确编码, 以及编码前的"证明"是否是真的. 在指数规模 PCP 定理中, 我们可以用线性检测来检查编码的正确性, 这也是性质检测的早期结果之一. 那么为什么线性检测是对的呢, 或者说如何证明其可靠性? 通常可以用 Fourier 分析的简单性质可以证明, 不过我们会从群表示论 (特征标理论) 的角度来看待这一证明, 并设法联系 Gowers-Hatami 定理 -- 因而线性检测可以被推广到矩阵值函数上, 进而证明推广后的 Pauli 矩阵的量子线性检测的可靠性. 这也是交互式证明版本的量子 PCP 定理的证明中用到的关键技术之一.

本文量子 PCP 猜想的系列介绍的第二篇. 由于在量子交互式证明中, 证明者(玩家)和验证者(裁判)使用量子态通信并不会带来任何计算能力的提升, 我们只考虑证明者之间共享纠缠态的情形. 这一篇会从不同的角度介绍 entangled games. 其一是从字面椅子考虑, 说明什么是量子策略, 如何定义获胜概率, 以及量子测量会对获胜概率带来哪些优势. 其二则是从证明者们共享的纠缠态的视角, 介绍量子态的自检测 (self-testing), 即如果玩家们的获胜概率是几乎最优的话, 那么他们共享的量子态几乎是极大纠缠态. 有趣的是, 后者有非常漂亮的群(近似)表示论解释, 极大纠缠态的自检测实际上给出了关于 Pauli 矩阵非对易性的性质检测! 这一联系也是 games qPCP theorem 证明中的关键技术之一.

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

前几天正好听了一次 Irit Dinur 的 seminar, 试着写点 UGC 相关的东西. 下面主要介绍 UGC 的来源 ( $\mathsf{NP}$-hardness 和 PCP 定理), 以及和 UGC 直接相关的进展.

这篇会讲一讲积和式 (Permanent) 和 $\mathsf{\#P}$-completeness, 以及玻色采样 (Boson Sampling) 之间的联系.

用以展示量子计算优越性 (quantum conputational supremacy)^[1] 的候选问题有很多, 不过玻色采样 (Boson sampling) 很可能是知名度最高的问题之一. 这一问题的美妙之处在于, 它联系了线性光学和积和式 (permanent), 因为光子 (photon) 在不同的模数 (mode) 上的概率分布, 可以对应到某个积和式上; 而积和式在计算复杂性理论中具有独特的地位, 原因之一是它提供了第一个非平凡的 $\mathsf{\#P}$-complete 问题. 有趣的是, 基于线性光学的技术给出了新的规约手段, 因而一并导出了一些特定类型的矩阵, 即 $GL(n)$,$O(n)$,$U(n)$,$Sp(2n)$ 对应的积和式求值也是 $\mathsf{\#P}$-complete 的^[2].

简单地说, 哈密顿量复杂性是从计算复杂性理论的角度来理解局部哈密顿量 (local Hamiltonian) 和基态 (包括基态本身和基态能量):

• 从计算机科学的角度来看, 这是对约束可满足性问题 (constraint satisfaction problem, $\mathsf{CSP}$) 的进一步推广, 而与之相关的一系列结果 (包括 PCP 定理) 在量子情形下的对应并不平凡;
• 从物理学的角度来看, 它与基态 (也包括激发态) 的纠缠和关联刻画 (比如面积定律) 息息相关, 并在此基础上提供了一系列全新的数值算法 (因而亦与数值模拟相关).

哈密顿量复杂性可以称为“量子计算”在观念上的一次革新, 在此之前大家对量子计算的理解限于量子算法 (如 Shor 算法) 和计算复杂性 (如对量子 Turing 机的正确刻画, 以及刻画量子计算机计算能力的复杂性类 $\mathsf{BQP}$), 在此之后, 则开始将理论计算机科学的思想和工具引入了理论物理 (主要是凝聚态物理), 并出现了一系列令人惊讶的结果.

本文主要参考 Umesh Vazirani 在 Simons Institute 的 talk: Quantum and Post-Quantum Cryptography , 说的是关于从一类非交换隐含子群问题到格密码(LWE)的简短历史, 稍微补充了一些细节. 值得一提的是, Oded Regev 关于使用 Learning with Errors (LWE) 作为困难假设的 Lattice-based cryptography 的工作^[1], 荣膺 2018 年 Gödel Prize.