绝热量子算法

组合优化问题——如布尔可满足性、最大割、整数规划——的经典求解在大规模实例上普遍遇到困难：目标函数的地貌充满局部极小，贪心与局部搜索会被困住，而精确算法在最坏情形下需要指数时间。绝热量子计算（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 }$、路径导数 $\Vert {\partial }_{s}H\Vert$、以及终态读出的成功概率。“把目标函数写成了 Hamiltonian”只完成了编码，并不构成任何复杂度证明：如果最小能隙随问题规模指数收缩，再漂亮的编码也救不了指数运行时间。本词条教程的目标，就是把这些因素一个个讲清楚：第 1—2 节建立绝热演化的框架与能隙定理，第 3 节用局部 Grover 搜索做一个完整可算的例子，第 4 节用一个可手算的两能级模型展示能隙如何指数收缩，第 5—7 节讨论模型的计算能力与主要瓶颈，第 8 节介绍连续变量的 Quantum Hamiltonian Descent 方案。

预备知识：我们假设读者熟悉量子力学基础（Hamiltonian、Schrödinger 方程、本征值问题）、Grover 搜索与相位估计、以及 QSP/QSVT 的基本语言（）。全篇取 $\hslash =1$。

1. 基本演化与重参数化

取一条光滑的 Hamiltonian 路径

$$H(s),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)⟩=H(s(t))|\psi (t)⟩.$$

这里引入 $s$ 与 $t$ 两层参数是有意为之的”重参数化 (reparametrization)“：路径 $H(s)$ 的形状由问题本身决定，而调度 $s(t)$ 则完全在我们手中——我们可以在能隙大的地方快速通过、在能隙小的地方放慢脚步。第 3 节的局部调度正是利用了这一自由度。

对每个固定的 $s$，$H(s)$ 是一个普通的 Hermitian 算符，可以求解瞬时本征值问题

$$H(s)|k(s)⟩=E_k(s)|k(s)⟩,E_0(s)<E_1(s)\le \cdots ,$$

其中 $|0(s)⟩$ 是瞬时基态，$|1(s)⟩$ 是第一激发态，依此类推。我们要求基态非简并，于是可以定义瞬时基态能隙 (ground gap)

$$\gamma (s)=E_1(s)-E_0(s),{\gamma }_{\min }=\underset{s\in [0,1]}{\min }\gamma (s).$$

算法的目标非常单纯：把系统制备在 $|0(0)⟩$（例如横场 $-{\sum }_i{X}_i$ 的基态 $|+{⟩}^{\otimes n}$），沿路径演化，使末态 $|\psi (T)⟩$ 与目标基态 $|0(1)⟩$ 有足够大的重叠，测量后即得以高概率读出最优解。整个理论的核心问题是：$T$ 需要多大，才能保证”贴着基态走”这件事真的发生？

2. 为什么误差含 $1/{\gamma }^2$

这一节推导绝热定理的核心尺度。分两步：第一步看瞬时基态本身对参数变化有多敏感（静态部分），第二步看真实演化偏离瞬时基态多少（动力学部分）。我们将看到，两个步骤各自贡献一个能隙分母，合起来就是 $1/{\gamma }^2$。

2.1 基态的敏感程度：一阶微扰

把本征方程 $H(s)|0(s)⟩=E_0(s)|0(s)⟩$ 两边对 $s$ 求导。左边用乘积法则，右边同样：

$${\partial }_{s}H|0⟩+H|{\partial }_{s}0⟩={\partial }_s{E}_0|0⟩+E_0|{\partial }_{s}0⟩.$$

这里每一项都是合法的：$H(s)$ 对 $s$ 光滑，本征态在基态非简并时可以取得光滑（简并点附近本征矢可能无法光滑选取，这正是我们要求 $\gamma (s)>0$ 的原因之一）。

用第一激发态以上的某个本征态 $⟨k(s)|$（$k\ge 1$）左乘上式。注意到两个事实：$⟨k|0⟩=0$（本征态正交），以及 $⟨k|H=E_k⟨k|$（Hermitian 算符左乘本征矢）。于是右边第一项 ${\partial }_s{E}_0⟨k|0⟩$ 消失，剩下

$$⟨k|{\partial }_{s}H|0⟩+E_k⟨k|{\partial }_{s}0⟩=E_0⟨k|{\partial }_{s}0⟩.$$

把含 $⟨k|{\partial }_{s}0⟩$ 的两项移到同侧，解出

$$⟨k|{\partial }_{s}0⟩=\frac{⟨k|{\partial }_{s}H|0⟩}{E_0-E_k}.$$

这个公式的含义值得停下来读一下。分子满足 $|⟨k|{\partial }_{s}H|0⟩|\le \Vert {\partial }_{s}H\Vert$（Cauchy—Schwarz 与算符范数的定义），是有界的；分母 $|E_0-E_k|\ge \gamma (s)$。因此基态方向随 $s$ 的变化率被 $1/\gamma$ 放大：能隙越小，基态”转身”越快。从几何上看，$|⟨k|{\partial }_{s}0⟩|$ 正是瞬时基态在射影 Hilbert 空间中沿路径的”速度”在第 $k$ 个激发方向上的分量。

2.2 动力学泄漏：快速相位与分部积分

第二步问：真实的 $|\psi (t)⟩$ 会有多少分量泄漏到激发态？把态按瞬时本征基展开，并把每个分量的快速相位因子显式写出来：

$$|\psi (t)⟩=\sum _k{c}_k(t)e^{-i{\int }_0^t{E}_k(s(t^{\prime }))d{t}^{\prime }}|k(s(t))⟩.$$

将它代入 Schrödinger 方程，左边对三项分别求导（系数、相位、本征态）。相位项求导给出 $-i{E}_k$，与右边 $H|k⟩=E_k|k⟩$ 恰好抵消——这正是我们按绝热相位展开的原因。整理后得到系数 $c_k$ 的常微分方程组：在选取合适的规范（parallel transport gauge，把 $⟨k|{\partial }_{s}k⟩$ 的对角项吸收进相位）之后，

$${\dot{c}}_k=-\sum _{j\ne k}{c}_j\dot{s}⟨k|{\partial }_{s}j⟩e^{i{\int }_0^t(E_k-E_j)d{t}^{\prime }}.$$

初态是 $c_0(0)=1$、$c_{k\ge 1}(0)=0$。只看从基态到第 $k$ 个激发态的直接耦合，并把 2.1 节的微扰公式代入 $⟨k|{\partial }_{s}0⟩$，一阶近似下

$$c_k(T)\approx -{\int }_0^T\dot{s}\frac{⟨k|{\partial }_{s}H|0⟩}{E_0-E_k}{e}^{i{\int }_0^t(E_k-E_0)d{t}^{\prime }}dt.$$

被积函数是”缓变振幅”乘以”快速振荡相位”。振荡相位满足

$$\frac{d}{dt}{e}^{i{\int }_0^t(E_k-E_0)d{t}^{\prime }}=i(E_k-E_0)e^{i{\int }_0^t(E_k-E_0)d{t}^{\prime }},$$

即它平均每振荡一周就把缓变振幅的贡献相互抵消。把这一观察严格化就是分部积分：以上式把指数因子写成导数，做一次分部积分，边界项为

$${\left[\frac{\dot{s}⟨k|{\partial }_{s}H|0⟩}{i(E_k-E_0)(E_0-E_k)}{e}^{i{\int }_0^t(E_k-E_0)d{t}^{\prime }}\right]}_0^T,$$

其大小被

$$\frac{\dot{s}\Vert {\partial }_{s}H\Vert }{{\gamma }^2}$$

控制——注意这里出现了两个能隙分母：一个来自 2.1 节基态导数的微扰公式，另一个来自振荡相位的分部积分。这就是绝热条件中 $1/{\gamma }^2$ 的来源。对匀速调度 $\dot{s}=1/T$，泄漏振幅因此是 $O\left(\frac{\Vert {\partial }_{s}H\Vert }{T{\gamma }^2}\right)$ 量级；要让它小于给定精度 $ϵ$，充分的时间尺度为

$$T\gg \underset{s}{\max }\frac{\Vert {\partial }_{s}H\Vert }{\gamma (s{)}^2}.$$

分部积分剩下的积分项含有被积函数再求一次导数的项，其中出现 ${\partial }_s^{2}H$、边界导数与更多重分部积分产生的更高阶修正。因此严谨的绝热定理有多种版本，结论的幂次依赖假设：

• 不加边界条件、对任意路径都成立的一般界，可以表现为 $T=O(\Vert {\partial }_{s}H{\Vert }^2/(ϵ{\gamma }_{\min }^3))$ 这类含 $1/{\gamma }_{\min }^3$ 的形式（积分项中对振幅再求导会多出一个能隙分母）；
• 若路径在端点处平滑切换（$H(s)$ 的若干阶导数在 $s=0,1$ 处消失，或路径充分光滑并配合边界消去技巧），误差的高阶项被压低，界可以改善到 $\tilde{O}(1/{\gamma }_{\min }^2)$。

所以，只引用一个幂次而不列出定理假设是会误导的：$1/{\gamma }^3$ 与 $\tilde{O}(1/{\gamma }^2)$ 都是正确陈述，区别在于对路径正则性和端点行为的要求。本词条后续讨论中，我们统一以启发式尺度 $T\gg {\max }_s\Vert {\partial }_{s}H\Vert /\gamma (s{)}^2$ 作为估算工具，并在涉及严格结论时注明假设。

3. 局部绝热 Grover 搜索

这是绝热优化最干净的样板间：问题、能隙、调度、运行时间全部可以精确算出来，而且能直接看到”调度设计”如何把 $O(N)$ 压缩回 $O(\sqrt{N})$。

3.1 问题的绝热编码

回到无结构搜索：$N$ 个条目中有唯一的目标条目 $w$，它对应计算基矢 $|w⟩$；预言机可以识别 $w$。定义均匀叠加态

$$|u⟩=\frac{1}{\sqrt{N}}\sum _x|x⟩.$$

取初始与问题 Hamiltonian 为两个投影算符的补：

$$H_0=I-|u⟩⟨u|,H_1=I-|w⟩⟨w|,$$

并沿线性插值路径演化：

$$H(s)=(1-s)H_0+s{H}_1.$$

为什么这样编码？$H_1$ 的基态正是 $|w⟩$（本征值 $0$），其余所有态本征值为 $1$，所以末态基态就是答案本身；$H_1$ 的实现只需要调用一次搜索预言机（对目标项翻转符号），不涉及对 $w$ 的先验知识。$H_0$ 的基态是 $|u⟩$，用 $n$ 个 Hadamard 门即可制备。整条路径因此是”可制备、可实现”的。

3.2 约化到二维子空间并求出能隙

定义未标记条目的均匀态

$$|\bar{u}⟩=\frac{1}{\sqrt{N-1}}\sum _{x\ne w}|x⟩,$$

并把 $|u⟩$ 分解为

$$|u⟩=\frac{1}{\sqrt{N}}|w⟩+\sqrt{\frac{N-1}{N}}|\bar{u}⟩.$$

论断：从 $|u⟩$ 出发的演化始终限制在二维子空间 $\mathrm{span}\{|w⟩,|\bar{u}⟩\}$ 内。理由是：$H(s)=I-(1-s)|u⟩⟨u|-s|w⟩⟨w|$ 只含恒等算符与两个投影，而 $|u⟩$ 本身落在该子空间内，故 $H(s)$ 把子空间映入自身；Schrödinger 演化由 $H(s)$ 生成，初态在子空间内就不会离开。（在子空间的正交补上 $H(s)=I$，只贡献全局相位。）

于是整个问题化为一个 $2\times 2$ 矩阵。在基 $\{|w⟩,|\bar{u}⟩\}$ 下，

$$|w⟩⟨w|=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right),|u⟩⟨u|=\left(\begin{array}{cc}\frac{1}{N}& \frac{\sqrt{N-1}}{N}\\ \frac{\sqrt{N-1}}{N}& \frac{N-1}{N}\end{array}\right),H(s)=I-M(s),$$

其中

$$M(s)=(1-s)|u⟩⟨u|+s|w⟩⟨w|=\left(\begin{array}{cc}s+\frac{1-s}{N}& (1-s)\frac{\sqrt{N-1}}{N}\\ (1-s)\frac{\sqrt{N-1}}{N}& (1-s)\frac{N-1}{N}\end{array}\right).$$

$H(s)$ 的能隙等于 $M(s)$ 两本征值之差（整体减去 $I$ 不改变本征值间距）。对 $2\times 2$ 矩阵，本征值为 ${\lambda }_{\pm }=\frac{1}{2}(\mathrm{tr}M\pm \sqrt{(\mathrm{tr}M{)}^2-4\det M})$，因此

$$\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.$$

行列式（利用 $(\frac{\sqrt{N-1}}{N}{)}^2=\frac{N-1}{N^2}$）：

$$\begin{array}{rl}\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-\frac{1}{N}\right).\end{array}$$

第二行到第三行，后两项完全相同、相互抵消——这不是巧合，而是 $|u⟩$ 与 $|w⟩$ 的内积结构所致。代回：

$$\gamma (s)=\sqrt{1-4\left(1-\frac{1}{N}\right)s(1-s)}.$$

由于 $s(1-s)$ 在 $s=\frac{1}{2}$ 处取最大值 $\frac{1}{4}$，根号内的量在该处最小，故

$${\gamma }_{\min }=\gamma \left(\frac{1}{2}\right)=\sqrt{1-\left(1-\frac{1}{N}\right)}=\frac{1}{\sqrt{N}}.$$

物理解读：在 $s=\frac{1}{2}$ 附近，$|u⟩$ 与 $|w⟩$ 两个投影”势均力敌”，基态从 $|u⟩$ 转向 $|w⟩$，两能级发生最小间隔为 $1/\sqrt{N}$ 的回避交叉（avoided crossing）。这个 $1/\sqrt{N}$ 与 Grover 迭代中每次旋转的角度 $\theta \approx 1/\sqrt{N}$ 是同一个数。

3.3 匀速调度：丢失加速

先用最朴素的匀速调度 $s=t/T$。路径导数为常数

$${\partial }_{s}H=H_1-H_0=|u⟩⟨u|-|w⟩⟨w|,$$

其算符范数有界：$\Vert {\partial }_{s}H\Vert \le \Vert |u⟩⟨u|\Vert +\Vert |w⟩⟨w|\Vert =2$（事实上可算出恰好为 $1$，这里只需常数界）。套用第 2 节的充分条件

$$T\gg \underset{s}{\max }\frac{\Vert {\partial }_{s}H\Vert }{\gamma (s{)}^2}=\frac{\Vert {\partial }_{s}H\Vert }{{\gamma }_{\min }^2}=\Theta (N),$$

得到 $T=O(N)$——与经典随机搜索同阶，Grover 的二次加速完全丢失。原因很清楚：匀速调度要求全程都慢到足以通过最窄的能隙，而最窄能隙 $1/\sqrt{N}$ 只在 $s=\frac{1}{2}$ 附近的极小窗口内出现；在路径的其余部分，能隙是 $\Theta (1)$，完全可以快速通过。

3.4 局部调度：按瞬时能隙变速

Roland—Cerf 的局部绝热条件把第 2 节的逐点约束用到极致：要求在每个时刻，基态的瞬时转动速率都不超过能隙允许的”跟随能力”，即

$$\left|⟨1(s)|\frac{d}{dt}0(s)⟩\right|=\frac{|\dot{s}||⟨1|{\partial }_{s}H|0⟩|}{\gamma (s)}\le ϵ\gamma (s),$$

其中等号用了链式法则 $\frac{d}{dt}|0(s(t))⟩=\dot{s}|{\partial }_{s}0⟩$ 与 2.1 节的微扰公式，$ϵ$ 是控制泄漏振幅的小参数。整理得对调度速度的逐点约束

$$|\dot{s}|\le \frac{ϵ\gamma (s{)}^2}{|⟨1|{\partial }_{s}H|0⟩|}.$$

由于 $|⟨1|{\partial }_{s}H|0⟩|\le \Vert {\partial }_{s}H\Vert =\Theta (1)$，取饱和调度

$$\frac{ds}{dt}=ϵ\gamma (s{)}^2$$

（吸收常数因子到 $ϵ$ 中）。这就是”能隙小处减速、能隙大处加速”的精确形式：在 $s=\frac{1}{2}$ 附近 $\dot{s}\sim ϵ/N$，在两端 $\dot{s}\sim ϵ$。

3.5 总运行时间：逐项积分

由 $dt=ds/\dot{s}$，总时间为

$$T={\int }_0^{T}dt={\int }_0^1\frac{ds}{\dot{s}}=\frac{1}{ϵ}{\int }_0^1\frac{ds}{\gamma (s{)}^2}=\frac{1}{ϵ}{\int }_0^1\frac{ds}{1-4\left(1-\frac{1}{N}\right)s(1-s)}.$$

这个积分可以精确算出。记 $a=1-\frac{1}{N}$，换元 $u=s-\frac{1}{2}$，则 $s(1-s)=\frac{1}{4}-u^2$，分母化为

$$1-4a\left(\frac{1}{4}-u^2\right)=1-a+4a{u}^2=\frac{1}{N}+4a{u}^2.$$

于是

$${\int }_0^1\frac{ds}{\gamma (s{)}^2}={\int }_{-1/2}^{1/2}\frac{du}{\frac{1}{N}+4a{u}^2}=\frac{1}{4a}{\int }_{-1/2}^{1/2}\frac{du}{u^2+\frac{1}{4aN}}.$$

用标准公式 $\int \frac{du}{u^2+b^2}=\frac{1}{b}\arctan \frac{u}{b}$（这里 $b=\frac{1}{2\sqrt{aN}}$）：

$$\frac{1}{4a}\cdot 2\sqrt{aN}{\left[\arctan \left(2\sqrt{aN}u\right)\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{\pi }{2}$ 且 $\frac{N}{\sqrt{N-1}}\to \sqrt{N}$，因此

$$T=\frac{1}{ϵ}\cdot \frac{N}{\sqrt{N-1}}\arctan \sqrt{N-1}=\frac{\pi }{2ϵ}\sqrt{N}(1+o(1))=O\left(\frac{\sqrt{N}}{ϵ}\right).$$

Grover 的二次加速被完整恢复。把复杂度表达式的每个因子交代清楚：$\sqrt{N}$ 来自能隙倒数 $1/{\gamma }_{\min }$（而不是其平方）——逐点调度把全局最坏的 $1/{\gamma }_{\min }^2$ 换成了积分 $\int ds/\gamma (s{)}^2$，而这个积分被宽度 $\sim 1/\sqrt{N}$、深度 $\sim N$ 的窄窗口主导，结果是 $N\cdot \frac{1}{\sqrt{N}}=\sqrt{N}$；$1/ϵ$ 是精度参数的代价，因为泄漏振幅被控制在 $O(ϵ)$。

这个例子的方法论意义超出了搜索本身：绝热运行时间应当积分局部能隙 $\int ds/\gamma (s{)}^2$，而不是永远套用全局最小能隙的粗界 ${\max }_{s}1/\gamma (s{)}^2$。每当能隙剖面中有狭窄的最小值，局部调度都能带来实质收益。

3.6 数值验证

取 $N=4$ 手算一遍。此时 $a=\frac{3}{4}$、$\gamma (s)=\sqrt{1-3s(1-s)}$，${\gamma }_{\min }=\gamma (\frac{1}{2})=\frac{1}{2}=\frac{1}{\sqrt{4}}$，与公式一致。精确积分

$${\int }_0^1\frac{ds}{\gamma (s{)}^2}=\frac{4}{\sqrt{3}}\arctan \sqrt{3}=\frac{4}{\sqrt{3}}\cdot \frac{\pi }{3}=\frac{4\pi }{3\sqrt{3}}\approx 2.418,$$

而渐近公式 $\frac{\pi }{2}\sqrt{N}=\pi \approx 3.142$。再取 $N=2$：积分 $=2\arctan 1=\frac{\pi }{2}\approx 1.571$，渐近值为 $\frac{\pi }{2}\sqrt{2}\approx 2.221$。两个点都精确值低于渐近值且比值趋向 $1$，与 $\arctan \sqrt{N-1}\to \frac{\pi }{2}$ 的收敛一致。

4. 小例子：回避交叉与指数小能隙

上一节的能隙 $1/\sqrt{N}$ 只是多项式地小，局部调度尚能应付。优化问题的真正噩梦是指数小能隙。用一个可以手算的两能级模型（Landau—Zener 模型的参数化形式）看它是怎么出现的：

$$H(s)=\left(s-\frac{1}{2}\right){\sigma }_z+\delta {\sigma }_x=\left(\begin{array}{cc}s-\frac{1}{2}& \delta \\ \delta & \frac{1}{2}-s\end{array}\right),\delta >0.$$

本征值由 $\det (H-\lambda I)={\lambda }^2-(s-\frac{1}{2}{)}^2-{\delta }^2=0$ 解出：

$$E_{\pm }(s)=\pm \sqrt{{\left(s-\frac{1}{2}\right)}^2+{\delta }^2},\gamma (s)=E_{+}-E_{-}=2\sqrt{{\left(s-\frac{1}{2}\right)}^2+{\delta }^2}.$$

• 若 $\delta =0$，两能级在 $s=\frac{1}{2}$ 处直接交叉，$\gamma =0$，基态与激发态交换身份：绝热演化无法定义，因为基态不光滑。
• 若 $\delta >0$，交叉变成回避交叉：${\gamma }_{\min }=2\delta$ 在 $s=\frac{1}{2}$ 处取到。$\delta$ 就是两能级”互相排斥”的耦合强度。

按第 2 节的尺度，$\Vert {\partial }_{s}H\Vert =\Vert {\sigma }_z\Vert =1$，绝热时间 $T\gg \frac{1}{{\gamma }_{\min }^2}=\frac{1}{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⟩$，定义

$$|\Psi ⟩=\frac{1}{\sqrt{T+1}}\sum _{t=0}^T|t⟩\otimes U_t\cdots U_1|x,0⟩.$$

它是”时钟寄存器 $|t⟩$“与”第 $t$ 步的部分计算结果”的均匀叠加。设计一组局域 Hamiltonian 项，每一项检查相邻两个时间片之间是否恰好由 $U_t$ 衔接（传播项），再加上约束输入的项；该 Hamiltonian 的基态恰好是 $|\Psi ⟩$——这就是 Feynman—Kitaev 传播 Hamiltonian。

它的能隙为何只需 $1/\mathrm{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 的所有非对角矩阵元都非正（$⟨x|H|x^{\prime }⟩\le 0$，$x\ne x^{\prime }$），则称它为 stoquastic。这个条件的物理后果由 Perron—Frobenius 型论证给出：对 $-H$ 而言，非对角元全非负，基态可以取成所有振幅非负的矢量。振幅没有符号振荡，路径积分 Monte Carlo 采样时就不会遇到正负贡献剧烈相消的 sign problem，因此 stoquastic 系统是量子退火硬件与量子 Monte Carlo 的天然对象。典型退火机实现的调度形如

$$H(s)=A(s)\left(-\sum _i{X}_i\right)+B(s)H_Z,$$

其中 $-{\sum }_i{X}_i$ 是横场驱动项（非对角元为 $-1$，满足 stoquastic 条件），$H_Z$ 是对角的 Ising 型经典代价函数。$s=0$ 时 $A$ 大、$B$ 小，基态 $|+{⟩}^{\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）逐比特调度、或改走”短路径”避开相变点。这些方法都可能改变能隙剖面，但必须逐实例证明——不存在对所有优化问题普适有效的调度定理。

7. Spectral-gap amplification 与 Markov 问题

有一类方法把经典 Markov 链的结构翻译成 Hamiltonian 能隙，从而获得干净的二次加速。设经典可逆 Markov 链的谱隙为 $\delta$（转移矩阵次大本征值与 $1$ 的距离），它控制链的 mixing 时间 $\sim 1/\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⟩=|b⟩$，可以构造一族 Hamiltonian 路径，使终点基态正比于 $A^{-1}|b⟩$。配合 time-optimal 调度与离散绝热定理（把连续演化离散化并精确控制误差），运行时间可以达到关于条件数 $\kappa$ 的近最优缩放（Zoo 517—518）。需要记住的保留条款与 HHL 类算法相同：输出是量子态 $|x⟩$，而不是完整的经典解向量，读出全部分量会抵消加速。

8. Quantum Hamiltonian Descent

绝热思想也可以搬到连续变量优化。Quantum Hamiltonian Descent（QHD，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 以 $\tilde{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}=ϵ\gamma (s{)}^2$，运行时间积分 $\int ds/\gamma (s{)}^2$；在 Grover 路径上它精确恢复 $O(\sqrt{N}/ϵ)$，而匀速调度只有 $O(N)$。
• AQC 经历史态构造与电路模型多项式等价，历史态能隙只需 $1/\mathrm{poly}(T)$；但该结论不保护任意优化路径，一阶相变可使 ${\gamma }_{\min }=e^{-\Theta (n)}$。
• Stoquastic 退火避开 sign problem 但不等于经典易模拟；spectral-gap amplification 把 Markov 谱隙 $\delta$ 放大为 $\Theta (\sqrt{\delta })$，给 hitting/搜索与绝热线性系统二次或近最优加速。
• Hamiltonian descent 的量子上界（查询复杂度的已证结果）与经典实证（对现有求解器的超多项式观察）应分开陈述，只宜称 empirical separation。

习题

1. （基础）从 $H(s)|0(s)⟩=E_0(s)|0(s)⟩$ 出发，完整推导 $⟨k|{\partial }_{s}0⟩=\frac{⟨k|{\partial }_{s}H|0⟩}{E_0-E_k}$（$k\ge 1$），并说明为什么基态简并会破坏这一推导。
2. （计算）对局部 Grover 路径，验证 $\det M(s)=s(1-s)(1-\frac{1}{N})$，完成积分 ${\int }_0^{1}ds/\gamma (s{)}^2=\frac{N}{\sqrt{N-1}}\arctan \sqrt{N-1}$，并取渐近极限得 $T=O(\sqrt{N}/ϵ)$；再验证匀速调度给出 $T=O(N)$。
3. （计算）对第 4 节的 $H(s)=(s-\frac{1}{2}){\sigma }_z+\delta {\sigma }_x$，求本征态在 $s=\frac{1}{2}$ 处的导数 $⟨1|{\partial }_{s}0⟩$，验证绝热条件 $T\gg 1/(4{\delta }^2)$，并讨论 $\delta =e^{-cn}$ 时运行时间的标度。
4. （概念）解释历史态 Hamiltonian 的能隙为什么只需 $1/\mathrm{poly}(T)$：把时钟方向视为一维链，最低激发模的”半个波长起伏”如何导致 $\Theta (1/T^2)$ 的能隙？这一结论为什么不能套用到任意优化 cost Hamiltonian？
5. （概念）比较 quantum simulated annealing 中的 Markov 谱隙 $\delta$ 与绝热框架中的能量能隙 $\sqrt{\delta }$：平方根关系从哪里来？它对 hitting time 意味着什么？
6. （辨析）QHD 论文（Zoo 529—530）中哪一部分是已证明的复杂度上界、哪一部分是经验观察？为什么后者只能支持 “empirical separation” 的措辞？试举一种可能推翻该分离的经典算法研究方向。

参考文献与 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。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch14-optimization-numerics/adiabatic-optimization
• 内容遵循 CC BY-NC-SA 4.0 许可协议