绝热量子算法：能隙定理、局部 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 等价性、局部 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。