绝热量子算法：能隙定理、局部 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，Zoo 96--98），因此它原则上不损失任何量子计算能力；与此同时，Roland--Cerf 的局部绝热搜索表明，绝热框架可以精确复现 Grover 搜索的二次加速（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\)。
本课知识点
绝热演化框架与瞬时能隙——能写出 Hamiltonian 路径、调度函数与瞬时本征值问题，定义能隙 \(\gamma(s)\) 与 \(\gamma_{\min}\)，并解释"路径形状"与"通过速度"分层参数化的设计意图。
绝热条件与误差尺度——能推导一阶微扰公式 \(\langle k|\partial_s0\rangle=\frac{\langle k|\partial_sH|0\rangle}{E_0-E_k}\)，说明分部积分如何引入第二个能隙分母，并比较不同版本绝热定理的前提差异。
局部绝热 Grover 搜索——能把搜索问题编码为投影 Hamiltonian 路径并在二维子空间中算出 \(\gamma_{\min}=1/\sqrt N\)，比较匀速调度的 \(O(N)\) 与局部调度的 \(O(\sqrt N/\epsilon)\) 运行时间。
回避交叉与指数小能隙——能对两能级模型 \(H(s)=\left(s-\tfrac12\right)\sigma_z+\delta\sigma_x\) 解出 \(\gamma_{\min}=2\delta\)，并解释微扰耦合 \(\delta=e^{-\Theta(n)}\) 如何导致指数运行时间。
历史态构造与电路等价——能写出 Feynman--Kitaev 历史态，解释其能隙只需 \(1/\operatorname{poly}(T)\) 的波动直觉，并说明该等价性为何不保护一般优化路径。
Stoquastic 退火与能隙瓶颈——能写出 stoquastic 条件与典型退火调度，说明它与 sign problem 的关系，并分析一阶相变瓶颈及各类补救手段的限度。
谱隙放大与 Markov 问题——能解释 Markov 谱隙 \(\delta\) 如何经相位间隔 \(\arccos\lambda\) 放大为 \(\Theta(\sqrt\delta)\) 的 Hamiltonian 能隙，并说明它给 hitting/search 带来的二次加速。
量子 Hamiltonian Descent——能写出 QHD 的动能—势能 Hamiltonian 形式并解释其隧穿机制，辨析已证上界与经验性分离两类证据的措辞区别。
1. 基本演化与重参数化¶
取一条光滑的 Hamiltonian 路径
其中无量纲参数 \(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 方程
这里引入 \(s\) 与 \(t\) 两层参数是有意为之的"重参数化 (reparametrization)"：路径 \(H(s)\) 的形状由问题本身决定，而调度 \(s(t)\) 则完全在我们手中——我们可以在能隙大的地方快速通过、在能隙小的地方放慢脚步。第 3 节的局部调度正是利用了这一自由度。
对每个固定的 \(s\)，\(H(s)\) 是一个普通的 Hermitian 算符，可以求解瞬时本征值问题
其中 \(|0(s)\rangle\) 是瞬时基态，\(|1(s)\rangle\) 是第一激发态，依此类推。我们要求基态非简并，于是可以定义瞬时基态能隙 (ground gap)
算法的目标非常单纯：把系统制备在 \(|0(0)\rangle\)（例如横场 \(-\sum_iX_i\) 的基态 \(|+\rangle^{\otimes n}\)），沿路径演化，使末态 \(|\psi(T)\rangle\) 与目标基态 \(|0(1)\rangle\) 有足够大的重叠，测量后即得以高概率读出最优解。整个理论的核心问题是：\(T\) 需要多大，才能保证"贴着基态走"这件事真的发生？
2. 为什么误差含 \(1/\gamma^2\)¶
这一节推导绝热定理的核心尺度。分两步：第一步看瞬时基态本身对参数变化有多敏感（静态部分），第二步看真实演化偏离瞬时基态多少（动力学部分）。我们将看到，两个步骤各自贡献一个能隙分母，合起来就是 \(1/\gamma^2\)。
2.1 基态的敏感程度：一阶微扰¶
把本征方程 \(H(s)|0(s)\rangle=E_0(s)|0(s)\rangle\) 两边对 \(s\) 求导。左边用乘积法则，右边同样：
这里每一项都是合法的：\(H(s)\) 对 \(s\) 光滑，本征态在基态非简并时可以取得光滑（简并点附近本征矢可能无法光滑选取，这正是我们要求 \(\gamma(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_s0\rangle\) 的两项移到同侧，解出
这个公式的含义值得停下来读一下。分子满足 \(|\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\) 会有多少分量泄漏到激发态？把态按瞬时本征基展开，并把每个分量的快速相位因子显式写出来：
将它代入 Schrödinger 方程，左边对三项分别求导（系数、相位、本征态）。相位项求导给出 \(-iE_k\)，与右边 \(H|k\rangle=E_k|k\rangle\) 恰好抵消——这正是我们按绝热相位展开的原因。整理后得到系数 \(c_k\) 的常微分方程组：在选取合适的规范（parallel transport gauge，把 \(\langle k|\partial_sk\rangle\) 的对角项吸收进相位）之后，
初态是 \(c_0(0)=1\)、\(c_{k\ge1}(0)=0\)。只看从基态到第 \(k\) 个激发态的直接耦合，并把 2.1 节的微扰公式代入 \(\langle k|\partial_s0\rangle\)，一阶近似下
被积函数是"缓变振幅"乘以"快速振荡相位"。振荡相位满足
即它平均每振荡一周就把缓变振幅的贡献相互抵消。把这一观察严格化就是分部积分：以上式把指数因子写成导数，做一次分部积分，边界项为
其大小被
控制——注意这里出现了两个能隙分母：一个来自 2.1 节基态导数的微扰公式，另一个来自振荡相位的分部积分。这就是绝热条件中 \(1/\gamma^2\) 的来源。对匀速调度 \(\dot s=1/T\)，泄漏振幅因此是 \(O\!\left(\frac{\|\partial_sH\|}{T\gamma^2}\right)\) 量级；要让它小于给定精度 \(\epsilon\)，充分的时间尺度为
分部积分剩下的积分项含有被积函数再求一次导数的项，其中出现 \(\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\) 作为估算工具，并在涉及严格结论时注明假设。
3. 局部绝热 Grover 搜索¶
这是绝热优化最干净的样板间：问题、能隙、调度、运行时间全部可以精确算出来，而且能直接看到"调度设计"如何把 \(O(N)\) 压缩回 \(O(\sqrt N)\)。
3.1 问题的绝热编码¶
回到无结构搜索：\(N\) 个条目中有唯一的目标条目 \(w\)，它对应计算基矢 \(|w\rangle\)；预言机可以识别 \(w\)。定义均匀叠加态
取初始与问题 Hamiltonian 为两个投影算符的补：
并沿线性插值路径演化：
为什么这样编码？\(H_1\) 的基态正是 \(|w\rangle\)（本征值 \(0\)），其余所有态本征值为 \(1\)，所以末态基态就是答案本身；\(H_1\) 的实现只需要调用一次搜索预言机（对目标项翻转符号），不涉及对 \(w\) 的先验知识。\(H_0\) 的基态是 \(|u\rangle\)，用 \(n\) 个 Hadamard 门即可制备。整条路径因此是"可制备、可实现"的。
3.2 约化到二维子空间并求出能隙¶
定义未标记条目的均匀态
并把 \(|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\}\) 下，
其中
\(H(s)\) 的能隙等于 \(M(s)\) 两本征值之差（整体减去 \(I\) 不改变本征值间距）。对 \(2\times2\) 矩阵，本征值为 \(\lambda_\pm=\frac12\big(\mathrm{tr}\,M\pm\sqrt{(\mathrm{tr}\,M)^2-4\det M}\big)\)，因此
逐项计算。迹：
行列式（利用 \(\big(\frac{\sqrt{N-1}}{N}\big)^2=\frac{N-1}{N^2}\)）：
第二行到第三行，后两项完全相同、相互抵消——这不是巧合，而是 \(|u\rangle\) 与 \(|w\rangle\) 的内积结构所致。代回：
由于 \(s(1-s)\) 在 \(s=\frac12\) 处取最大值 \(\frac14\)，根号内的量在该处最小，故
物理解读：在 \(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\|\le\||u\rangle\langle u|\|+\||w\rangle\langle w|\|=2\)（事实上可算出恰好为 \(1\)，这里只需常数界）。套用第 2 节的充分条件
得到 \(T=O(N)\)——与经典随机搜索同阶，Grover 的二次加速完全丢失。原因很清楚：匀速调度要求全程都慢到足以通过最窄的能隙，而最窄能隙 \(1/\sqrt N\) 只在 \(s=\frac12\) 附近的极小窗口内出现；在路径的其余部分，能隙是 \(\Theta(1)\)，完全可以快速通过。
3.4 局部调度：按瞬时能隙变速¶
Roland--Cerf 的局部绝热条件把第 2 节的逐点约束用到极致：要求在每个时刻，基态的瞬时转动速率都不超过能隙允许的"跟随能力"，即
其中等号用了链式法则 \(\frac{d}{dt}|0(s(t))\rangle=\dot s\,|\partial_s0\rangle\) 与 2.1 节的微扰公式，\(\epsilon\) 是控制泄漏振幅的小参数。整理得对调度速度的逐点约束
由于 \(|\langle1|\partial_sH|0\rangle|\le\|\partial_sH\|=\Theta(1)\)，取饱和调度
（吸收常数因子到 \(\epsilon\) 中）。这就是"能隙小处减速、能隙大处加速"的精确形式：在 \(s=\frac12\) 附近 \(\dot s\sim\epsilon/N\)，在两端 \(\dot s\sim\epsilon\)。
3.5 总运行时间：逐项积分¶
由 \(dt=ds/\dot s\)，总时间为
这个积分可以精确算出。记 \(a=1-\frac1N\)，换元 \(u=s-\frac12\)，则 \(s(1-s)=\frac14-u^2\)，分母化为
于是
用标准公式 \(\int\frac{du}{u^2+b^2}=\frac1b\arctan\frac ub\)（这里 \(b=\frac1{2\sqrt{aN}}\)）：
最后一步代回了 \(\sqrt{aN}=\sqrt{N-1}\)。当 \(N\to\infty\) 时，\(\arctan\sqrt{N-1}\to\frac\pi2\) 且 \(\frac{N}{\sqrt{N-1}}\to\sqrt N\)，因此
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}\)，与公式一致。精确积分
而渐近公式 \(\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\) 的收敛一致。
4. 小例子：回避交叉与指数小能隙¶
上一节的能隙 \(1/\sqrt N\) 只是多项式地小，局部调度尚能应付。优化问题的真正噩梦是指数小能隙。用一个可以手算的两能级模型（Landau--Zener 模型的参数化形式）看它是怎么出现的：
本征值由 \(\det(H-\lambda I)=\lambda^2-(s-\frac12)^2-\delta^2=0\) 解出：
若 \(\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 节将讨论的一阶相变瓶颈的微观图像。
5. 与电路模型的等价¶
绝热模型的能力上限由如下结果刻画：AQC 与标准量子电路模型多项式等价（quant-ph/0405098，Zoo 96--98）。构造的核心是 Feynman--Kitaev 的历史态 (history state)。给定一个 \(T\) 步电路 \(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)\) 能隙由问题实例决定，不受此定理保护。
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 的天然对象。典型退火机实现的调度形如
其中 \(-\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 节图像的大规模化：一阶相变伴随的回避交叉使
运行时间随之指数化，与定理中 gap 的幂次无关。已提出的补救手段包括：加入 catalyst 项（在路径中段引入、端点消失的辅助项）、改用 non-stoquastic 驱动、非均匀（inhomogeneous）逐比特调度、或改走"短路径"避开相变点。这些方法都可能改变能隙剖面，但必须逐实例证明——不存在对所有优化问题普适有效的调度定理。
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)\)，与振幅放大中的二次加速同源。
同一个思想也进入了数值线性代数：对线性方程组 \(A|x\rangle=|b\rangle\)，可以构造一族 Hamiltonian 路径，使终点基态正比于 \(A^{-1}|b\rangle\)。配合 time-optimal 调度与离散绝热定理（把连续演化离散化并精确控制误差），运行时间可以达到关于条件数 \(\kappa\) 的近最优缩放（Zoo 517--518）。需要记住的保留条款与 HHL 类算法相同：输出是量子态 \(|x\rangle\)，而不是完整的经典解向量，读出全部分量会抵消加速。
8. Quantum Hamiltonian Descent¶
绝热思想也可以搬到连续变量优化。Quantum Hamiltonian Descent（QHD，2311.00811，Zoo 529--530）使用形如
的 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 节）
基础：写出绝热计算的 Hamiltonian 路径 \(H(s)\) 与调度函数 \(s(t)\) 应满足的边界条件，并给出瞬时能隙 \(\gamma(s)\) 与 \(\gamma_{\min}\) 的定义。
进阶：解释"路径形状 \(H(s)\)"与"通过速度 \(s(t)\)"为什么要作为两层独立的自由度分别设计，并说明算法成功的判据（末态与目标基态的重叠）由哪些量控制。
提示：末态只需与 \(|0(1)\rangle\) 有足够大的重叠，即可高概率读出最优解。
练习 2【绝热条件与误差尺度】（→ 第 2 节）
基础：从 \(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\)），并说明为什么基态简并会破坏这一推导。
进阶：指出泄漏振幅 \(c_k(T)\) 的估计中出现两个能隙分母的位置，分别说明它们来自哪一步推导；再比较一般界 \(T=O(\|\partial_sH\|^2/(\epsilon\,\gamma_{\min}^3))\) 与端点平滑时 \(\widetilde O(1/\gamma_{\min}^2)\) 各自需要的前提。
提示：一个分母在 2.1 节的本征态导数公式里，另一个来自把振荡相位写成导数后的分部积分。
练习 3【局部绝热 Grover 搜索】（→ 第 3 节）
基础：写出局部 Grover 路径的 \(H_0=I-|u\rangle\langle u|\) 与 \(H_1=I-|w\rangle\langle w|\)，说明 \(H_1\) 的基态为何就是搜索答案、\(H_0\) 的基态为何能用 Hadamard 门制备，并解释演化为何始终限制在二维子空间内。
基础：取 \(N=4\)，写出 \(\gamma(s)\) 并求 \(\gamma_{\min}\)，再计算积分 \(\int_0^1\frac{ds}{\gamma(s)^2}\)，并与渐近近似 \(\frac{\pi}{2}\sqrt N\) 比较。
进阶：对局部 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 节）
基础：对 \(H(s)=(s-\frac12)\sigma_z+\delta\sigma_x\) 解出本征值 \(E_\pm(s)\) 与能隙 \(\gamma(s)\)，并分别描述 \(\delta=0\) 与 \(\delta>0\) 时在 \(s=\frac12\) 处发生的事情。
进阶：对第 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 节）
基础：写出 \(T\) 步电路 \(U_T\cdots U_1\) 的历史态 \(|\Psi\rangle\)，并说明 Feynman--Kitaev 传播项检查的是相邻时间片之间的什么关系。
进阶：解释历史态 Hamiltonian 的能隙为什么只需 \(1/\operatorname{poly}(T)\)：把时钟方向视为一维链，最低激发模的"半个波长起伏"如何导致 \(\Theta(1/T^2)\) 的能隙？这一结论为什么不能套用到任意优化 cost Hamiltonian？
提示：把传播项在时钟基下的矩阵与一维链的离散 Laplacian 对照，低激发模的波长受链长限制。
练习 6【Stoquastic 退火与能隙瓶颈】（→ 第 6 节）
基础：写出 stoquastic 条件与典型退火调度 \(H(s)=A(s)\left(-\sum_iX_i\right)+B(s)\,H_Z\)，并说明为什么 stoquastic Hamiltonian 的基态可取为振幅全非负、从而不遇到 sign problem。
进阶：解释"没有 sign problem"为何不等于"经典易模拟"，并说明一阶相变使 \(\gamma_{\min}=e^{-\Theta(n)}\) 时，catalyst 项、non-stoquastic 驱动、非均匀调度等补救手段为什么必须逐实例证明有效。
提示：mixing 可因拓扑或熵势垒而指数缓慢；再回忆第 4 节——指数小的能隙使任何幂次的绝热条件都给出指数时间。
练习 7【谱隙放大与 Markov 问题】（→ 第 7 节）
基础：写出经典可逆 Markov 链谱隙 \(\delta\) 的定义及其与 mixing 时间 \(\sim1/\delta\) 的关系，并说明 spectral-gap amplification 把 frustration-free Hamiltonian 的能隙放大为 \(\Theta(\sqrt\delta)\)。
进阶：由 \(\cos\theta\approx1-\frac{\theta^2}{2}\) 证明 \(\arccos(1-\delta)\approx\sqrt{2\delta}\)（\(\delta\) 小），并解释这一相位间隔如何把 hitting/search 的 \(O(1/\delta)\) 改进为 \(O(1/\sqrt\delta)\)。
进阶：比较 quantum simulated annealing 中的 Markov 谱隙 \(\delta\) 与绝热框架中的能量能隙 \(\sqrt\delta\)：平方根关系从哪里来？它对 hitting time 意味着什么？
提示：相位估计能分辨的最小相位差决定可观测的能隙尺度。
练习 8【量子 Hamiltonian Descent】（→ 第 8 节）
基础：写出 QHD 所用 Hamiltonian \(H(t)=a(t)(-\Delta)+b(t)f(\hat x)\) 中动能项与势能项各自的含义，并描述演化早期与晚期波包分别发生什么。
进阶：QHD 论文（Zoo 529--530）中哪一部分是已证明的复杂度上界、哪一部分是经验观察？为什么后者只能支持 "empirical separation" 的措辞？试举一种可能推翻该分离的经典算法研究方向。
提示：\(\widetilde O(d^3)\) 的查询上界有定理支撑；经典一侧只有对现有求解器的超多项式实证，并无下界证明。
参考文献与 Zoo 覆盖¶
Zoo 96--98、185、247：AQC 等价性、局部 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。