# 绝热量子算法：能隙定理、局部 Grover 调度与 Hamiltonian Descent 组合优化问题——如布尔可满足性、最大割、整数规划——的经典求解在大规模实例上普遍遇到困难：目标函数的地貌充满局部极小，贪心与局部搜索会被困住，而精确算法在最坏情形下需要指数时间。绝热量子计算（adiabatic quantum computation, AQC）为这类问题提供了一条与众不同的路线：把优化目标编码成一个 Hamiltonian $H(1)$，使得**解就是它的基态**；然后从一个基态容易制备的 Hamiltonian $H(0)$ 出发，让系统随时间缓慢变化。如果演化足够慢，量子态会始终"贴着"瞬时基态走，最终在 $H(1)$ 的基态附近被读出——也就是读出了最优解。 这一思想有两条主要历史线索。一条是 quantum annealing：用横场驱动项帮助系统隧穿出局部极小，后来演化为专用的退火硬件（Zoo 508--509）。另一条是通用 AQC：Aharonov 等人证明绝热模型与标准量子电路模型多项式等价（[quant-ph/0405098](https://arxiv.org/abs/quant-ph/0405098)，Zoo 96--98），因此它原则上不损失任何量子计算能力；与此同时，Roland--Cerf 的局部绝热搜索表明，绝热框架可以精确复现 [Grover 搜索](../ch03-algo-basics/grover.md)的二次加速（Zoo 96--98、185）。 但必须强调：模型等价于电路模型，**不等于**任意优化实例都有加速。一个绝热算法的运行时间由三个因素决定——路径上的最小能隙 $\gamma_{\min}$、路径导数 $\|\partial_s H\|$、以及终态读出的成功概率。"把目标函数写成了 Hamiltonian"只完成了编码，并不构成任何复杂度证明：如果最小能隙随问题规模指数收缩，再漂亮的编码也救不了指数运行时间。本篇教程的目标，就是把这些因素一个个讲清楚：第 1--2 节建立绝热演化的框架与能隙定理，第 3 节用局部 Grover 搜索做一个完整可算的例子，第 4 节用一个可手算的两能级模型展示能隙如何指数收缩，第 5--7 节讨论模型的计算能力与主要瓶颈，第 8 节介绍连续变量的 Quantum Hamiltonian Descent 方案。 **预备知识**：我们假设读者熟悉量子力学基础（Hamiltonian、Schrödinger 方程、本征值问题）、Grover 搜索与相位估计（本站 ch01--ch03）、以及 QSP/QSVT 的基本语言（ch05）。全篇取 $\hbar = 1$。 :::{admonition} 本课知识点 :class: tip 1. **[绝热演化框架与瞬时能隙](#adiabatic-framework-gap)**——能写出 Hamiltonian 路径、调度函数与瞬时本征值问题，定义能隙 $\gamma(s)$ 与 $\gamma_{\min}$，并解释"路径形状"与"通过速度"分层参数化的设计意图。 2. **[绝热条件与误差尺度](#adiabatic-error-scaling)**——能推导一阶微扰公式 $\langle k|\partial_s0\rangle=\frac{\langle k|\partial_sH|0\rangle}{E_0-E_k}$，说明分部积分如何引入第二个能隙分母，并比较不同版本绝热定理的前提差异。 3. **[局部绝热 Grover 搜索](#grover-local-adiabatic)**——能把搜索问题编码为投影 Hamiltonian 路径并在二维子空间中算出 $\gamma_{\min}=1/\sqrt N$，比较匀速调度的 $O(N)$ 与局部调度的 $O(\sqrt N/\epsilon)$ 运行时间。 4. **[回避交叉与指数小能隙](#avoided-crossing-gap)**——能对两能级模型 $H(s)=\left(s-\tfrac12\right)\sigma_z+\delta\sigma_x$ 解出 $\gamma_{\min}=2\delta$，并解释微扰耦合 $\delta=e^{-\Theta(n)}$ 如何导致指数运行时间。 5. **[历史态构造与电路等价](#history-state-equivalence)**——能写出 Feynman--Kitaev 历史态，解释其能隙只需 $1/\operatorname{poly}(T)$ 的波动直觉，并说明该等价性为何不保护一般优化路径。 6. **[Stoquastic 退火与能隙瓶颈](#stoquastic-annealing-bottleneck)**——能写出 stoquastic 条件与典型退火调度，说明它与 sign problem 的关系，并分析一阶相变瓶颈及各类补救手段的限度。 7. **[谱隙放大与 Markov 问题](#spectral-gap-amplification)**——能解释 Markov 谱隙 $\delta$ 如何经相位间隔 $\arccos\lambda$ 放大为 $\Theta(\sqrt\delta)$ 的 Hamiltonian 能隙，并说明它给 hitting/search 带来的二次加速。 8. **[量子 Hamiltonian Descent](#quantum-hamiltonian-descent)**——能写出 QHD 的动能—势能 Hamiltonian 形式并解释其隧穿机制，辨析已证上界与经验性分离两类证据的措辞区别。 ::: (adiabatic-framework-gap)= ## 1. 基本演化与重参数化 取一条光滑的 Hamiltonian 路径 $$ H(s),\qquad s\in[0,1], $$ 其中无量纲参数 $s$ 标记"演化进度"：$s=0$ 对应容易制备基态的初始 Hamiltonian $H(0)$，$s=1$ 对应编码了优化问题答案的**问题 Hamiltonian (problem Hamiltonian)** $H(1)$。物理时间记为 $t\in[0,T]$，二者通过调度函数 $s=s(t)$ 联系，要求 $s(0)=0$、$s(T)=1$。系统的态矢量满足含时 Schrödinger 方程 $$ i\frac{d}{dt}|\psi(t)\rangle =H(s(t))\,|\psi(t)\rangle . $$ 这里引入 $s$ 与 $t$ 两层参数是有意为之的"重参数化 (reparametrization)"：路径 $H(s)$ 的形状由问题本身决定，而调度 $s(t)$ 则完全在我们手中——我们可以在能隙大的地方快速通过、在能隙小的地方放慢脚步。第 3 节的局部调度正是利用了这一自由度。 对每个固定的 $s$，$H(s)$ 是一个普通的 Hermitian 算符，可以求解**瞬时本征值问题** $$ H(s)|k(s)\rangle=E_k(s)|k(s)\rangle,\qquad E_0(s)0$ 的原因之一）。 用第一激发态以上的某个本征态 $\langle k(s)|$（$k\ge1$）左乘上式。注意到两个事实：$\langle k|0\rangle=0$（本征态正交），以及 $\langle k|H=E_k\langle k|$（Hermitian 算符左乘本征矢）。于是右边第一项 $\partial_sE_0\langle k|0\rangle$ 消失，剩下 $$ \langle k|\partial_sH|0\rangle+E_k\langle k|\partial_s0\rangle =E_0\langle k|\partial_s0\rangle . $$ 把含 $\langle k|\partial_s0\rangle$ 的两项移到同侧，解出 $$ \langle k|\partial_s0\rangle =\frac{\langle k|\partial_sH|0\rangle} {E_0-E_k}. $$ 这个公式的含义值得停下来读一下。分子满足 $|\langle k|\partial_sH|0\rangle|\le\|\partial_sH\|$（Cauchy--Schwarz 与算符范数的定义），是有界的；分母 $|E_0-E_k|\ge\gamma(s)$。因此**基态方向随 $s$ 的变化率被 $1/\gamma$ 放大**：能隙越小，基态"转身"越快。从几何上看，$|\langle k|\partial_s0\rangle|$ 正是瞬时基态在射影 Hilbert 空间中沿路径的"速度"在第 $k$ 个激发方向上的分量。 ### 2.2 动力学泄漏：快速相位与分部积分 第二步问：真实的 $|\psi(t)\rangle$ 会有多少分量泄漏到激发态？把态按瞬时本征基展开，并把每个分量的快速相位因子显式写出来： $$ |\psi(t)\rangle=\sum_k c_k(t)\, e^{-i\int_0^t E_k(s(t'))\,dt'}\,|k(s(t))\rangle . $$ 将它代入 Schrödinger 方程，左边对三项分别求导（系数、相位、本征态）。相位项求导给出 $-iE_k$，与右边 $H|k\rangle=E_k|k\rangle$ 恰好抵消——这正是我们按绝热相位展开的原因。整理后得到系数 $c_k$ 的常微分方程组：在选取合适的规范（parallel transport gauge，把 $\langle k|\partial_sk\rangle$ 的对角项吸收进相位）之后， $$ \dot c_k=-\sum_{j\ne k}c_j\,\dot s\, \langle k|\partial_s j\rangle\, e^{i\int_0^t(E_k-E_j)\,dt'} . $$ 初态是 $c_0(0)=1$、$c_{k\ge1}(0)=0$。只看从基态到第 $k$ 个激发态的直接耦合，并把 2.1 节的微扰公式代入 $\langle k|\partial_s0\rangle$，一阶近似下 $$ c_k(T)\approx-\int_0^T \dot s\,\frac{\langle k|\partial_sH|0\rangle}{E_0-E_k}\, e^{i\int_0^t(E_k-E_0)\,dt'}\,dt . $$ 被积函数是"缓变振幅"乘以"快速振荡相位"。振荡相位满足 $$ \frac{d}{dt}e^{i\int_0^t(E_k-E_0)dt'} =i\,(E_k-E_0)\,e^{i\int_0^t(E_k-E_0)dt'}, $$ 即它平均每振荡一周就把缓变振幅的贡献相互抵消。把这一观察严格化就是**分部积分**：以上式把指数因子写成导数，做一次分部积分，边界项为 $$ \left[ \frac{\dot s\,\langle k|\partial_sH|0\rangle} {i\,(E_k-E_0)\,(E_0-E_k)}\, e^{i\int_0^t(E_k-E_0)dt'} \right]_{0}^{T}, $$ 其大小被 $$ \frac{\dot s\,\|\partial_sH\|}{\gamma^2} $$ 控制——注意这里出现了**两个**能隙分母：一个来自 2.1 节基态导数的微扰公式，另一个来自振荡相位的分部积分。这就是绝热条件中 $1/\gamma^2$ 的来源。对匀速调度 $\dot s=1/T$，泄漏振幅因此是 $O\!\left(\frac{\|\partial_sH\|}{T\gamma^2}\right)$ 量级；要让它小于给定精度 $\epsilon$，充分的时间尺度为 $$ T\gg \max_s\frac{\|\partial_sH\|}{\gamma(s)^2}. $$ 分部积分剩下的积分项含有被积函数再求一次导数的项，其中出现 $\partial_s^2H$、边界导数与更多重分部积分产生的更高阶修正。因此严谨的绝热定理有多种版本，结论的幂次依赖假设： - 不加边界条件、对任意路径都成立的一般界，可以表现为 $T=O(\|\partial_sH\|^2/(\epsilon\,\gamma_{\min}^3))$ 这类含 $1/\gamma_{\min}^3$ 的形式（积分项中对振幅再求导会多出一个能隙分母）； - 若路径在端点处平滑切换（$H(s)$ 的若干阶导数在 $s=0,1$ 处消失，或路径充分光滑并配合边界消去技巧），误差的高阶项被压低，界可以改善到 $\widetilde O(1/\gamma_{\min}^2)$。 所以，**只引用一个幂次而不列出定理假设是会误导的**：$1/\gamma^3$ 与 $\widetilde O(1/\gamma^2)$ 都是正确陈述，区别在于对路径正则性和端点行为的要求。本篇后续讨论中，我们统一以启发式尺度 $T\gg\max_s\|\partial_sH\|/\gamma(s)^2$ 作为估算工具，并在涉及严格结论时注明假设。 (grover-local-adiabatic)= ## 3. 局部绝热 Grover 搜索 这是绝热优化最干净的样板间：问题、能隙、调度、运行时间全部可以精确算出来，而且能直接看到"调度设计"如何把 $O(N)$ 压缩回 $O(\sqrt N)$。 ### 3.1 问题的绝热编码 回到无结构搜索：$N$ 个条目中有唯一的目标条目 $w$，它对应计算基矢 $|w\rangle$；预言机可以识别 $w$。定义均匀叠加态 $$ |u\rangle=\frac1{\sqrt N}\sum_x|x\rangle . $$ 取初始与问题 Hamiltonian 为两个投影算符的补： $$ H_0=I-|u\rangle\langle u|,\qquad H_1=I-|w\rangle\langle w|, $$ 并沿线性插值路径演化： $$ H(s)=(1-s)H_0+sH_1 . $$ 为什么这样编码？$H_1$ 的基态正是 $|w\rangle$（本征值 $0$），其余所有态本征值为 $1$，所以末态基态就是答案本身；$H_1$ 的实现只需要调用一次搜索预言机（对目标项翻转符号），不涉及对 $w$ 的先验知识。$H_0$ 的基态是 $|u\rangle$，用 $n$ 个 Hadamard 门即可制备。整条路径因此是"可制备、可实现"的。 ### 3.2 约化到二维子空间并求出能隙 定义未标记条目的均匀态 $$ |\bar u\rangle=\frac1{\sqrt{N-1}}\sum_{x\ne w}|x\rangle , $$ 并把 $|u\rangle$ 分解为 $$ |u\rangle=\frac1{\sqrt N}|w\rangle +\sqrt{\frac{N-1}{N}}\,|\bar u\rangle . $$ **论断**：从 $|u\rangle$ 出发的演化始终限制在二维子空间 $\mathrm{span}\{|w\rangle,|\bar u\rangle\}$ 内。理由是：$H(s)=I-(1-s)|u\rangle\langle u|-s|w\rangle\langle w|$ 只含恒等算符与两个投影，而 $|u\rangle$ 本身落在该子空间内，故 $H(s)$ 把子空间映入自身；Schrödinger 演化由 $H(s)$ 生成，初态在子空间内就不会离开。（在子空间的正交补上 $H(s)=I$，只贡献全局相位。） 于是整个问题化为一个 $2\times2$ 矩阵。在基 $\{|w\rangle,|\bar u\rangle\}$ 下， $$ |w\rangle\langle w|= \begin{pmatrix}1&0\\0&0\end{pmatrix}, \qquad |u\rangle\langle u|= \begin{pmatrix} \frac1N & \frac{\sqrt{N-1}}{N}\\[2pt] \frac{\sqrt{N-1}}{N} & \frac{N-1}{N} \end{pmatrix}, \qquad H(s)=I-M(s), $$ 其中 $$ M(s)=(1-s)|u\rangle\langle u|+s|w\rangle\langle w| = \begin{pmatrix} s+\frac{1-s}{N} & (1-s)\frac{\sqrt{N-1}}{N}\\[2pt] (1-s)\frac{\sqrt{N-1}}{N} & (1-s)\frac{N-1}{N} \end{pmatrix}. $$ $H(s)$ 的能隙等于 $M(s)$ 两本征值之差（整体减去 $I$ 不改变本征值间距）。对 $2\times2$ 矩阵，本征值为 $\lambda_\pm=\frac12\big(\mathrm{tr}\,M\pm\sqrt{(\mathrm{tr}\,M)^2-4\det M}\big)$，因此 $$ \gamma(s)=\lambda_+-\lambda_-=\sqrt{(\mathrm{tr}\,M)^2-4\det M}. $$ 逐项计算。迹： $$ \mathrm{tr}\,M =s+\frac{1-s}{N}+(1-s)\frac{N-1}{N} =s+(1-s)\left(\frac{1}{N}+\frac{N-1}{N}\right) =s+(1-s)=1. $$ 行列式（利用 $\big(\frac{\sqrt{N-1}}{N}\big)^2=\frac{N-1}{N^2}$）： $$ \begin{aligned} \det M &=\left(s+\frac{1-s}{N}\right)(1-s)\frac{N-1}{N} -(1-s)^2\frac{N-1}{N^2}\\ &=s(1-s)\frac{N-1}{N} +(1-s)^2\frac{N-1}{N^2} -(1-s)^2\frac{N-1}{N^2}\\ &=s(1-s)\frac{N-1}{N} =s(1-s)\left(1-\frac1N\right). \end{aligned} $$ 第二行到第三行，后两项完全相同、相互抵消——这不是巧合，而是 $|u\rangle$ 与 $|w\rangle$ 的内积结构所致。代回： $$ \gamma(s)=\sqrt{1-4\left(1-\frac1N\right)s(1-s)}. $$ 由于 $s(1-s)$ 在 $s=\frac12$ 处取最大值 $\frac14$，根号内的量在该处最小，故 $$ \gamma_{\min}=\gamma\!\left(\tfrac12\right) =\sqrt{1-\left(1-\frac1N\right)} =\frac1{\sqrt N}. $$ 物理解读：在 $s=\frac12$ 附近，$|u\rangle$ 与 $|w\rangle$ 两个投影"势均力敌"，基态从 $|u\rangle$ 转向 $|w\rangle$，两能级发生最小间隔为 $1/\sqrt N$ 的回避交叉（avoided crossing）。这个 $1/\sqrt N$ 与 Grover 迭代中每次旋转的角度 $\theta\approx1/\sqrt N$ 是同一个数。 ### 3.3 匀速调度：丢失加速 先用最朴素的匀速调度 $s=t/T$。路径导数为常数 $$ \partial_sH=H_1-H_0=|u\rangle\langle u|-|w\rangle\langle w|, $$ 其算符范数有界：$\|\partial_sH\|\le\||u\rangle\langle u|\|+\||w\rangle\langle w|\|=2$（事实上可算出恰好为 $1$，这里只需常数界）。套用第 2 节的充分条件 $$ T\gg\max_s\frac{\|\partial_sH\|}{\gamma(s)^2} =\frac{\|\partial_sH\|}{\gamma_{\min}^2} =\Theta(N), $$ 得到 $T=O(N)$——与经典随机搜索同阶，Grover 的二次加速完全丢失。原因很清楚：匀速调度要求**全程**都慢到足以通过最窄的能隙，而最窄能隙 $1/\sqrt N$ 只在 $s=\frac12$ 附近的极小窗口内出现；在路径的其余部分，能隙是 $\Theta(1)$，完全可以快速通过。 ### 3.4 局部调度：按瞬时能隙变速 Roland--Cerf 的局部绝热条件把第 2 节的逐点约束用到极致：要求在每个时刻，基态的瞬时转动速率都不超过能隙允许的"跟随能力"，即 $$ \left|\langle 1(s)|\tfrac{d}{dt}0(s)\rangle\right| =\frac{|\dot s|\,\big|\langle1|\partial_sH|0\rangle\big|}{\gamma(s)} \le\epsilon\,\gamma(s), $$ 其中等号用了链式法则 $\frac{d}{dt}|0(s(t))\rangle=\dot s\,|\partial_s0\rangle$ 与 2.1 节的微扰公式，$\epsilon$ 是控制泄漏振幅的小参数。整理得对调度速度的逐点约束 $$ |\dot s|\le \frac{\epsilon\,\gamma(s)^2}{\big|\langle1|\partial_sH|0\rangle\big|}. $$ 由于 $|\langle1|\partial_sH|0\rangle|\le\|\partial_sH\|=\Theta(1)$，取饱和调度 $$ \frac{ds}{dt}=\epsilon\,\gamma(s)^2 $$ （吸收常数因子到 $\epsilon$ 中）。这就是"能隙小处减速、能隙大处加速"的精确形式：在 $s=\frac12$ 附近 $\dot s\sim\epsilon/N$，在两端 $\dot s\sim\epsilon$。 ### 3.5 总运行时间：逐项积分 由 $dt=ds/\dot s$，总时间为 $$ T=\int_0^Tdt=\int_0^1\frac{ds}{\dot s} =\frac1\epsilon\int_0^1\frac{ds}{\gamma(s)^2} =\frac1\epsilon\int_0^1 \frac{ds}{1-4\left(1-\frac1N\right)s(1-s)}. $$ 这个积分可以**精确算出**。记 $a=1-\frac1N$，换元 $u=s-\frac12$，则 $s(1-s)=\frac14-u^2$，分母化为 $$ 1-4a\left(\tfrac14-u^2\right)=1-a+4au^2=\frac1N+4au^2. $$ 于是 $$ \int_0^1\frac{ds}{\gamma(s)^2} =\int_{-1/2}^{1/2}\frac{du}{\frac1N+4au^2} =\frac1{4a}\int_{-1/2}^{1/2}\frac{du}{u^2+\frac1{4aN}}. $$ 用标准公式 $\int\frac{du}{u^2+b^2}=\frac1b\arctan\frac ub$（这里 $b=\frac1{2\sqrt{aN}}$）： $$ \frac1{4a}\cdot 2\sqrt{aN}\, \left[\arctan\!\big(2\sqrt{aN}\,u\big)\right]_{-1/2}^{1/2} =\frac{\sqrt N}{\sqrt a}\arctan\sqrt{aN} =\frac{N}{\sqrt{N-1}}\arctan\sqrt{N-1}. $$ 最后一步代回了 $\sqrt{aN}=\sqrt{N-1}$。当 $N\to\infty$ 时，$\arctan\sqrt{N-1}\to\frac\pi2$ 且 $\frac{N}{\sqrt{N-1}}\to\sqrt N$，因此 $$ T=\frac1\epsilon\cdot\frac{N}{\sqrt{N-1}}\arctan\sqrt{N-1} =\frac{\pi}{2\epsilon}\sqrt N\,\big(1+o(1)\big) =O\!\left(\frac{\sqrt N}{\epsilon}\right). $$ Grover 的二次加速被完整恢复。把复杂度表达式的每个因子交代清楚：$\sqrt N$ 来自能隙倒数 $1/\gamma_{\min}$（而不是其平方）——逐点调度把全局最坏的 $1/\gamma_{\min}^2$ 换成了积分 $\int ds/\gamma(s)^2$，而这个积分被宽度 $\sim1/\sqrt N$、深度 $\sim N$ 的窄窗口主导，结果是 $N\cdot\frac1{\sqrt N}=\sqrt N$；$1/\epsilon$ 是精度参数的代价，因为泄漏振幅被控制在 $O(\epsilon)$。 这个例子的方法论意义超出了搜索本身：**绝热运行时间应当积分局部能隙 $\int ds/\gamma(s)^2$，而不是永远套用全局最小能隙的粗界 $\max_s1/\gamma(s)^2$**。每当能隙剖面中有狭窄的最小值，局部调度都能带来实质收益。 ### 3.6 数值验证 取 $N=4$ 手算一遍。此时 $a=\frac34$、$\gamma(s)=\sqrt{1-3s(1-s)}$，$\gamma_{\min}=\gamma(\frac12)=\frac12=\frac1{\sqrt4}$，与公式一致。精确积分 $$ \int_0^1\frac{ds}{\gamma(s)^2} =\frac{4}{\sqrt3}\arctan\sqrt3 =\frac{4}{\sqrt3}\cdot\frac\pi3 =\frac{4\pi}{3\sqrt3}\approx2.418, $$ 而渐近公式 $\frac\pi2\sqrt N=\pi\approx3.142$。再取 $N=2$：积分 $=2\arctan1=\frac\pi2\approx1.571$，渐近值为 $\frac{\pi}{2}\sqrt2\approx2.221$。两个点都精确值低于渐近值且比值趋向 $1$，与 $\arctan\sqrt{N-1}\to\frac\pi2$ 的收敛一致。 (avoided-crossing-gap)= ## 4. 小例子：回避交叉与指数小能隙 上一节的能隙 $1/\sqrt N$ 只是多项式地小，局部调度尚能应付。优化问题的真正噩梦是**指数小能隙**。用一个可以手算的两能级模型（Landau--Zener 模型的参数化形式）看它是怎么出现的： $$ H(s)=\left(s-\tfrac12\right)\sigma_z+\delta\,\sigma_x = \begin{pmatrix} s-\frac12 & \delta\\ \delta & \frac12-s \end{pmatrix}, \qquad \delta>0. $$ 本征值由 $\det(H-\lambda I)=\lambda^2-(s-\frac12)^2-\delta^2=0$ 解出： $$ E_\pm(s)=\pm\sqrt{\left(s-\tfrac12\right)^2+\delta^2}, \qquad \gamma(s)=E_+-E_-=2\sqrt{\left(s-\tfrac12\right)^2+\delta^2}. $$ - 若 $\delta=0$，两能级在 $s=\frac12$ 处**直接交叉**，$\gamma=0$，基态与激发态交换身份：绝热演化无法定义，因为基态不光滑。 - 若 $\delta>0$，交叉变成**回避交叉**：$\gamma_{\min}=2\delta$ 在 $s=\frac12$ 处取到。$\delta$ 就是两能级"互相排斥"的耦合强度。 按第 2 节的尺度，$\|\partial_sH\|=\|\sigma_z\|=1$，绝热时间 $T\gg\frac{1}{\gamma_{\min}^2}=\frac1{4\delta^2}$。关键点在于：在真实的优化实例中，两个竞争的低能组态往往对应差异悬殊的自旋构型，它们之间的有效耦合 $\delta$ 要经过 $\Theta(n)$ 阶微扰才出现，因此 $\delta=e^{-\Theta(n)}$ 是普遍现象。此时无论定理中的幂次是 $1/\gamma^2$ 还是 $1/\gamma^3$，运行时间都是 $e^{\Theta(n)}$——**定理的幂次只影响指数前的常数，救不了指数本身**。这就是第 6 节将讨论的一阶相变瓶颈的微观图像。 (history-state-equivalence)= ## 5. 与电路模型的等价 绝热模型的能力上限由如下结果刻画：AQC 与标准量子电路模型多项式等价（[quant-ph/0405098](https://arxiv.org/abs/quant-ph/0405098)，Zoo 96--98）。构造的核心是 Feynman--Kitaev 的**历史态 (history state)**。给定一个 $T$ 步电路 $U_T\cdots U_1$ 作用于输入 $|x,0\rangle$，定义 $$ |\Psi\rangle =\frac1{\sqrt{T+1}} \sum_{t=0}^T |t\rangle\otimes U_t\cdots U_1|x,0\rangle . $$ 它是"时钟寄存器 $|t\rangle$"与"第 $t$ 步的部分计算结果"的均匀叠加。设计一组局域 Hamiltonian 项，每一项检查相邻两个时间片之间是否恰好由 $U_t$ 衔接（传播项），再加上约束输入的项；该 Hamiltonian 的基态恰好是 $|\Psi\rangle$——这就是 Feynman--Kitaev 传播 Hamiltonian。 它的能隙为何只需 $1/\operatorname{poly}(T)$？直觉是把时钟方向看成一条长度为 $T+1$ 的一维链：传播项在时钟坐标上相当于离散 Laplacian，合法的历史态对应链上的"均匀波"（零动量模）。一维链上 Laplacian 的激发模式是波长受限的驻波，最低激发态要多出半个波长的起伏，动量 $\sim\pi/T$，能量 $\sim(\pi/T)^2$——这正是 $\Theta(1/T^2)$ 量级的能隙（精确常数依赖具体构造，但幂次是稳健的）。于是从简单的"输入+初始时钟"Hamiltonian 绝热演化到传播/输出 Hamiltonian，所需时间由 $1/\gamma^2\sim T^4$ 这类多项式控制；构造甚至可以限制到二维格点上的局域相互作用。 结论的含义要读准： - **它证明了**：非 stoquastic 的通用绝热模型在计算能力上与 BQP 等价——任何量子电路都能被绝热地模拟，代价是多项式开销。 - **它没有证明**：任意优化 cost Hamiltonian 的绝热路径有多项式能隙。历史态路径是为人造目标精心设计的，其能隙有下界保证；而优化问题的 $H(s)$ 能隙由问题实例决定，不受此定理保护。 (stoquastic-annealing-bottleneck)= ## 6. Stoquastic、Quantum Annealing 与瓶颈 在计算基下，若 Hamiltonian 的所有**非对角矩阵元都非正**（$\langle x|H|x'\rangle\le0$，$x\ne x'$），则称它为 **stoquastic**。这个条件的物理后果由 Perron--Frobenius 型论证给出：对 $-H$ 而言，非对角元全非负，基态可以取成所有振幅非负的矢量。振幅没有符号振荡，路径积分 Monte Carlo 采样时就不会遇到正负贡献剧烈相消的 **sign problem**，因此 stoquastic 系统是量子退火硬件与量子 Monte Carlo 的天然对象。典型退火机实现的调度形如 $$ H(s)=A(s)\left(-\sum_iX_i\right)+B(s)\,H_Z, $$ 其中 $-\sum_iX_i$ 是横场驱动项（非对角元为 $-1$，满足 stoquastic 条件），$H_Z$ 是对角的 Ising 型经典代价函数。$s=0$ 时 $A$ 大、$B$ 小，基态 $|+\rangle^{\otimes n}$ 易制备；$s=1$ 时退化为纯经典问题。 但 **stoquastic 不等于经典易模拟**，两个方向都要小心： - 即使振幅全正，采样链的 mixing 仍可能因拓扑势垒或熵势垒而指数缓慢——"没有 sign problem"只排除了一种具体的数值困难，不排除动力学困难； - Hastings 的构造表明，无 sign problem 的模型仍可能比某些经典路径方法更强，因此也不能反过来说明 stoquastic 系统一定没有量子优势。其精确复杂度类很可能与通用 non-stoquastic AQC 不同，但边界尚未完全划定（Zoo 429、508--509）。 实践中绝热优化最常见的失败模式是第 4 节图像的大规模化：一阶相变伴随的回避交叉使 $$ \gamma_{\min}=e^{-\Theta(n)}, $$ 运行时间随之指数化，与定理中 gap 的幂次无关。已提出的补救手段包括：加入 catalyst 项（在路径中段引入、端点消失的辅助项）、改用 non-stoquastic 驱动、非均匀（inhomogeneous）逐比特调度、或改走"短路径"避开相变点。这些方法都可能改变能隙剖面，但**必须逐实例证明**——不存在对所有优化问题普适有效的调度定理。 (spectral-gap-amplification)= ## 7. Spectral-gap amplification 与 Markov 问题 有一类方法把经典 Markov 链的结构翻译成 Hamiltonian 能隙，从而获得干净的二次加速。设经典可逆 Markov 链的谱隙为 $\delta$（转移矩阵次大本征值与 $1$ 的距离），它控制链的 mixing 时间 $\sim1/\delta$。某些这样的链可以映射到 frustration-free Hamiltonian，其能隙与 $\delta$ 相关；进一步引入辅助比特、构造新的 Hamiltonian，可以把能隙**放大**为 $\Theta(\sqrt\delta)$（Zoo 184、85）。 平方根的直觉与 Szegedy 量子行走一致：经典链的判别矩阵被嵌入一个酉行走算符，经典本征值 $\lambda$ 变成行走相位 $\pm\arccos\lambda$，谱隙 $\delta=1-\lambda_1$ 附近的相位间隔 $\arccos\lambda_1\approx\sqrt{2\delta}$——相位估计能分辨 $\sqrt\delta$ 的相位差，对应能隙 $\Theta(\sqrt\delta)$。对 hitting/search 类问题，这把经典的 $O(1/\delta)$ 改进为绝热/行走意义上的 $O(1/\sqrt\delta)$，与[振幅放大](../ch03-algo-basics/amplitude-amplification.md)中的二次加速同源。 同一个思想也进入了数值线性代数：对线性方程组 $A|x\rangle=|b\rangle$，可以构造一族 Hamiltonian 路径，使终点基态正比于 $A^{-1}|b\rangle$。配合 time-optimal 调度与离散绝热定理（把连续演化离散化并精确控制误差），运行时间可以达到关于条件数 $\kappa$ 的近最优缩放（Zoo 517--518）。需要记住的保留条款与 [HHL 类算法](../ch06-scientific-computing/quantum-linear-solver-tutorial.md)相同：输出是量子态 $|x\rangle$，而不是完整的经典解向量，读出全部分量会抵消加速。 (quantum-hamiltonian-descent)= ## 8. Quantum Hamiltonian Descent 绝热思想也可以搬到连续变量优化。Quantum Hamiltonian Descent（QHD，[2311.00811](https://arxiv.org/abs/2311.00811)，Zoo 529--530）使用形如 $$ H(t)=a(t)(-\Delta)+b(t)f(\hat x) $$ 的 Hamiltonian（或其离散化），其中 $-\Delta$ 是动能项（Laplacian），$f(\hat x)$ 是把经典目标函数直接当作势能的对角算符。机制是绝热退火在连续空间的翻版：演化早期动能项占主导，波包在 $f$ 的地貌上扩散、**隧穿**过势垒（而不是像经典梯度下降那样被局部极小捕获）；随着 $b(t)$ 增大，波包逐步向低势能区域集中，最终测量位置即得近似极小点。 已证明的结果（Zoo 529--530）：对一族特制的 $d$ 维非凸函数——它们含有 $2^d$ 个局部极小，是专为困住经典局部搜索而设计的——QHD 以 $\widetilde O(d^3)$ 次函数查询（function queries）求解。这里复杂度的每个因子都属于**量子算法自身的、在明确查询模型下证明的上界**：$d^3$ 的多项式来自波包演化时间的离散化与查询模拟，波浪线掩盖对数因子。 论文同时对 Gurobi 等代表性经典求解器做了广泛实证，显示它们在该函数族上呈超多项式行为。但必须按证据的性质措辞：经典一侧是**经验性证据而非复杂度下界证明**——没有人证明所有经典算法在该函数族上都需要超多项式时间，只观察到当前最好的通用求解器表现如此。因此正确的说法是 "**plausible / empirical quantum--classical separation**"（可信的、经验性的量子--经典分离），而不能写成"已证明经典算法都需要超多项式时间"。这条措辞纪律对第 6 节的退火瓶颈讨论同样适用：量子加速的论断与经典困难的论断，证据强度必须分别标注。 ## 9. 小结 - 绝热误差有两个来源：瞬时基态导数被 $1/\gamma$ 放大（一阶微扰），动力学泄漏经快速相位分部积分再得一个能隙分母；典型充分尺度含 $1/\gamma^2$，无边界正则性的一般严谨界可到 $1/\gamma_{\min}^3$。引用幂次必须同时引用定理假设。 - 局部调度按瞬时能隙变速，$\dot s=\epsilon\gamma(s)^2$，运行时间积分 $\int ds/\gamma(s)^2$；在 Grover 路径上它精确恢复 $O(\sqrt N/\epsilon)$，而匀速调度只有 $O(N)$。 - AQC 经历史态构造与电路模型多项式等价，历史态能隙只需 $1/\operatorname{poly}(T)$；但该结论不保护任意优化路径，一阶相变可使 $\gamma_{\min}=e^{-\Theta(n)}$。 - Stoquastic 退火避开 sign problem 但不等于经典易模拟；spectral-gap amplification 把 Markov 谱隙 $\delta$ 放大为 $\Theta(\sqrt\delta)$，给 hitting/搜索与绝热线性系统二次或近最优加速。 - Hamiltonian descent 的量子上界（查询复杂度的已证结果）与经典实证（对现有求解器的超多项式观察）应分开陈述，只宜称 empirical separation。 ## 练习题 **练习 1【绝热演化框架与瞬时能隙】**（→ [第 1 节](#adiabatic-framework-gap)） 1. 基础：写出绝热计算的 Hamiltonian 路径 $H(s)$ 与调度函数 $s(t)$ 应满足的边界条件，并给出瞬时能隙 $\gamma(s)$ 与 $\gamma_{\min}$ 的定义。 2. 进阶：解释"路径形状 $H(s)$"与"通过速度 $s(t)$"为什么要作为两层独立的自由度分别设计，并说明算法成功的判据（末态与目标基态的重叠）由哪些量控制。 > 提示：末态只需与 $|0(1)\rangle$ 有足够大的重叠，即可高概率读出最优解。 **练习 2【绝热条件与误差尺度】**（→ [第 2 节](#adiabatic-error-scaling)） 1. 基础：从 $H(s)|0(s)\rangle=E_0(s)|0(s)\rangle$ 出发，完整推导 $\langle k|\partial_s0\rangle=\frac{\langle k|\partial_sH|0\rangle}{E_0-E_k}$（$k\ge1$），并说明为什么基态简并会破坏这一推导。 2. 进阶：指出泄漏振幅 $c_k(T)$ 的估计中出现**两个**能隙分母的位置，分别说明它们来自哪一步推导；再比较一般界 $T=O(\|\partial_sH\|^2/(\epsilon\,\gamma_{\min}^3))$ 与端点平滑时 $\widetilde O(1/\gamma_{\min}^2)$ 各自需要的前提。 > 提示：一个分母在 2.1 节的本征态导数公式里，另一个来自把振荡相位写成导数后的分部积分。 **练习 3【局部绝热 Grover 搜索】**（→ [第 3 节](#grover-local-adiabatic)） 1. 基础：写出局部 Grover 路径的 $H_0=I-|u\rangle\langle u|$ 与 $H_1=I-|w\rangle\langle w|$，说明 $H_1$ 的基态为何就是搜索答案、$H_0$ 的基态为何能用 Hadamard 门制备，并解释演化为何始终限制在二维子空间内。 2. 基础：取 $N=4$，写出 $\gamma(s)$ 并求 $\gamma_{\min}$，再计算积分 $\int_0^1\frac{ds}{\gamma(s)^2}$，并与渐近近似 $\frac{\pi}{2}\sqrt N$ 比较。 3. 进阶：对局部 Grover 路径，验证 $\det M(s)=s(1-s)(1-\frac1N)$，完成积分 $\int_0^1ds/\gamma(s)^2=\frac{N}{\sqrt{N-1}}\arctan\sqrt{N-1}$，并取渐近极限得 $T=O(\sqrt N/\epsilon)$；再验证匀速调度给出 $T=O(N)$。 > 提示：换元 $u=s-\frac12$，再用 $\int\frac{du}{u^2+b^2}=\frac1b\arctan\frac ub$。 **练习 4【回避交叉与指数小能隙】**（→ [第 4 节](#avoided-crossing-gap)） 1. 基础：对 $H(s)=(s-\frac12)\sigma_z+\delta\sigma_x$ 解出本征值 $E_\pm(s)$ 与能隙 $\gamma(s)$，并分别描述 $\delta=0$ 与 $\delta>0$ 时在 $s=\frac12$ 处发生的事情。 2. 进阶：对第 4 节的 $H(s)=(s-\frac12)\sigma_z+\delta\sigma_x$，求本征态在 $s=\frac12$ 处的导数 $\langle1|\partial_s0\rangle$，验证绝热条件 $T\gg1/(4\delta^2)$，并讨论 $\delta=e^{-cn}$ 时运行时间的标度。 > 提示：在 $s=\frac12$ 处 $H=\delta\sigma_x$，把 $\partial_sH=\sigma_z$ 代入一阶微扰公式即可。 **练习 5【历史态构造与电路等价】**（→ [第 5 节](#history-state-equivalence)） 1. 基础：写出 $T$ 步电路 $U_T\cdots U_1$ 的历史态 $|\Psi\rangle$，并说明 Feynman--Kitaev 传播项检查的是相邻时间片之间的什么关系。 2. 进阶：解释历史态 Hamiltonian 的能隙为什么只需 $1/\operatorname{poly}(T)$：把时钟方向视为一维链，最低激发模的"半个波长起伏"如何导致 $\Theta(1/T^2)$ 的能隙？这一结论为什么不能套用到任意优化 cost Hamiltonian？ > 提示：把传播项在时钟基下的矩阵与一维链的离散 Laplacian 对照，低激发模的波长受链长限制。 **练习 6【Stoquastic 退火与能隙瓶颈】**（→ [第 6 节](#stoquastic-annealing-bottleneck)） 1. 基础：写出 stoquastic 条件与典型退火调度 $H(s)=A(s)\left(-\sum_iX_i\right)+B(s)\,H_Z$，并说明为什么 stoquastic Hamiltonian 的基态可取为振幅全非负、从而不遇到 sign problem。 2. 进阶：解释"没有 sign problem"为何不等于"经典易模拟"，并说明一阶相变使 $\gamma_{\min}=e^{-\Theta(n)}$ 时，catalyst 项、non-stoquastic 驱动、非均匀调度等补救手段为什么必须逐实例证明有效。 > 提示：mixing 可因拓扑或熵势垒而指数缓慢；再回忆第 4 节——指数小的能隙使任何幂次的绝热条件都给出指数时间。 **练习 7【谱隙放大与 Markov 问题】**（→ [第 7 节](#spectral-gap-amplification)） 1. 基础：写出经典可逆 Markov 链谱隙 $\delta$ 的定义及其与 mixing 时间 $\sim1/\delta$ 的关系，并说明 spectral-gap amplification 把 frustration-free Hamiltonian 的能隙放大为 $\Theta(\sqrt\delta)$。 2. 进阶：由 $\cos\theta\approx1-\frac{\theta^2}{2}$ 证明 $\arccos(1-\delta)\approx\sqrt{2\delta}$（$\delta$ 小），并解释这一相位间隔如何把 hitting/search 的 $O(1/\delta)$ 改进为 $O(1/\sqrt\delta)$。 3. 进阶：比较 [quantum simulated annealing](../ch13-topology-statistical-physics/quantum-simulated-annealing.md) 中的 Markov 谱隙 $\delta$ 与绝热框架中的能量能隙 $\sqrt\delta$：平方根关系从哪里来？它对 hitting time 意味着什么？ > 提示：相位估计能分辨的最小相位差决定可观测的能隙尺度。 **练习 8【量子 Hamiltonian Descent】**（→ [第 8 节](#quantum-hamiltonian-descent)） 1. 基础：写出 QHD 所用 Hamiltonian $H(t)=a(t)(-\Delta)+b(t)f(\hat x)$ 中动能项与势能项各自的含义，并描述演化早期与晚期波包分别发生什么。 2. 进阶：QHD 论文（Zoo 529--530）中哪一部分是已证明的复杂度上界、哪一部分是经验观察？为什么后者只能支持 "empirical separation" 的措辞？试举一种可能推翻该分离的经典算法研究方向。 > 提示：$\widetilde O(d^3)$ 的查询上界有定理支撑；经典一侧只有对现有求解器的超多项式实证，并无下界证明。 ## 参考文献与 Zoo 覆盖 - Zoo 96--98、185、247：[AQC 等价性](https://arxiv.org/abs/quant-ph/0405098)、局部 Grover 与严谨 adiabatic theorems。 - Zoo 176、179--199、226、406：优化、PageRank、机器学习与图问题实例及 gap 分析。 - Zoo 184、85：spectral gap amplification/Szegedy 联系。 - Zoo 429、508--509：stoquastic 能力与早期 quantum annealing。 - Zoo 517--518：绝热线性系统；Zoo 529--530：[Hamiltonian descent 与实证 separation](https://arxiv.org/abs/2311.00811)。