# 绝热量子算法：能隙定理、局部 Grover 调度与 Hamiltonian Descent

绝热量子计算从易制备基态 $H(0)$ 出发，缓慢改变到问题 Hamiltonian $H(1)$。若演化相对瞬时能隙足够慢，状态跟随 ground state。模型与通用量子电路多项式等价，但优化实例是否加速完全取决于最小 gap、路径导数和终态读出；“Hamiltonian 写出来了”并不构成算法复杂度证明。

## 1. 基本演化与重参数化

取光滑路径

$$
H(s),\qquad s\in[0,1],
$$

物理时间 $t\in[0,T]$，$s=s(t)$。Schrödinger 方程

$$
i\frac{d}{dt}|\psi(t)\rangle
=H(s(t))|\psi(t)\rangle.
$$

瞬时本征值

$$
E_0(s)<E_1(s)\le\cdots,
$$

ground gap

$$
\gamma(s)=E_1(s)-E_0(s),\qquad
\gamma_{\min}=\min_s\gamma(s).
$$

目标从 $|0(0)\rangle$ 演化到接近 $|0(1)\rangle$。

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

对本征方程求导，并投影到 excited state $|k(s)\rangle$：

$$
\langle k|\partial_s0\rangle
=\frac{\langle k|\partial_sH|0\rangle}
{E_0-E_k}.
$$

所以 ground state 本身随 $s$ 的变化被 $1/\gamma$ 放大。时间演化中，excited transition amplitude 还要对快速相位

$$
e^{iT\int^s(E_k-E_0)du}
$$

积分分部，再产生一个 gap denominator。典型充分条件尺度

$$
T\gg
\max_s\frac{\|\partial_sH\|}{\gamma(s)^2}
$$

并含 $\partial_s^2H$、边界导数与积分项。一般严谨界可表现为 $1/\gamma_{min}^3$；若端点平滑切换/更强正则性，常改善到 $\widetilde O(1/\gamma_{min}^2)$。只引用一个幂次而不列 theorem assumptions 会误导。

## 3. 局部绝热 Grover 搜索

未知 marked state $|w\rangle$，均匀态

$$
|u\rangle=N^{-1/2}\sum_x|x\rangle.
$$

取

$$
H_0=I-|u\rangle\langle u|,\qquad
H_1=I-|w\rangle\langle w|,
$$

$$
H(s)=(1-s)H_0+sH_1.
$$

动力学限制在 $|w\rangle$ 与未标记均匀态张成的二维子空间，gap

$$
\gamma(s)=
\sqrt{1-4(1-1/N)s(1-s)},
$$

在 $s=1/2$ 最小为 $1/\sqrt N$。

若匀速 $s=t/T$，$1/\gamma_{min}^2$ 给 $T=O(N)$，丢掉 Grover 优势。局部调度在小 gap 处减速：

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

于是

$$
T=\epsilon^{-1}\int_0^1\frac{ds}{\gamma(s)^2}
=O(\sqrt N/\epsilon),
$$

恢复 Grover quadratic speedup。这个例子说明 runtime 应积分局部 gap，而非永远用全局最小 gap 的粗界。

## 4. 与 circuit model 等价

给 circuit $U_T\cdots U_1$，构造 history state

$$
|\Psi\rangle
=\frac1{\sqrt{T+1}}
\sum_{t=0}^T
|t\rangle U_t\cdots U_1|x,0\rangle.
$$

Feynman--Kitaev propagation Hamiltonian 的 ground state 是该 history state，gap 为 $1/\operatorname{poly}(T)$。设计 $H(s)$ 从简单 input-clock Hamiltonian 走到 propagation/output Hamiltonian，即可绝热模拟任意 circuit，甚至限制到二维格局部相互作用。

这证明 non-stoquastic/通用绝热模型与 BQP 等价；它不证明任意优化 cost Hamiltonian 都有多项式 gap。

## 5. Stoquastic、Quantum Annealing 与瓶颈

在计算基中若 off-diagonal entry 非正，Hamiltonian 称 stoquastic；ground state 可取非负振幅，避免传统路径积分 sign problem。许多 quantum annealer 使用

$$
H(s)=A(s)\left(-\sum_iX_i\right)+B(s)H_Z.
$$

Stoquastic 不等于经典易模拟：mixing 可因 topological/entropic barrier 极慢；但其复杂度类与通用 non-stoquastic AQC 可能不同。Hastings 构造展示无 sign problem 模型仍可比某些经典路径方法强，不能简单用“无 sign problem”断言无量子优势。

优化最常见失败是 first-order transition/avoided crossing 导致

$$
\gamma_{min}=e^{-\Theta(n)}.
$$

即使 theorem 只含平方，时间仍指数。Catalyst/non-stoquastic driver、inhomogeneous schedule 或 short path 可能改变 gap，但需逐实例证明。

## 6. Spectral-gap amplification 与 Markov 问题

某些 classical reversible Markov chain 可映到 frustration-free Hamiltonian，其 gap 与 Markov gap $\delta$ 相关。加 ancilla/构造新 Hamiltonian 可把 gap 放大为 $\Theta(\sqrt\delta)$，给 hitting/search 类问题 quadratic adiabatic speedup，类似 Szegedy walk。

线性系统也可构造 ground state 路径，使终态正比 $A^{-1}|b\rangle$；time-optimal schedule 与离散 adiabatic theorem 可达到条件数近最优缩放。输出仍是 quantum state，不是完整经典解向量。

## 7. Quantum Hamiltonian Descent

连续变量方案使用

$$
H(t)=a(t)(-\Delta)+b(t)f(\hat x)
$$

或其离散化，让 wavepacket 在 kinetic term 下隧穿/扩散并向低势能集中。对一族 $d$ 维、含 $2^d$ local minima 的特制非凸函数，QHD 被证明以 $\widetilde O(d^3)$ function queries 求解；论文对 Gurobi 等代表性经典 solver 给出广泛实证，显示 super-polynomial 行为。

但经典下半部是**经验性证据而非复杂度 lower bound**，所以应称“plausible/empirical quantum--classical separation”。不能把它写成已证明经典算法都需超多项式时间。

## 8. 小结与习题

- 绝热误差来自 ground-state 导数与动态相位，典型含 $1/\gamma^2$ 或更保守 gap 幂。
- 局部调度积分 $1/\gamma(s)^2$，在 Grover 路径恢复 $\sqrt N$。
- AQC 可通用模拟 circuits，但优化路径可能有指数小 avoided-crossing gap。
- Hamiltonian descent 的量子上界与经典实证应分开陈述。

1. 推导 $\langle k|\partial_s0\rangle$ 公式。
2. 对局部 Grover gap 完成积分并得 $O(\sqrt N)$。
3. 解释 history-state Hamiltonian 为什么 gap 只需 inverse polynomial。
4. 比较 quantum simulated annealing 的 Markov gap 与 AQC energy gap。

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