离散绝热方法（Discrete Adiabatic Method）是将连续绝热量子计算（AQC）转化为可在量子门电路上实现的离散算法的关键技术。它桥接了”绝热演化”这一物理概念与”量子电路”这一计算模型，使得绝热思想可以在通用量子计算机上实现。

绝热量子计算回顾

绝热定理

定理（Born & Fock, 1928）：设 $H(s)$（$s = t/T \in [0, 1]$）是随时间缓慢变化的哈密顿量，$H(0)$ 的基态为 $|\psi_0(0)\rangle$。若 $|\psi_0(0)\rangle$ 与 $H(s)$ 的瞬时基态 $|\psi_0(s)\rangle$ 之间始终存在能隙 $\Delta(s) = E_1(s) - E_0(s) > 0$，则：

$$|\langle\psi_0(1)|\psi(T)\rangle|^2 \ge 1 - \varepsilon$$

只要总演化时间：

$$T = \Omega\left(\frac{\max_s \|H'(s)\|}{\min_s \Delta(s)^2} \cdot \log(1/\varepsilon)\right)$$

其中 $H'(s) = dH/ds$，$\Delta_{\min} = \min_s \Delta(s)$ 是最小能隙。

绝热量子计算的范式

目标：制备 $H_P$（问题哈密顿量）的基态（编码优化问题的解）。

方法：从容易制备基态的 $H_B$（初始哈密顿量）出发，缓慢插值到 $H_P$：

$$H(s) = (1 - s) H_B + s H_P, \quad s \in [0, 1]$$

初始态：$|\psi(0)\rangle = |+\rangle^{\otimes n}$（$H_B = -\sum_i X_i$ 的基态）

总时间：$T = O(1/\Delta_{\min}^2)$（最坏情况）

为什么需要离散化

连续绝热演化 $e^{-i\int_0^T H(t)dt}$ 不能直接在量子电路上执行——量子门是离散操作。需要将连续时间演化离散化为量子门序列。

离散绝热方法一：Trotter 化

基本思想

将 $[0, T]$ 切成 $r$ 个时间步，每步内哈密顿量近似为常数：

$$e^{-i\int_0^T H(t)dt} \approx \prod_{k=0}^{r-1} e^{-iH(s_k)\delta}, \quad s_k = k/r, \quad \delta = T/r$$

每个 $e^{-iH(s_k)\delta}$ 再用 Trotter 分解。

误差分析

定理：对线性插值 $H(s) = (1-s)H_B + sH_P$，$r$ 步 Trotter 化的误差为：

$$\varepsilon_{\text{total}} = O\left(\frac{\|H\|^2 T}{r}\right) + O\left(\frac{[H_B, H_P]}{\Delta_{\min}^2}\right)$$

第一项是 Trotter 离散化误差，第二项是绝热逼近误差。

取 $r = O(\|H\|^2 T / \varepsilon)$，总误差 $O(\varepsilon + \|H_B, H_P]\|/\Delta_{\min}^2)$。

门数

每步 $e^{-iH(s_k)\delta}$ 需要 $O(L)$ 个门（$L$ 为 $H_B + H_P$ 的项数）。总门数 $O(r \cdot L)$。

离散绝热方法二：量子信号处理化

核心思想

利用 QSP（量子信号处理），直接实现绝热路径的多项式逼近，无需 Trotter 分解。

方法

1. 将绝热演化 $U(T) = \mathcal{T} e^{-i\int_0^T H(t)dt}$ 展开为 $H(0)$ 和 $H(1)$ 的多项式
2. 用 QSP 实现该多项式（通过交替施加 $e^{-iH_B \delta}$ 和 $e^{-iH_P \delta}$）

深度：$O(T + \log(1/\varepsilon))$，优于 Trotter 的 $O(T^2/\varepsilon)$。

优势

• 无需 Trotter 分解
• 误差精确可控
• 深度达到理论下界

离散绝热方法三：分段恒定路径（分段绝热）

基本思想

将 $[0, 1]$ 切成 $p$ 段，每段内 $H$ 为常数：

$$H_k = (1 - s_k) H_B + s_k H_P, \quad s_k \in [0, 1], \quad k = 0, 1, \ldots, p$$

系统依次演化：$U_k = e^{-iH_k T/p}$。

与 QAOA 的关系

分段恒定绝热路径正是 $p$ 层 QAOA 的特例：

$$|\gamma, \beta\rangle = \prod_{l=1}^{p} \left[ e^{-i\gamma_l H_P} \cdot e^{-i\beta_l H_B} \right] |+\rangle^{\otimes n}$$

当 $\gamma_l = s_l T/p$，$\beta_l = (1-s_l) T/p$ 时，QAOA 退化为离散绝热演化。

QAOA 的额外自由度：QAOA 允许独立优化每个 $\gamma_l, \beta_l$，不受单调插值约束，表达能力严格强于离散绝热。

离散绝热方法四：变分绝热量子计算（VAQC）

核心思想

将绝热路径参数化 $H(s) = (1 - f(s; \vec{\theta})) H_B + f(s; \vec{\theta}) H_P$，其中 $f(s; \vec{\theta})$ 是参数化函数（如神经网络、样条）。

用变分方法优化 $\vec{\theta}$，使最终态与目标基态的重叠最大化。

优势

• 避免了精确绝热条件的约束
• 对小能隙问题可能优于标准绝热
• 与 NISQ 设备兼容

绝热条件与能隙

最小能隙的决定作用

总演化时间 $T = O(g^{-2})$（$g = \Delta_{\min}$）。能隙越小，所需时间越长。

典型能隙缩放：

关键问题：对许多 NP-Hard 问题，最小能隙是指数小的，绝热方法没有加速。

量子绝热定理的改进

定理（Jansen, Ruskai, Bhatt, 2007）：

$$T = \Omega\left(\frac{\|H'\|_{\text{rms}}^2}{\Delta_{\min}^3} \cdot \log(1/\varepsilon)\right)$$

其中 $\|H'\|_{\text{rms}} = \sqrt{\int_0^1 \|H'(s)\|^2 ds}$ 是均方根驱动强度。

这比朴素估计 $\|H'\|_{\max}/\Delta_{\min}^2$ 更紧。

具体例子

例子一：Max-Cut 的离散绝热

$H_B = -\sum_i X_i$，$H_P = \sum_{(i,j)} \frac{1}{2}(I - Z_i Z_j)$。

对三角形 $K_3$，$\Delta_{\min} \approx 0.5$，$T = O(4)$，$r = 10$ 步足够。

例子二：横向场 Ising 反铁磁体

$H(s) = (1-s)(-\sum_i X_i) + s(-\sum_{\langle i,j\rangle} Z_i Z_j)$

一维链的能隙 $\Delta_{\min} = O(1/n)$（Goldstone 模式），$T = O(n^2)$。

例子三：量子搜索的绝热实现

$H(s) = (1-s)(I - |s\rangle\langle s|) + s(I - |w\rangle\langle w|)$

最小能隙 $\Delta_{\min} = O(1/\sqrt{N})$，$T = O(\sqrt{N})$——复现 Grover 复杂度。

离散绝热 vs. 标准门模型

总结

离散绝热方法将绝热量子计算的物理直觉转化为可在门模型量子计算机上实现的算法。Trotter 化是最直接的方法，QSP 化提供了更优的深度，而 QAOA 通过引入可优化参数超越了固定绝热路径的限制。理解离散绝热方法是连接绝热量子计算与门模型量子计算的桥梁。

参考文献：

1. Born, M., & Fock, V. (1928). Beweis des Adiabatensatzes. Zeitschrift für Physik, 51(3-4), 165-180.
2. Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000). Quantum computation by adiabatic evolution. arXiv:quant-ph/0001106.
3. Jansen, S., Ruskai, M. B., & Bhatt, R. (2007). Bounds for the adiabatic approximation with applications to quantum computation. Journal of Mathematical Physics, 48(10), 212104.
4. Somma, R. D., & Boixo, S. (2013). Bloch-oscillation approach to the quantum adiabatic algorithm. Physical Review A, 88(4), 042321.