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

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

第一稿写于 2018 年 7 月, 主要是 circuit-to-Hamiltonian construction 与随机行走的一系列联系. 第二稿写于 2020 年 2 月, 增加了 circuit-to-Hamiltonian construction 在其他问题中的应用的简单介绍, 包括绝热量子计算的等价性, 低维局部哈密顿量问题 (local Hamiltonian problem) 的困难性, 以及多方量子交互式证明中的压缩 (compression).

下面开始正文.

Markov 链和图论

故事先从 Markov 链的收敛速度和图论中某些量的联系开始.

不妨想象一座城市的路网, 假定这座城市的车辆总数恒定, 并且所有在路上的车辆的车主都想回家. 如果大家都回家是稳定状态的话, 那么什么情况会需要很长时间到达稳定状态? 自然是堵车.

堵车 (图片来自网络)

那堵车可能是怎么造成的呢:

  • 城市中的某个区域里几乎都是写字楼, 大家都想出去, 可是只有很少的人能出去;
  • 在某条干道上大家被堵死了.

这样两种可能性分别对应于 Mark Jerrum 和 Alistair Sinclair 在 1996 年荣膺 Gödel Prize 的工作[2]中, 用图论中的量来刻画 Markov 链的 mixing time (rate) 的两种方法, 分别对应于 conductance 和 maximum edge load (canonical path) [3]. Markov 链的 mixing time, 即在给定初始状态的情况下, 需要多长时间的演化才能使得系统的状态和 Markov 链的稳定状态 (stationary distribution) 足够接近.

而 mixing time 应该如何估计呢? 事实上它的上界和 Markov 链的转移矩阵的逆谱隙, 即 1/(1−λ2)1/(1-\lambda_2) 相关. 等等…既然 Markov 链的转移矩阵和哈密顿量说的都是矩阵, 而且至少都是半正定且对称的, 那它们的谱隙之间不能没有关系吧? 确实有一些人这么想过, 比如 Alexei Kitaev 和 Peter Shor:

  • 前者在证明 kk-局部哈密顿量问题 (local Hamiltonian problem) 是 QMA\mathsf{QMA}-complete 的 soundness 部分时[4], 即不满足的实例对应的哈密顿量的基态能量大于某个常数, 用时间演化对应的 Markov 链上的 conductance 计算谱隙.
  • 后者构造了一系列的无阻挫哈密顿量[1:1], 并从哈密顿量所允许的量子态的演化 (即 Motzkin path 或 Dyck path 的生成规则) 出发构造了一个图, 用图上的随机行走对应的 canonical path 来证明这些哈密顿量是无谱隙的.

如何"量子化"Cook-Levin 定理

下面就说说前者吧, 我会忽略掉大部分细节, 除了与随机行走相关的部分.

Kitaev 关于 kk-LHP\mathsf{LHP} (k≥5k\geq 5) 是 QMA\mathsf{QMA}-complete 是为数不多的把经典证明"量子化"的成功尝试之一. 如果读者熟悉 Cook-Levin 定理的证明的话, 就知道证明 kk-SAT\mathsf{SAT} (k≥3k \geq 3) 是 NP-complete\mathsf{NP}\text{-complete} 是把非确定性 Turing 机的纸带的演化过程, 转换成布尔表达式.

非确定性 Turing 机利用计算历史规约 (图片来自 Wikipedia)

  • 右边是Turing 机的纸带, 表示 Turing 机当前的"状态" (确切地说是 configuration 中的一部分);
  • 演化过程 (即左侧 Step) 中的纸带被按照顺序顺次排列;
  • 纸带在演化的每一步中的变化都是局部的, 如图中的红色圆圈所示部分.

于是呢, 可以看到上面的构造最核心的想法是利用计算历史 (history of computation). 如果我们想把上述证明"量子化"的话, 即构造任意量子线路与 kk-局部哈密顿量问题的对应关系. 我们可以考虑下述基态 ∣η⟩=1T+1∑t=0TUt⋯U1∣x,ξ⟩∣t⟩|\eta\rangle = \frac{1}{\sqrt{T+1}}\sum_{t=0}^T U_t\cdots U_1 |x,\xi\rangle |t\rangle, 其中 xx 是输入, ξ\xi 是用以验证输入是否被接受的证据 (witness), tt 是演化所在的步骤. 因为这里的计算历史是 ∣x⟩∣ξ⟩|x\rangle|\xi\rangle, U1∣x⟩∣ξ⟩U_1|x\rangle|\xi\rangle, U2U1∣x⟩∣ξ⟩U_2U_1|x\rangle|\xi\rangle, ⋯\cdots, Ut⋯U2U1∣x⟩∣ξ⟩U_t\cdots U_2U_1|x\rangle|\xi\rangle.
构造的哈密顿量 (称为 circuit-to-Hamiltonian construction) 类似 Cook-Levin 定理, 即 H=Hin+Hout+HpropH=H_{in}+H_{out}+H_{prop}, 前两项对应于允许的初态和终态; 最后一项对应于允许的演化过程, 即传播项. 传播项 Hprop=∑t=1THprop(t)H_{prop}=\sum_{t=1}^T H_{prop}(t) 限制了允许的演化, 其中从 t−1t-1 到 tt 的演化对应于

Hprop(t)=12(I⊗∣t⟩⟨t∣+I⊗∣t−1⟩⟨t−1∣−Ut⊗∣t⟩⟨t−1∣−Ut†⊗∣t−1⟩⟨t∣).H_{prop(t)}=\frac{1}{2}\left( I\otimes|t\rangle\langle t|+I\otimes|t-1\rangle\langle t-1|-U_t\otimes |t\rangle\langle t-1|-U_t^{\dagger}\otimes |t-1\rangle\langle t| \right).

事实上通过简单的基变换, 我们可以得到 H~prop(t)=12I⊗(∣t⟩−∣t−1⟩)(⟨t∣−⟨t−1∣)\tilde{H}_{prop}(t)=\frac{1}{2}I\otimes\left( |t\rangle-|t-1\rangle \right) \left( \langle t|-\langle t-1| \right), 即投影算符. 不难验证最小的特征值零对应的态是 ∣t⟩+∣t−1⟩2\frac{|t\rangle+|t-1\rangle}{\sqrt{2}}, 也就是说传播项的约束使得基态必须是所有步骤对应的态的均匀叠加.

为了证明 soundness, 即 HH 的基态能量大于某一常数, 我们把其分为 H_1=H_{in}+H_{out} 和 H_2=H_{prop}. 通过一些处理, 这一问题可以转化为计算 H1H_1 和 H2H_2 的次小特征值. 这里我们关心的是 H2H_2, 不妨把基变换后的 H2H_2 写作 H~prop=I⊗A\tilde{H}_{prop} = I\otimes A, 不难得到 A=∑i=0T−1(12−12−1212)i,i+1=I−BA = \sum_{i=0}^{T-1} \begin{pmatrix}\frac{1}{2} & -\frac{1}{2}\\ -\frac{1}{2} & \frac{1}{2}\\ \end{pmatrix}_{i,i+1}=I-B, 其中

B=(12120⋯00012012⋯0000120⋯000⋮⋮⋮⋱⋮⋮⋮000⋯0120000⋯12012000⋯01212).B=\begin{pmatrix} \frac{1}{2} & \frac{1}{2} & 0 & \cdots & 0 & 0 &0 \\ \frac{1}{2} & 0 & \frac{1}{2} & \cdots & 0 & 0 & 0\\ 0 & \frac{1}{2} & 0 & \cdots & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 0 & \frac{1}{2} & 0\\ 0 & 0 & 0 & \cdots & \frac{1}{2} & 0 & \frac{1}{2}\\ 0 & 0 & 0 & \cdots & 0 &\frac{1}{2} & \frac{1}{2}\\ \end{pmatrix}.

上述 BB 是 (T+1)×(T+1)(T+1)\times(T+1) 矩阵. 由于我们讨论的是封闭量子系统下的演化, 即这里的时间演化可逆, 那么量子 Turing 机 (量子线路) 对应的演化过程是时间戳对应的链上的随机行走!

一维链上的随机行走

即上图所对应的 (reversible) Markov 链, 其稳定分布为均匀分布 π=(1T+1,1T+1,⋯,1T+1)\pi=(\frac{1}{\sqrt{T+1}},\frac{1}{\sqrt{T+1}},\cdots,\frac{1}{\sqrt{T+1}}) 对应于 BB 的最大特征值 λ1=1\lambda_1=1.

而 BB 的次大特征值由 Jerrum-Sinclair [2:1] 给出上界 1−λ2≥Φ2/21-\lambda_2\geq \Phi^2/2, 其中 ϕ\phi 是前文中提到的 conductance. 上述链的 conductance 为 1T+1\frac{1}{T+1}, 代入即得 AA 的次小特征值.

本节中关于 Kitaev 的证明中最关键的想法的叙述到此为止. 即把量子线路对应的封闭量子系统的演化, 用时间戳对应的链上的随机行走描述. 进而借助其对应的 Markov 链的性质, 得到所构造的哈密顿量的谱隙.

回到 Conductance

下面来说一说 conductance 的定义和计算.

先回到图上的随机行走和 Markov 链. 什么样的图对应的 Markov 链的演化能使其非常快地接近稳定状态呢? 更形式化一些, rapidly mixing, 即即使 Markov 链所在的空间是指数规模的, 我们仍然只需要多项式规模的时间就可以从任意初态到达稳定状态.

答案之一是 expander graph, 顾名思义, 它描述了一类很容易"扩展"的图 G=(V,E)G=(V,E). 比如说, 它的定义之一就是关于 expansion ϕ(G)=min⁡S⊂V,∣S∣≤n/2∣∂S∣∣S∣\phi(G) = \min_{S \subset V, |S|\leq n/2} \frac{|\partial S|}{|S|}, 即顶点的子集 SS 中的点通过割边跳转到子集外的点的容易程度, ∂S\partial S 即端点分别在 SS 和 Sˉ\bar{S} 上的边的集合.

注意到上述定义中 SS 里的每个顶点的权重相同. 如果这样的图对应一个 Markov 链的话, 考虑它的稳定分布 π\pi 作为权重, 再把割边对应于 Markov 链的转移矩阵 PP, 可以得到

Φ=min⁡0<∣S∣<N,Cs≤1/2∑x∈S,y∈SˉP(x,y)π(x)∑x∈Sπ(x).\Phi=\min_{0< |S| < N, C_s\leq 1/2} \frac{\sum_{x\in S, y\in \bar{S}} P(x,y) \pi(x)}{\sum_{x\in S} \pi(x)}.

上式中分子是各态历经流 (ergodic flow) 的和, 分母则可以视为容量. 此外, 上式也可以视为条件概率, 即给定的初始位置在子集 S⊆VS \subseteq V 中, 下一步逃出集合 SS 的概率.

可上面的 conductance 是如何跟转移矩阵发生联系的呢?

这与矩阵的特征值和 Rayleigh 商的关系有关, 即如果矩阵的最大特征值对应的特征对是 (λ1,v1)(\lambda_1, v_1) 的话, 那么 λ1=max⁡x∈RnxTAxxTx,λ2=max⁡x⊥v1xTAxxTx,⋯.\lambda_1 = \max_{x\in \mathbb{R}^n} \frac{x^T A x}{x^T x}, \lambda_2=\max_{x \perp v_1} \frac{x^T A x}{x^T x}, \cdots.

进一步地, 如果 AA 对应于图 G=(V,E)G=(V,E) 的邻接矩阵的话, 那么可以定义图 GG 的 Laplacian L=dI−AL=dI-A. 为了便宜起见, 这里假定图 GG 是 regular graph, 即其中所有顶点的度相同. 那么通过简单地计算可以得到下述 Rayleigh 商 (分子是关于 Laplacian 的二次型):

d−λ2=min⁡x⊥v1xTLxxTx=min⁡x⊥v1∑(u,v)∈E(xu−xv)2∑v∈Vxv2.d-\lambda_2=\min_{x\perp v_1}\frac{x^T L x}{x^T x}=\min_{x \perp v_1} \frac{\sum_{(u,v)\in E}(x_u-x_v)^2}{\sum_{v\in V} x_v^2}.

比较上述次大(小)特征值的变分刻画和 conductance 的定义, 通过一些计算和放缩, 可以得到 Jerrum-Sinclair [2:2] 中关于次大(小)特征值的上下界:

1−2Φ≤λ2≤1−Φ2/2.1-2\Phi \leq \lambda_2 \leq 1-\Phi^2/2.

不难发现, 右侧部分即为前一节中证明所需. 另外, conductance 和谱隙的联系也并非巧合, 事实上 expander graph 的另一个等价定义就是基于图的邻接矩阵的谱隙的; 而上式在谱图论 (spectral graph theory) 中也有类似的结果, 称为 Cheeger 不等式.

简而言之, 本节的讨论意味着

  • 一方面, 我们通过边的 expansion 和图上随机行走对应的 Markov 链, 把 expansion 的定义加权得到了 conductance, 并有了新的概率解释;
  • 另一方面, 我们通过对次大(小)的特征值的变分刻画, 以及图 Laplacian 得到了类似的 Rayleigh 商形式.
    从而就可以用图论中 conductance 来刻画 Markov 链的谱隙, 进而刻画了 Markov 链的 mixing rate.

计算历史态: 量子 Cook-Levin 定理之外

这一节我会非常简略的介绍一下 circuit-to-Hamiltonian construction 的改进以及其他应用, 包括如何证明绝热量子计算和通用量子计算等价 [5], 如何证明一维的局部哈密顿量问题对于量子计算来说仍然是困难的[6], 以及如何用 non-local game 来验证多方量子交互式证明[7][8].

绝热量子计算的强与弱

首先是证明绝热量子计算 (adiabatic quantum computation) 是 BQP\mathsf{BQP}-complete 的[5:1].

绝热量子计算是说, 有一个绝热演化的过程可以写成含时哈密顿量 H(t)=T−tTHstart+tTHfinal,0≤t≤1H(t)=\frac{T-t}{T} H_{start} + \frac{t}{T} H_{final}, 0 \leq t \leq 1. 也就是说, 随着缓慢的绝热演化, 当前系统对应的态会逐渐从 HstartH_{start} 的基态变成 HfinalH_{final} 的基态. 绝热定理告诉我们, 演化的最终态会接近于 HfinalH_{final} 的基态的条件是, 演化速度只要要和 Ω(∥Hfinal−Hstart∥/Δ(H(t)))\Omega(\|H_{final}-H_{start}\|/\Delta(H(t))) 一样慢, 其中 Δ(H(t))\Delta(H(t)) 是 H(t)H(t) 的谱隙 (spectral gap). 换而言之, 如果我们想在多项式时间内完成绝热量子计算的话, 那么 H(t)H(t) 在任何时刻的谱隙都应该至少是逆多项式的.

怎么证明 BQP\mathsf{BQP}-hardness 呢? [5:2] 中的主要想法是利用前文中的 circuit-to-Hamiltonian construction, 考虑构造 Hstart:=Hin+HoutH_{start}:= H_{in}+H_{out}, 以及 Hfinal:=HpropH_{final}:=H_{prop}. 也就是说绝热演化的初态是 ∣ψstart⟩|\psi_{start}\rangle =∣00⋯0⟩=|00\cdots 0\rangle∣00⋯0⟩|00 \cdots 0 \rangle, 而终态则是 ∣ψfinal⟩=1T+1∑t=0TUt⋯U0∣00⋯0⟩∣t⟩|\psi_{final}\rangle = \frac{1}{\sqrt{T+1}}\sum_{t=0}^T U_t\cdots U_0 |00\cdots 0\rangle|t\rangle. 于是在设法使得 H(t)H(t) 的基态 (ground state) 唯一的情况下, 我们可以类似 [4:1] 中的技术证明 Δ(H(t))≥12(T+1)2\Delta(H(t)) \geq \frac{1}{2(T+1)^2}.

低维局部哈密顿量问题的困难性

除此之外, [5:3] 中的另一个贡献是证明了局部哈密顿量问题即使在二维的时候仍然是 QMA\mathsf{QMA}-complete 的.

不难验证 circuit-to-Hamiltonian construction 中的大部分都是一维的, 除了传播项 HpropH_{prop} 中的时钟 (clock). 时钟通常用一进制 (unary) 串来表示, 即长度为 TT 的比特串的前 tt 位为 11, 后面都是 00. 通过使用更大的字母表 (不只是量子比特), 并设计更精巧的传播项, 我们可以设法把得到的哈密顿量中检查时钟是否合法的部分限制在二维平面上.

可是既然得到的哈密顿量中除了传播项都是一维的, 我们能证明局部哈密顿量问题在一维的时候, 甚至在平移不变的时候也是一样难吗? 平移不变意味着哈密顿量中的每一项都一样, 只是所在的位置不同, 这意味着问题的难度仅仅和输入规模有关, 甚至和具体输入无关. [6:1] 证明了如果输入规模可以表示成多项式规模的比特串 (这意味着哈密顿量在指数长的链上) 的话, 那么这样的平移不变的一维局部哈密顿量问题是 QMAEXP\mathsf{QMA_{EXP}}-complete 的. 这个时候的传播项的更新过程非常像图灵机的读写过程. 如果设法将这一技术应用在无限大的网格上, 比如说考虑能量密度 (energy density), 即网格上的每一小块的能量, 那么甚至可以导出二维哈密顿量的谱隙是否和体系规模无关是不可判定 (undeciable) 的[9].

如何压缩 (多方) 量子交互式证明

无独有偶, 用计算历史态 (history state) 来处理 BQP\mathsf{BQP}-complete 问题的想法, 也不仅出现在绝热量子计算中. 这一想法也出现在用几乎经典的交互式证明来验证量子计算的结果中, 如代表性的 post-hoc verification [10], 限于篇幅这里不再展开. 甚至还可以用在 (多方) 量子交互式证明中, 把证明者们和验证者之间发送的信息, 看成是他们在自己手里的量子比特们和公共的量子比特上的计算过程.

譬如说, 证明者给验证者发送一条信息, 相当于证明者在自己的量子比特们和公共部分的量子比特上作用很复杂的量子线路; 而验证者给证明者发送信息同理. 这一系列"计算"过程同样可以用计算历史态写出, 而 circuit-to-Hamiltonian construction 得到的哈密顿量的每一项, 提供了验证这一计算历史态的天然方式. 这就是多方量子交互式证明中的压缩 (compression) 技术 [7:1][8:1] 的主要想法. 但是证明者的测量可能对应于非常负责的运算, 验证者除了迫使证明者们验证之外别无他法, 目前已知的办法只有让两个证明者们共享纠缠, 然后利用类似 CHSH game (更多介绍见 [11]) 的方式验证他们是否做了正确的测量.

参考文献

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

  2. Sinclair A, Jerrum M. Approximate counting, uniform generation and rapidly mixing Markov chains[J]. Information and Computation, 1989, 82(1): 93-133. ↩︎ ↩︎ ↩︎

  3. Sinclair A. Improved bounds for mixing rates of Markov chains and multicommodity flow[J]. Combinatorics, probability and Computing, 1992, 1(4): 351-370. ↩︎

  4. Aharonov D, Naveh T. Quantum NP-a survey[J]. arXiv preprint quant-ph/0210077, 2002. ↩︎ ↩︎

  5. Aharonov, D., W. van Dam, Z. Landau, S. Lloyd, J. Kempe, and O. Regev. “Universality of Adiabatic quantum computation.” In Proceedings of 45th FOCS. 2004. ↩︎ ↩︎ ↩︎ ↩︎

  6. Gottesman, Daniel, and Sandy Irani. “The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems.” In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 95-104. IEEE, 2009. ↩︎ ↩︎

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

  8. Fitzsimons, Joseph, Zhengfeng Ji, Thomas Vidick, and Henry Yuen. “Quantum proof systems for iterated exponential time, and beyond.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 473-480. 2019. ↩︎ ↩︎

  9. Cubitt, Toby S., David Perez-Garcia, and Michael M. Wolf. “Undecidability of the spectral gap.” Nature 528, no. 7581 (2015): 207-211. ↩︎

  10. Fitzsimons, Joseph F., Michal Hajdušek, and Tomoyuki Morimae. “Post hoc verification of quantum computation.” Physical review letters 120, no. 4 (2018): 040501. ↩︎

  11. 量子 PCP 猜想浅说 (二): 量子纠缠的交互式证明验证 ↩︎