# 离散绝热方法详解：绝热量子计算的离散化实现

离散绝热方法（Discrete Adiabatic Method）是将连续绝热量子计算（Adiabatic Quantum Computing, AQC）转化为可在量子门电路上实现的离散算法的关键技术。它桥接了"绝热演化"这一物理概念与"量子电路"这一计算模型，使得绝热思想可以在通用量子计算机上实现。本文先精确陈述绝热定理并给出其 $1/\Delta_{\min}^2$ 条件的推导，再依次讨论四种离散化方案，其中 Trotter 化方案的误差界与步长选择将被逐步展开；最后我们对三个具体例子重新核对全部数值。

## 绝热量子计算回顾

### 绝热定理

定理（绝热定理，Born–Fock, 1928 [1]）：设 $H(s)$（$s = t/T \in [0,1]$）是光滑依赖参数的哈密顿量，基态非简并，且基态与其余谱之间始终存在能隙

$$\Delta(s) = E_1(s) - E_0(s) \ \ge\ \Delta_{\min} > 0 .$$

若总演化时间满足

$$T \ \ge\ \frac{1}{\varepsilon}\cdot\frac{\max_{s\in[0,1]}\|H'(s)\|}{\Delta_{\min}^2},$$

则从基态出发的终态与 $H(1)$ 基态的重叠满足

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

（严格陈述还需包含 $\|H''\|/\Delta_{\min}^3$ 等高阶修正，见下文与 [3]。）

我们给出 $1/\Delta_{\min}^2$ 的来源，这是一阶微扰论加分部积分的标准推导。把态展开到瞬时本征基 $H(s)|j(s)\rangle = E_j(s)|j(s)\rangle$ 上：

$$|\psi(t)\rangle = \sum_j b_j(t)\, e^{-i\int_0^t E_j(s(t'))\,dt'}\,|j(s(t))\rangle .$$

代入薛定谔方程 $i\frac{d}{dt}|\psi\rangle = H(t)|\psi\rangle$，对角项相消，两边左乘 $\langle m(s)|$ 得振幅方程

$$\dot b_m = -\frac{1}{T}\sum_j b_j\,\langle m|\partial_s j\rangle\, e^{\,i\int_0^t (E_m - E_j)\,dt'} .$$

对 $m \ne j$，我们对恒等式 $H|j\rangle = E_j|j\rangle$ 两边关于 $s$ 求导、再投影到 $\langle m|$，得

$$\langle m|H'|j\rangle + E_m\,\langle m|\partial_s j\rangle = E_j\,\langle m|\partial_s j\rangle \quad\Longrightarrow\quad \langle m|\partial_s j\rangle = \frac{\langle m|H'|j\rangle}{E_j - E_m}.$$

在一阶近似 $b_0 \approx 1$、$b_j \approx 0$（$j \ne 0$）下换元回 $s$，得到向第 $m$ 激发态的跃迁振幅

$$b_m(1) \approx \int_0^1 g(s)\, e^{-iT\Phi(s)}\, ds, \qquad g(s) = \frac{\langle m|H'|0\rangle}{E_0 - E_m}, \quad \Phi(s) = \int_0^s \Delta_{m0}(u)\,du .$$

对相位做分部积分（利用 $\frac{d}{ds}e^{-iT\Phi} = -iT\,\Phi' e^{-iT\Phi}$，且 $\Phi' = \Delta_{m0} \ge \Delta_{\min}$）：

$$\left|\int_0^1 g\, e^{-iT\Phi}\,ds\right| \ \le\ \frac{1}{T}\left[\frac{|g(0)| + |g(1)|}{\Delta_{\min}} + \int_0^1 \frac{|g'(s)|}{\Delta_{\min}}\,ds\right] \ \lesssim\ \frac{\max_s \|H'(s)\|}{T\,\Delta_{\min}^2},$$

其中最后一步用了 $|g| \le \|H'\| / \Delta_{\min}$；$g'$ 项给出形如 $\|H''\|/\Delta_{\min}^3$ 的高阶修正，可由更细致的分析控制 [3]。令右端不超过 $\varepsilon$，即得 $T = \Omega(\max_s \|H'\| / (\varepsilon \Delta_{\min}^2))$——能隙以 $-2$ 次幂进入绝热时间。

### 绝热量子计算的范式

绝热量子计算的目标是制备问题哈密顿量（problem Hamiltonian）$H_P$ 的基态，用其编码组合优化问题的解。方法是从容易制备基态的初始哈密顿量（initial Hamiltonian）$H_B$ 出发，缓慢插值到 $H_P$：

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

标准选择是横场初始哈密顿量 $H_B = -\sum_i X_i$，其基态为 $|\psi(0)\rangle = |+\rangle^{\otimes n}$。由绝热定理，在最坏情况下所需时间为

$$T = O\!\left(\frac{\|H'\|}{\varepsilon\,\Delta_{\min}^2}\right),$$

其中 $\|H'\| = \|H_P - H_B\|$；文献中常取按自旋数归一化的 $\|H'\| = O(1)$ 约定，此时简记 $T = O(1/\Delta_{\min}^2)$。

### 为什么需要离散化

连续绝热演化 $\mathcal T\, e^{-i\int_0^T H(t)\,dt}$（$\mathcal T$ 为时间编序算符）不能直接在量子电路上执行，因为量子门是离散的酉操作。我们需要把连续时间演化离散化为量子门序列，并保证离散化引入的误差与绝热近似误差一起可控。下面介绍四种离散化方案。

## 离散绝热方法一：Trotter 化

### 基本思想

我们把 $[0, T]$ 切成 $r$ 个长度为 $\delta = T/r$ 的时间片，在第 $k$ 片内把哈密顿量冻结为常数：

$$\widetilde H(t) = H(s_k), \quad t \in [t_k, t_{k+1}), \qquad s_k = \frac{k}{r}, \quad t_k = \frac{kT}{r}.$$

冻结后的演化严格等于一个门序列

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

每个 $e^{-iH(s_k)\delta} = e^{-i[(1-s_k)H_B + s_k H_P]\delta}$ 再用一阶 Trotter 分解为 $e^{-i(1-s_k)H_B\,\delta}\, e^{-is_k H_P\,\delta}$（若 $H_B$、$H_P$ 各为 $L$ 个局域项之和，则每个指数进一步拆为 $L$ 个单指数）。

### 误差分析

总误差有三个来源：绝热近似误差、片内冻结误差与片内 Trotter 分裂误差。我们逐项推导后两者。

引理一（冻结误差）：若 $\max_t \|\dot H(t)\| \le M$，则

$$\left\|\mathcal T\, e^{-i\int_{t_k}^{t_{k+1}} H\,dt} - e^{-iH(t_k)\delta}\right\| \le \frac{M\,\delta^2}{2}.$$

推导：由 Duhamel 恒等式（对两边积分 $U^\dagger(\cdot)u$ 型关系）

$$\mathcal T\, e^{-i\int_{t_k}^{t_k+\delta} H\,d\tau} - e^{-iH(t_k)\delta} = -i\int_0^\delta \left[\mathcal T\, e^{-i\int_{t_k+s}^{t_{k+1}} H\,d\tau}\right]\big(H(t_k+s) - H(t_k)\big)\, e^{-iH(t_k)\,s}\, ds,$$

对右边取范数，用酉性消去两个演化算符、再用 $\|H(t_k+s) - H(t_k)\| \le sM$，即得 $\int_0^\delta sM\,ds = \frac{M\delta^2}{2}$。对 $r$ 片求和，总冻结误差 $\le \frac{rM\delta^2}{2} = \frac{MT\delta}{2}$。代入 $M = \max\|\dot H\| = \frac{\|H'\|}{T}$，得到与 $T$ 无关的简洁形式

$$\varepsilon_{\text{冻结}} \le \frac{\|H'\|\,\delta}{2} = \frac{T\,\|H'\|}{2r}.$$

引理二（Trotter 分裂误差）：

$$\|e^{A}e^{B} - e^{A+B}\| \le \frac{1}{2}\|[A, B]\|\,e^{\|A\| + \|B\|}.$$

证明思路：由 Duhamel 公式 $e^{A}e^{B} - e^{A+B} = \int_0^1 e^{(1-\sigma)(A+B)}\,[A,B]\,e^{\sigma(A+B)}\cdot(\ldots)$ 型展开可得；下面只需应用。取 $A = -i(1-s_k)\delta H_B$、$B = -is_k\delta H_P$，则 $\|[A,B]\| = (1-s_k)s_k\,\delta^2\,\|[H_B, H_P]\| \le \frac{\delta^2}{4}\|[H_B,H_P]\|$。当 $\delta\max_s\|H(s)\| \le 1$ 时指数因子为 $O(1)$，单片分裂误差为 $O(\delta^2\|[H_B,H_P]\|)$，共 $r$ 片，利用 $r\delta^2 = T\delta = \frac{T^2}{r}$ 得

$$\varepsilon_{\text{Trotter}} = O\!\left(\frac{T^2\,\|[H_B, H_P]\|}{r}\right).$$

把三项相加，我们得到总的误差预算

$$\varepsilon_{\text{total}} \ \le\ \underbrace{\frac{\|H'\|}{T\,\Delta_{\min}^2}}_{\text{绝热误差}} \ +\ \underbrace{\frac{T\,\|H'\|}{2r}}_{\text{冻结误差}} \ +\ \underbrace{\frac{T^2\,\|[H_B, H_P]\|}{4r}}_{\text{Trotter 误差}} .$$

### 步长选择与门数

根据上式可以显式选出 $T$ 与 $r$。取

$$T = \frac{2\,\|H'\|}{\varepsilon\,\Delta_{\min}^2},$$

则绝热误差不超过 $\varepsilon/2$；再取

$$r = \left\lceil \max\left\{\ \frac{2\,\|H'\|^2}{\varepsilon^2\,\Delta_{\min}^2},\ \ \frac{2\,\|H'\|^2\,\|[H_B, H_P]\|}{\varepsilon^3\,\Delta_{\min}^4}\ \right\}\right\rceil,$$

则冻结项 $\frac{T\|H'\|}{2r} = \frac{\|H'\|^2}{r\,\varepsilon\,\Delta_{\min}^2} \le \frac\varepsilon2$、Trotter 项 $\frac{T^2\|[H_B,H_P]\|}{4r} = \frac{\|H'\|^2\|[H_B,H_P]\|}{r\,\varepsilon^2\Delta_{\min}^4} \le \frac\varepsilon2$，总误差不超过 $\varepsilon$。

每个 Trotter 步需要 $O(L)$ 个指数门（$L$ 为 $H_B + H_P$ 的局域项数），因此总门数为

$$O(r \cdot L) = O\!\left(\frac{L\,\|H'\|^2}{\varepsilon^2}\left(\frac{1}{\Delta_{\min}^2} + \frac{\|[H_B, H_P]\|}{\varepsilon\,\Delta_{\min}^4}\right)\right),$$

其中较重的一项（对 $1/\varepsilon$ 三次、对 $1/\Delta_{\min}$ 四次）来自一阶 Trotter 分裂。改用高阶 Trotter–Suzuki 公式可把 $\varepsilon$ 的次数降下来，代价是每步的电路更深。

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

### 核心思想

利用量子信号处理（Quantum Signal Processing, QSP），我们可以绕开 Trotter 分解，直接以最优精度实现指数演化。

### 方法

先把绝热路径做分段常数近似（同方法一），再对每一段使用 QSP：设我们持有 $H_k = H(s_k)$ 的块编码（block-encoding），则 QSP 把目标函数 $e^{-iH_k\delta}$ 的多项式逼近编译为一串交替的信号旋转与块编码调用，从而以受控精度实现 $e^{-iH_k\delta}$。整个过程不需要把 $e^{-iH_k\delta}$ 拆成不可交换项的乘积，因而不产生 Trotter 型误差。

### 优势

块编码模型下，模拟时间无关哈密顿量时间 $\tau$、精度 $\varepsilon$ 的最优调用次数为 $\widetilde O(\tau + \log(1/\varepsilon))$（最优实现带双对数修正因子 $\frac{\log(\tau/\varepsilon)}{\log\log(\tau/\varepsilon)}$，达到已知的查询复杂度下界）。对整条绝热路径逐段求和，总深度关于总演化时间线性、关于 $1/\varepsilon$ 对数，相比一阶 Trotter 的 $O(T^2/\varepsilon)$ 有本质改进。此外误差是精确可控的多项式逼近误差，无需通过缩小步长间接压低。

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

### 基本思想

我们将 $[0,1]$ 切成 $p$ 段，第 $k$ 段内哈密顿量取常数

$$H_k = (1 - s_k)\, H_B + s_k\, H_P, \qquad s_k \in [0, 1],$$

系统依次演化 $U = U_p \cdots U_1$，其中 $U_k = e^{-i H_k\, T/p}$。每个 $U_k$ 是有限个局域项指数的乘积，因此这是量子电路可直接执行的"离散绝热演化"。其误差分析与方法一完全相同（冻结误差 $\frac{\|H'\|}{2p}$、分裂误差 $\frac{T^2\|[H_B,H_P]\|}{4p}$、绝热误差 $\frac{\|H'\|}{T\Delta_{\min}^2}$）。

### 与 QAOA 的关系

分段恒定绝热路径正是 $p$ 层量子近似优化算法（QAOA）的特例。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$ 时，每一层（先作用 $e^{-i\beta_l H_B}$、再作用 $e^{-i\gamma_l H_P}$）恰好等于离散绝热段 $e^{-i H_l\,T/p}$ 的一阶 Trotter 分裂（分裂中两项的先后次序不同只影响 $O(\delta^2)$ 项），因此单调参数下的 QAOA 拟设完全覆盖离散绝热演化。

QAOA 的额外自由度在于：它允许独立优化每个 $\gamma_l, \beta_l$，不受"离散绝热中 $\beta_l = (1-s_l)T/p$ 与 $\gamma_l = s_lT/p$ 必须随 $s_l$ 单调变化"这一约束，表达能力严格强于离散绝热；代价是需要经典外环优化。

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

### 核心思想

我们把绝热路径本身参数化：$H(s) = (1 - f(s; \vec\theta)) H_B + f(s; \vec\theta)\, H_P$，其中 $f(s; \vec\theta)$ 是参数化的插值函数（例如样条或小型神经网络的输出），只要求 $f(0) = 0$、$f(1) = 1$。随后用变方法优化 $\vec\theta$，使终态与目标基态的重叠最大化。

### 优势

该方法避免了精确绝热条件对路径形状的限制，允许路径绕开能隙极小的区域，对小能隙问题可能优于标准绝热方案；同时每段演化深度浅，与 NISQ 设备兼容。其代价是把困难转移到经典优化，且没有全局最优性保证。

## 绝热条件与能隙

### 最小能隙的决定作用

绝热时间 $T = O(\|H'\| / (\varepsilon\, g^2))$（$g = \Delta_{\min}$，取 $\|H'\| = O(1)$ 归一化）表明：能隙越小，所需时间越长。典型问题的能隙标度如下：

| 问题类型 | 最小能隙 $g$ | 所需时间 |
|---------|-------------|-------------|
| 无结构搜索（线性调度） | $O(N^{-1/2})$ | $O(N)$ |
| 无结构搜索（局域绝热调度） | $O(N^{-1/2})$ | $O(\sqrt N)$（= Grover） |
| 一维横场 Ising 临界点 | $O(1/n)$ | $O(n^2)$（局域调度，见例子二） |
| 随机 SAT 相变点（一阶相变情形） | 可指数小 | 指数 |
| 一般局域哈密顿量基态（QMA 完全） | 可指数小 | 指数 |

关键结论是：对许多 NP-Hard 问题，最小能隙被认为是指数小的，此时绝热方法没有指数加速；量子加速只出现在能隙多项式小的场合。

### 局域绝热调度（Roland–Cerf）

线性调度的绝热条件用了 $\max_s\|H'\|$，即在整条路径上均匀放慢。Roland 与 Cerf（2002）指出可以只在能隙小处放慢：把绝热条件逐点化为

$$\frac{|\langle 1(s)|H'(s)|0(s)\rangle|}{\Delta(s)^2}\,\dot s \ \le\ \varepsilon \qquad (\forall s),$$

（这是由上文一阶跃迁振幅的被积函数逐点有界给出的充分条件。）对 $\dot s$ 解出并积分，得局域绝热时间

$$T \ =\ \int_0^1 \frac{ds}{\dot s} \ =\ \frac{1}{\varepsilon}\int_0^1 \frac{|\langle 1(s)|H'(s)|0(s)\rangle|}{\Delta(s)^2}\,ds \ \le\ \frac{1}{\varepsilon}\int_0^1 \frac{\|H'(s)\|}{\Delta(s)^2}\,ds.$$

当被积函数集中在 $\Delta_{\min}$ 附近时该式退回 $\|H'\|/(\varepsilon\Delta_{\min}^2)$；但当能隙只在窄区间变小（如无结构搜索）时，积分可以被 $\Delta_{\min}$ 的低次幂控制，从而显著节省时间——例子三将把搜索问题的 $O(N)$ 降到 $O(\sqrt N)$。

### 量子绝热定理的改进

朴素的 $\max\|H'\| / \Delta_{\min}^2$ 条件既非必要也非充分（Marzlin 与 Sanders 2004 给出了反例）。Jansen、Ruskai 与 Bhatt [3] 在光滑路径假设下证明了形如

$$1 - |\langle\psi_0(1)|\psi(T)\rangle|^2 \ \le\ \frac{1}{T}\left(\frac{\|H'\|_1}{\Delta_{\min}^2} + \frac{c\,\|H''\|_1}{\Delta_{\min}^3}\right), \qquad \|G\|_1 := \int_0^1 \|G(s)\|\,ds$$

的界（常数 $c$ 依赖于归一化约定）。相对朴素形式有两点改进：其一，用积分范数代替最大值，允许 $\|H'\|$ 在少数点很大；其二，显式给出 $\|H''\|/\Delta^3$ 修正项，明确了定理成立所需的光滑性。我们推导中的分部积分正是这两项的来源。

## 具体例子

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

对图 $G = (V,E)$ 与自旋组态 $z_i \in \{\pm 1\}$，断边指示符 $\frac{1 - z_i z_j}{2}$ 在 $z_i \ne z_j$ 时取 1，故割值 $C = \sum_{(i,j)}\frac{1 - z_iz_j}{2}$。最大化 $C$ 等价于最小化 $-C$，因此问题哈密顿量应取

$$H_P = \frac{1}{2}\sum_{(i,j) \in E} \left(Z_i Z_j - I\right),$$

其基态对应最大割。注意不能取 $+\frac{1}{2}\sum(I - Z_iZ_j)$：那是把割值本身当作能量去最小化，基态是全自旋相同、割值为 0 的平凡解，与 Max-Cut 南辕北辙。初始哈密顿量取横场 $H_B = -\sum_i X_i$，初态 $|+\rangle^{\otimes 3}$。

我们对三角形 $K_3$（3 个顶点、3 条边）完全对角化整条路径 $H(s) = (1-s)H_B + sH_P$。首先核对谱：$H_P$ 的本征值是 $\frac12\sum(z_iz_j - 1)$；全同组态（2 个）给出 $\frac12(3 - 3) = 0$，单翻转组态（6 个）给出 $\frac12(1 - 3) = -2$。故 $\|H_P\| = 2$，基态 6 重简并（正是 6 个最大割解，割值为 2）。又 $\|H_B\| = 3$，$\|H'\| = \|H_P - H_B\| \le 5$。

其次做对称约化。$H(s)$ 与全体置换及 $P = X_1 X_2 X_3$ 对易，因此 8 维空间分解为解耦的扇区；初态 $|+\rangle^{\otimes 3}$ 完全落在对称（自旋 3/2）扇区，演化永不离开。在对称扇区内 $-\sum_i X_i = -2S_x$，且由恒等式 $\sum_{i<j} Z_iZ_j = \frac{(\sum_i Z_i)^2 - 3}{2}$ 可得 $H_P = \frac{(\sum_iZ_i)^2 - 9}{4} = S_z^2 - \frac 94$。再按 $P$ 的宇称分为两个二维块。偶宇称块取基组 $|a\rangle = \frac{|m_z = 3/2\rangle + |m_z = -3/2\rangle}{\sqrt 2}$、$|b\rangle = \frac{|m_z = 1/2\rangle + |m_z = -1/2\rangle}{\sqrt 2}$。利用 $S_x$ 的矩阵元 $\langle b|2S_x|b\rangle = 2$、$\langle a|2S_x|b\rangle = \sqrt 3$（由 $J_{\mp}|3/2\rangle = \sqrt 3|1/2\rangle$、$J_\mp|1/2\rangle = 2|\mp 1/2\rangle$ 逐项算出）以及 $\langle a|H_P|a\rangle = 0$、$\langle b|H_P|b\rangle = -2$，我们得到

$$H_{\text{even}}(s) = \begin{pmatrix} 0 & -\sqrt 3\,(1-s) \\ -\sqrt 3\,(1-s) & -2 \end{pmatrix},$$

其迹为 $-2$、行列式为 $-3(1-s)^2$，两本征值之差为

$$\Delta_{\text{even}}(s) = 2\sqrt{1 + 3(1-s)^2} \ \in\ [2, 4].$$

端点核对：$s = 0$ 时本征值为 $-3, 1$，与 $-2S_x$ 在偶宇称块的谱一致；$s = 1$ 时为 $-2, 0$，与 $H_P$ 谱一致。奇宇称块 $\begin{pmatrix} 0 & -\sqrt3(1-s) \\ -\sqrt3(1-s) & 2-4s \end{pmatrix}$ 的最低能级在整个路径上不低于偶块最低能级、仅在 $s = 1$ 处与之简并（属于最大割解空间的简并），非对称扇区同样被对称性隔离。因此演化实际所处的解耦扇区内有效最小能隙为

$$\Delta_{\min} = 2 \qquad (\text{而非朴素估计的 } 0.5).$$

数值重算：取目标精度 $\varepsilon = 0.1$。

- 绝热时间：$T \ge \frac{\|H'\|}{\varepsilon\,\Delta_{\min}^2} = \frac{5}{0.1 \times 4} = 12.5$，我们取 $T = 15$；
- 步数：冻结条件 $\frac{T\|H'\|}{2r} \le \varepsilon$ 给 $r \ge 375$；Trotter 条件 $\frac{T^2\|[H_B, H_P]\|}{4r} \le \varepsilon$ 用 $\|[H_B,H_P]\| \le 2\|H_B\|\|H_P\| = 12$ 给 $r \ge 6750$。

因此严格界要求 $r$ 达到 $10^3$–$10^4$ 量级。必须强调：这些是最坏情形的充分条件，数值实验中 $r \sim 10$ 的离散绝热演化通常已能把成功概率（终态落在 6 个最大割基态上的概率）做到接近 1；可证明的界远松于实际所需。

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

取

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

其中 $\langle i, j\rangle$ 遍历一维链的最近邻。一维链是二部图，把其中一个子格上的 $Z$ 反号（幺正变换）即可把反铁磁耦合映为铁磁耦合而谱不变，因此我们分析标准的横场 Ising 模型（transverse-field Ising model, TFIM）$H = -J\sum_i Z_iZ_{i+1} - h\sum_i X_i$，对应 $J = s$、$h = 1-s$、周期边界。Jordan–Wigner 变换把它映射为自由费米子，单粒子激发能为（证明思路：JW 变换把自旋链映为无自旋费米子，再做 Bogoliubov 对角化，这是 Onsager–Lieb 的标准结果）

$$\epsilon_k = 2\sqrt{J^2 + h^2 - 2Jh\cos k}, \qquad k \in \left\{\frac{2\pi m}{n}\right\}.$$

能隙 $\Delta = \min_k \epsilon_k = 2|J - h| = 2|2s-1|$（$J \ne h$ 时）。在临界点 $s = \frac 12$（$J = h$）处，$\epsilon_k = 4h\,|\sin\frac k2| = 2|\sin\frac k2|$，最小非零动量 $k_{\min} = \frac{2\pi}{n}$ 给出

$$\Delta_{\min} = 2\sin\frac{\pi}{n} \approx \frac{2\pi}{n} = O(1/n).$$

需要更正一个常见的说法：这并不是 Goldstone 模式——Ising 自发破缺的是离散对称性，不存在 Goldstone 无能隙激发；$1/n$ 关闭是临界点处的有限尺寸标度（临界慢化）。绝热时间上，$\|H'\| = \|H_P - H_B\| = O(n)$，故线性调度给 $T = O(n \cdot n^2) = O(n^3)$。改用局域绝热调度可积出 $T = O(n^2)$：把 $\Delta^2(s)$ 用光滑化的 $4(2s-1)^2 + 4\pi^2/n^2$ 代替，代入 $T = \frac{\|H'\|}{\varepsilon}\int_0^1\frac{ds}{\Delta(s)^2}$，令 $u = 2s - 1$ 并用 $\int\frac{du}{u^2 + a^2} = \frac1a\arctan\frac ua$：

$$T \approx \frac{2n}{\varepsilon}\int_0^1 \frac{ds}{4(2s-1)^2 + 4\pi^2/n^2} = \frac{n}{4\varepsilon}\int_{-1}^{1}\frac{du}{u^2 + \pi^2/n^2} = \frac{n}{4\varepsilon}\cdot\frac{n}{\pi}\,2\arctan\frac{n}{\pi} = O\!\left(\frac{n^2}{\varepsilon}\right).$$

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

取归一化的搜索哈密顿量

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

其中 $|s\rangle$ 是均匀叠加、$|w\rangle$ 是标记态。我们在 $\{|w\rangle, |r\rangle\}$ 基（$|r\rangle = \frac{1}{\sqrt{N-1}}\sum_{x \neq w}|x\rangle$）中计算 $G(s) = (1-s)|s\rangle\langle s| + s|w\rangle\langle w|$（$H = I - G$，二者能隙相同）。由 $|s\rangle$ 在该基下的坐标为 $\frac{1}{\sqrt N}(1, \sqrt{N-1})$，

$$G(s) = \begin{pmatrix} \frac{1-s}{N} + s & \frac{(1-s)\sqrt{N-1}}{N} \\[4pt] \frac{(1-s)\sqrt{N-1}}{N} & \frac{(1-s)(N-1)}{N} \end{pmatrix}.$$

能隙等于 $\sqrt{(\text{对角差})^2 + 4(\text{非对角})^2}$。对角差为 $\frac{1-s}{N} + s - \frac{(1-s)(N-1)}{N} = 2s - 1 + \frac{2(1-s)}{N}$，于是（交叉项展开后 $\frac{4(1-s)^2}{N^2}[1 + (N-1)]$ 与中间项合并为 $\frac{4s(1-s)}{N}$）

$$\Delta(s) = \sqrt{\left(2s - 1 + \frac{2(1-s)}{N}\right)^{\!2} + \frac{4(1-s)^2 (N-1)}{N^2}} = \sqrt{(2s-1)^2 + \frac{4s(1-s)}{N}}.$$

两个平方项都非负，且分别只在 $s = \frac 12$ 和端点为零，故最小能隙在 $s^* = \frac 12$ 处：

$$\Delta_{\min} = \sqrt{\frac{4 \cdot \frac14}{N}} = \frac{1}{\sqrt N}.$$

驱动强度 $\|H'\| = \||s\rangle\langle s| - |w\rangle\langle w|\|$：两个秩 1 投影之差在 $\mathrm{span}\{|w\rangle, |s\rangle\}$ 内的矩阵迹为 0、行列式为 $-(1 - |\langle s|w\rangle|^2) = -(1 - \frac 1N)$，故本征值为 $\pm\sqrt{1 - \frac 1N}$，即 $\|H'\| = \sqrt{1 - \frac 1N}$。

线性调度的绝热时间为 $T = O(\|H'\|/(\varepsilon\Delta_{\min}^2)) = O(N/\varepsilon)$。改用 Roland–Cerf 局域调度，则

$$T = \frac{\|H'\|}{\varepsilon}\int_0^1 \frac{ds}{\Delta(s)^2}.$$

令 $u = 2s - 1$，则 $4s(1-s) = 1 - u^2$、$\Delta^2 = \frac{1 + (N-1)u^2}{N}$、$ds = \frac{du}{2}$：

$$T = \frac{\sqrt{1 - 1/N}}{\varepsilon}\cdot\frac{N}{2}\int_{-1}^{1}\frac{du}{1 + (N-1)u^2} = \frac{\sqrt{1-1/N}}{\varepsilon}\cdot\frac{N}{\sqrt{N-1}}\,\arctan\sqrt{N-1} = \frac{\sqrt N}{\varepsilon}\arctan\sqrt{N-1}.$$

（最后一步用 $\sqrt{1 - 1/N} = \frac{\sqrt{N-1}}{\sqrt N}$。）由 $\arctan\sqrt{N-1} \to \frac \pi 2$ 得

$$T = \frac{\pi}{2\varepsilon}\sqrt N\,\big(1 + O(N^{-1/2})\big) = O(\sqrt N),$$

精确复现 Grover 复杂度。这也印证了"能隙表"中的对比：线性调度 $O(N)$、局域调度 $O(\sqrt N)$，后者对能隙只在窄区间变小的路径有整整一个多项式因子的节省。

## 离散绝热 vs. 标准门模型

| 特性 | 连续绝热 | 离散绝热（Trotter） | QAOA |
|------|---------|------------------|------|
| 演化方式 | 连续时间 | 离散步 | 离散步 |
| 参数数量 | 0（路径固定） | 0（等间隔） | $2p$（可优化） |
| 误差来源 | 绝热逼近 | 绝热 + 冻结 + Trotter | 变分优化 |
| 能隙依赖 | $O(g^{-2})$ | $O(g^{-2})$ | 可绕过小能隙 |
| 适用平台 | 专用 AQC 设备 | 通用量子计算机 | NISQ 设备 |

## 总结

离散绝热方法把绝热量子计算的物理直觉转化为门模型量子计算机上的算法。其核心是一套可显式控制的误差预算：绝热误差 $\frac{\|H'\|}{T\Delta_{\min}^2}$、片内冻结误差 $\frac{T\|H'\|}{2r}$ 与 Trotter 分裂误差 $\frac{T^2\|[H_B,H_P]\|}{4r}$，由它们可逐步选出总时间与步长。Trotter 化最直接；QSP 化把复杂度降到对时间线性、对精度对数；分段常数路径与 QAOA 相通，并通过变分参数超越了固定绝热路径的限制。三个算例（三角形的 Max-Cut、临界横场 Ising 链、绝热搜索）的能隙与时间均已逐项重算。理解离散绝热方法是连接绝热量子计算与门模型量子计算的桥梁。

---

**参考文献：**

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

> 返回目录：[量子计算算法教程系列](https://chenzhaoyun.com/index.php/archives/54/)