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

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

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

便宜起见, 下面的叙述假设读者知道本科层次计算理论中涉及的一些概念.

计算基态能量: LHP, QMA, 二分定理

“哈密顿量复杂性“这个名词提出的其实很晚 (2010, 见 [1]), 而 Alexei Kitaev 在 1999 年将 Cook-Levin 定理 (33-SAT\mathsf{SAT}是NP\mathsf{NP}-complete ) "量子化"的成功尝试 [2] 之后, 这个领域客观上就已经存在——Kitaev 定义了复杂性类 BQNP\mathsf{BQNP} ( 即 QMA\mathsf{QMA} ) 和局部哈密顿量问题 (local Hamiltonian problem), 并且证明了 55-LHP\mathsf{LHP} 是 QMA\mathsf{QMA}-complete. 这样的成功尝试并不平凡, 其一是因为对于 LHP\mathsf{LHP}, 时间演化的局部约束并不能直接导出全局约束 (多个量子态可以对应于相同的约化密度矩阵); 其二则是 soundness (NO instance 被接受的概率) 的证明需要引入新的技术, 即随机行走 (random walk) 和谱隙的联系. 而这个结果本身也并不平凡——计算局部哈密顿量的局部可观测量的期望值, 在一般情况下即使对量子计算机都是困难的.

局部哈密顿量问题 ( LHP\mathsf{LHP} ) 说的是如何计算基态能量 (或者说是任何局部可观测量的期望值), 对应于经典情形下的约束可满足性问题 ( CSP\mathsf{CSP} )的优化版本 (有多少约束未被满足?). 而计算基态能量 (以及基态本身) 是凝聚态物理的数值模拟中的基本问题之一, 所以讨论模拟量子系统的困难程度是哈密顿量复杂性中的一部分. 在此之后, 很多特定类型的 LHP 所属的复杂性类被讨论, 这里不再赘述, 见 [3]. 类似 CSP, 一个自然的想法是能否建立关于 LHP 的二分定理 (dichotomy theorem), 即用某些参数对具体 LHP 所属的复杂性层次进行分类. Cubitt 和 Montanaro 在 2013 年给出了关于量子比特(d=2d=2)的哈密顿量的 LHP 的二分定理, 它们可能属于 P\mathsf{P} , NP\mathsf{NP}-complete, QMA\mathsf{QMA}-complete 或 Ising\mathsf{Ising}-complete.

计算基态: 面积定律, 张量网络, 随机行走/概率方法

除了基态能量, 如何计算基态也是凝聚态物理中的常见问题之一. 基于 DMRG 的一系列数值算法 (包括后来的张量网络相关算法) 对于一维有谱隙系统非常成功, 但是很长一段时间内没有严格解释. 那么从计算复杂性的角度来看, 很自然的想到两个问题:

  • 这样的物理系统的基态能否被有效地描述 (即参数规模为多项式)?
  • 它们对应的局部哈密顿量问题是否在计算相对容易 (比如在 NP\mathsf{NP} 或 P\mathsf{P} 中)?

第一个问题涉及面积定律(猜想), 即有谱隙系统的纠缠与边界(“面积”)而不是整个系统(“体积”)有关. 基于张量网络方法的一系列构造性证明给出了一部分答案: 如一维面积定律的组合证明 [1:1], 即从乘积态出发用某些算符来制造纠缠, 并同时限制纠缠程度, 使得得到基态满足谱隙和纠缠熵下界; 以及一维有谱隙的局部哈密顿量问题在 P\mathsf{P} 中[4], 这里用到了矩阵乘积态 (matrix product state), 这也给出了第二个问题的部分答案. 而二维面积定律以及相关的计算复杂性结果 (如对应的 LHP∈NP\mathsf{LHP} \in \mathsf{NP}) 至今仍是公开问题, 它的困难之处在于, 我们不知道如何证明这样的基态的有效表示和投影纠缠对态 (projected entangled-pair states) 相关; 而即使这样的有效表示得以证明, 在计算局部可观测量期望值的过程中, 张量网络的有效收缩仍然需要依赖系统的非平凡性质 (一般情形下收缩 PEPS 是 #P\mathsf{\#P}-hard).

而对于无谱隙系统, 比如基态简并情形, 在一维情形下可以证明它们符合对数修正后的面积定律[5]; 并提出了类似重整化群的具有递归结构的算法, 对于部分临界系统的数值模拟结果远好于 DMRG[6], 后者是 2017 年 APS March meeting 的 talk. 除此之外, Peter Shor 等人利用 Markov 链和随机行走等组合/概率方法(计算谱隙和纠缠熵下界), 构造了 spin-1 的无谱隙的无阻挫 (frustration-free) 系统基态[7], 这意味着无阻挫系统的基态也可能有非平凡的纠缠 (spin-1/21/2 的无阻挫系统基态为乘积态).

关于无阻挫系统的另一个有趣结果, 是局部 Lovasz 引理 (local Lovasz lemma) 的量子对应所导出的基态计算算法[8]. 如果我们把局部哈密顿量问题改为判断系统是否无阻挫, 即基态能量是否为0, 这样的问题称为 quantum SAT. 而在经典情形下, 局部 Lovasz 引理的构造性证明给出了求解 SAT 问题的随机算法, 这也是经典结果"量子化"的为数不多的成功尝试之一.

基态能量能被很好地近似吗: 量子 PCP 猜想与拓扑序

PCP 定理, 即概率可检查证明 (probability checkable proof, 或局部可检查证明), 从交互式证明系统的角度重新刻画了 NP\mathsf{NP}, 并在此基础上建立了和不可近似性之间的联系. 对于约束可满足问题, 比如说33-SAT\mathsf{SAT}, 我们知道判定是不是所有的子句(clause)都是满足的是 NP\mathsf{NP}-hard 的; 而 PCP 定理告诉我们, 判定所有子句都是满足的, 还是除了1/1001/100的子句都是满足的仍然是 NP\mathsf{NP}-hard 的. 因而 PCP 定理一度成为证明不可近似性的标准方法, 那么 PCP 定理是否有量子对应呢?

这是一个非常困难的问题, 并且和很多问题有深刻地联系, 限于笔者水平姑且写上一些. 回忆一下比较"传统"的拓扑序 (topological order) 定义, 拓扑序说的是一种全局纠缠性质 (或者说长程纠缠, long-range entanglement). 在上世纪末的一系列关于容错量子计算 (fault-tolerant quantum computation) 的工作中, Alexei Kitaev 在面包圈上的 Toric code 非常引入注目——原因在于如果我们想把 Toric code 的基态变成激发态 (或者从纠错编码的角度看, 想让 codeword 无法被纠正), 仅仅依靠局部扰动是不够的, 这是一种全局纠缠性质. Toric code 满足拓扑序的"传统"定义, 它的基态简并取决于亏格 (genus).

但是后来人们发现, 热力学极限下量子相 (quantum phase) 的等价可以用常数深度 (constant-depth) 量子线路定义, 它被用以刻画长程纠缠. 换而言之, 对于短程纠缠 (short-range entanglement), 这样的基态可以通过对真空态 (或乘积态) 应用常数深度量子线路来制备, 这样的态称为平凡态 (trivial state). 另一个事实则是球面上的 Kitaev model 的基态也具有长程纠缠, 即它不能被常数深度量子线路制备, 但是很明显这里并没有基态简并. 不妨考虑一下常见例子:

  • nn-qubit EPR 对 ∣EPR⟩⊗|EPR\rangle ^{\otimes} 是 trivial state, 显然可以逐对制备.
  • 猫态 12(∣0⟩⊗n+∣1⟩⊗n)\frac{1}{\sqrt{2}}(|0\rangle^{\otimes n}+|1\rangle^{\otimes n}) 是 non-trivial state, 需要深度 Ω(log⁡n)\Omega(\log{n}) 的量子线路制备. 证明较常见, 如 [9] 中的定理 16.

短程纠缠通常被认为是脆弱的, 很容易被退相干或环境噪音等方式破坏. 而长程纠缠则不同, 不能被常数深度量子线路制备, 意味着这些基态是鲁棒的 (称为 robust entanglement). 从 Toric code 和球面上的 Kitaev model 出发, 人们意识到 homological code 的基态往往也是 non-trivial 的.

PCP 定理的量子对应意味着局部哈密顿量 (local Hamiltonian) 的基态能量的近似是困难的, 那么一定存在某些局部哈密顿量使得它的低能态是 non-trivial states, 因为 trivial state 在计算上很容易被用于近似局部可观测量 (local observable) 的期望值——常数深度量子线路意味着因果锥 (causal cone) 非常小. 上述论题就是 Matthew Hastings 提出的 NLTS 猜想 (No Low-energy Trivial State). 它说的是, 如果我们想寻找基态的近似的话 (即 low-energy state), 这些量子态都不能由常数深度 (const-depth) 的量子线路产生. 这和作为纠错编码 (error-correction code)的哈密顿量的基态相关, 因为这些纠错编码在出错情形下不能和基态偏离太多, 也就是说具有足够的鲁棒性 (robust entanglement).

这一猜想的弱化版本被 Eldar 和 Harrow 证明[10], 称为 NLETS 定理. 证明中使用了高维 expander 和代数拓扑中的同调, 即把 Toric code 进一步一般化; 也跟 qLDPC (low-density parity-check) code 相关, 因为直觉上 PCP 定理与纠错编码的局部可检测性 (locally testable) 和局部可解码性 (locally decodable) 相关, 我们想从局部信息中 (以很高的概率) 推断某些全局性质是否存在. 更多的介绍见 Thomas Vidick 的博客 (Quid qPCP?), 以及 Nirkhe-Vazirani-Yuen 今年给出的 NLETS 定理简化证明[11].

上面的介绍没有提及 Toby Cubitt 与可计算性相关的一些工作, 即某些哈密顿量的是否具有谱隙是不可判定问题, 见 Nature 上的进一步介绍[11:1].

总而言之, 哈密顿量复杂性讨论的是, 计算复杂性角度下的局部哈密顿量的基态 (包括低能态) 的一系列性质 (比如能量), 包括它们所属的复杂性类层次 (特定类型的局部哈密顿量具有非平凡的物理意义, 比如有谱隙系统, 无谱隙系统, 子项互相对易的哈密顿量), 以及能否被很好地近似 (与量子纠缠, 拓扑序和纠错编码, 以及交互式证明系统和 quantum game 相关).

参考文献

  1. Aharonov D, Arad I, Landau Z, et al. Quantum Hamiltonian complexity and the detectability lemma[J]. arXiv preprint arXiv:1011.3445, 2010. ↩︎ ↩︎

  2. Kitaev A. Quantum np[J]. Talk at AQIP, 1999, 99. ↩︎

  3. Gharibian S, Huang Y, Landau Z, et al. Quantum hamiltonian complexity[J]. Foundations and Trends® in Theoretical Computer Science, 2015, 10(3): 159-282. ↩︎

  4. Landau Z, Vazirani U, Vidick T. A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians[J]. Nature Physics, 2015, 11(7): 566-569. ↩︎

  5. Arad I, Landau Z, Vazirani U, et al. Rigorous RG algorithms and area laws for low energy eigenstates in 1D[J]. Communications in Mathematical Physics, 2017, 356(1): 65-105. (ITCS 2017) ↩︎

  6. Roberts B, Vidick T, Motrunich O I. Rigorous renormalization group method for ground space and low-energy states of local Hamiltonians[J]. arXiv preprint arXiv:1703.01994, 2017. (APS March meeting 2017) ↩︎

  7. Movassagh R, Shor P W. Power law violation of the area law in quantum spin chains[J]. arXiv preprint arXiv:1408.1657, 2014. (QIP 2015) ↩︎

  8. Gilyén A, Sattath O. On preparing ground states of gapped Hamiltonians: An efficient Quantum Lov’asz Local Lemma[J]. arXiv preprint arXiv:1611.08571, 2016. (FOCS 2017) ↩︎

  9. Watts, Adam Bene, Robin Kothari, Luke Schaeffer, and Avishay Tal. “Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 515-526. 2019. ↩︎

  10. Eldar L, Harrow A W. Local Hamiltonians Whose Ground States are Hard to Approximate[J]. arXiv preprint arXiv:1510.02082, 2015 (FOCS 2017) ↩︎

  11. [1802.07419] Approximate low-weight check codes and circuit lower bounds for noisy ground states ↩︎ ↩︎