# 量子模拟退火：Szegedy Walk、Phase Gap 与 Quantum Zeno

经典模拟退火（simulated annealing）的做法是缓慢提高逆温度，让 Markov chain 的稳态从一个容易制备的高温分布，逐步移动到一个集中在低能量构型上的低温分布。量子模拟退火（quantum simulated annealing, QSA）**不是**把目标函数直接写成一个绝热 Hamiltonian 再做绝热演化，而是把退火过程中使用的**同一组经典转移矩阵**相干地量子化：Szegedy walk 把 Markov chain 的谱隙（spectral gap）$\delta$ 变成量子 walk 的相位隙（phase gap）$\Theta(\sqrt\delta)$，于是"投影到稳态"这一步的成本从经典的 $\widetilde O(1/\delta)$ 降到量子的 $\widetilde O(1/\sqrt\delta)$，获得平方改进。本教程的目标是把这条链路上的每一步都讲清楚：经典退火的瓶颈在哪里、Szegedy 量子化为什么把 $\delta$ 开方、冷却 schedule 上如何靠 quantum Zeno 效应逐级转移量子态，以及最终复杂度表达式里每个因子从哪里来。

读者应具备本站前几章的基础：量子力学与量子线路记号（第 1 章）、相位估计与振幅放大（第 3 章）。本文用到的相位估计只当作黑箱：给定酉算子 $W$ 与其某个本征态，可以用 $O(1/\varepsilon)$ 次受控 $W$ 把本征相位估计到精度 $\varepsilon$。

:::{admonition} 本课知识点
:class: tip

1. **[经典退火的瓶颈：mixing 与谱隙](#mixing-spectral-gap)**——能写出 Gibbs 分布与冷却 schedule，由第二大本征值 $1-\delta$ 解释 mixing time 为 $\widetilde O(1/\delta)$，并说明整个退火为何被 $\delta=\min_i\delta_i$ 卡住。
2. **[detailed balance 与 discriminant 对称化](#detailed-balance-discriminant)**——能写出 detailed balance 条件，验证 discriminant $D=\Pi^{1/2}P\Pi^{-1/2}$ 是与 $P$ 同谱的对称矩阵，并说明它是连接经典谱与量子相位的桥梁。
3. **[Szegedy 量子化：isometry 与两次反射](#szegedy-walk-construction)**——能写出 isometry $V$ 与子空间 $\mathcal A$、$\mathcal B$ 的定义，说明 walk 算子 $W=R_BR_A$ 的构造及其与 Grover 型反射的几何联系。
4. **[相干稳态的零相位](#coherent-stationary-state)**——能用 detailed balance 证明 $\mathrm{SWAP}|\pi\rangle=|\pi\rangle$，从而推出 $W|\pi\rangle=|\pi\rangle$、稳态对应零相位。
5. **[谱隙到相位隙的平方根放大](#phase-gap-square-root)**——能由 $\lambda_j=\cos\theta_j$ 推导非零本征相位 $\pm2\theta_j$ 与相位隙 $\Delta=\Theta(\sqrt\delta)$，并计算稳态投影成本 $\widetilde O(1/\sqrt\delta)$。
6. **[相邻 Gibbs 态 overlap 与 quantum Zeno](#overlap-quantum-zeno)**——能推导 $\langle\Pi_i|\Pi_{i+1}\rangle=Z\big(\tfrac{\beta_i+\beta_{i+1}}{2}\big)/\sqrt{Z(\beta_i)Z(\beta_{i+1})}$，并用逐级投影的成功率估计解释 quantum Zeno 效应对 schedule 粗细的要求。
7. **[Evolution randomization 替代相位估计](#evolution-randomization)**——能计算随机时长演化对相位 $\varphi$ 分量的退相干因子，并说明取 $T=\Theta(1/\sqrt\delta)$ 时它与相位估计版本同样完成向稳态的投影。
8. **[读出与适用边界](#readout-and-limitations)**——能比较 QSA 与绝热优化的输入与 gap，计算振幅放大读出的 $O(1/\sqrt{p_*})$ 成本，并解释指数小的谱隙开方后为何仍然指数。

:::

## 1. 问题背景：采样、优化与经典瓶颈

### 1.1 问题从哪里来

组合优化问题中，我们有一个巨大但有限的构型空间 $\Omega$（例如所有可能的布尔赋值、所有可能的晶格自旋排布）和一个能量函数 $E:\Omega\to\mathbb R$，目标是找到使 $E$ 最小的构型。统计物理中，我们关心的是给定逆温度 $\beta=1/(k_B T)$ 下的 Gibbs 分布

$$
\pi_\beta(x)=\frac{e^{-\beta E(x)}}{Z(\beta)},\qquad
Z(\beta)=\sum_{x\in\Omega}e^{-\beta E(x)},
$$

其中 $Z(\beta)$ 是配分函数。这两个问题通过"降温"联系起来：当 $\beta\to\infty$ 时，$\pi_\beta$ 的质量全部集中到能量最低的构型集合上（见 1.4 节的定量估计）。所以一个能按任意 $\beta$ 从 $\pi_\beta$ 采样的机器，同时就是一个优化器：把温度慢慢调低，采样结果就是越来越好的解。这就是 1980 年代 Kirkpatrick、Gelatt 与 Vecchi 提出的经典模拟退火的思想，它是当今应用最广的通用优化启发式之一。

### 1.2 经典算法能做到什么程度

实现退火的标准工具是 Markov chain Monte Carlo（MCMC）：构造一个以 $\pi_\beta$ 为稳态分布的 Markov chain（最常用的是 Metropolis–Hastings 或 Glauber 动力学），从任意初态出发运行足够多步，分布就会收敛到 $\pi_\beta$。冷却过程用一串中间温度

$$
0=\beta_0<\beta_1<\cdots<\beta_L=\beta_f
$$

来完成：$\beta_0=0$ 时 $\pi_0$ 是均匀分布，可以直接采样；在每个 $\beta_i$ 处运行对应的 chain 使分布"跟上"当前的 Gibbs 分布，再把样本作为下一个温度的初态（warm start），最终得到 $\pi_{\beta_f}$ 的样本。

(mixing-spectral-gap)=
### 1.3 瓶颈：mixing time 与谱隙

"运行足够多步"到底要多少步？这由 chain 的 **mixing time** 决定，而 mixing time 又由转移矩阵的谱控制。设可逆（reversible，即满足 detailed balance，见 2.2 节）Markov chain 的转移矩阵 $P$ 的第二大本征值绝对值为 $1-\delta$，其中 $\delta\in(0,1)$ 称为**谱隙（spectral gap）**。那么混合到距离稳态 $\varepsilon$ 以内大约需要

$$
t_{\mathrm{mix}}=O\!\left(\frac{1}{\delta}\log\frac{1}{\varepsilon\,\pi_{\min}}\right)
$$

步，即 mixing 成本正比于 $1/\delta$，再乘以对数因子与 warm-start 相关的因子。整个退火过程要在每个温度都混合一次，整体瓶颈由最差的那个温度决定：

$$
\delta=\min_i\delta_i.
$$

困难在于：对许多有实际意义的能量景观（例如有高耸势垒的自旋玻璃型景观），局部更新 chain 的谱隙随问题规模指数缩小，$\delta=e^{-\Theta(n)}$，经典退火因此需要指数时间。谱隙是经典退火的命门。

### 1.4 量子加速的历史线索

Szegedy 在 2004 年前后给出了任意经典 Markov chain 的相干量子化（Zoo 编号 85、135），其 walk 算子的相位隙是经典谱隙的平方根量级，并由此得到"$\sqrt{\delta\epsilon}$ rule"一类的通用平方加速。Somma、Boixo 与 Barnum（Zoo 编号 84）随后指出：把退火 schedule 上每个温度的 chain 都做 Szegedy 量子化，再用相位估计把量子态逐级投影到下一个温度的相干 Gibbs 态，就得到一个通用地把经典退火平方加速的量子算法——量子模拟退火。Somma、Boixo、Barnum 与 Knill（Zoo 编号 177）随后给出了更贴近物理实现的版本：不用完整相位估计，而是用随机时长演化的去相干效应实现同样的投影。Montanaro（Zoo 编号 265）把相关思想发展为量子 Monte Carlo 的通用平方加速框架。本教程沿这条脉络展开，但所有推导自足。

需要提前说清楚的保留条款：QSA 加速的是**给定的那组经典 chain**。如果经典 chain 本身的谱隙指数小，平方根之后仍然指数小（见第 9 节）。QSA 是一个"通用二次加速定理"，不是 NP-hard 优化的多项式时间算法。

## 2. 经典退火框架

本节把经典侧的对象逐一固定下来，并推导两个后面要反复用的定量事实。

### 2.1 Gibbs 分布与冷却 schedule

状态空间 $\Omega$ 有限，能量函数 $E(x)$ 给定。逆温度 $\beta$ 下的 Gibbs 分布为

$$
\pi_\beta(x)=\frac{e^{-\beta E(x)}}{Z(\beta)},\qquad
Z(\beta)=\sum_{x\in\Omega}e^{-\beta E(x)}.
$$

选定一个冷却 schedule

$$
0=\beta_0<\beta_1<\cdots<\beta_L=\beta_f,
$$

其中 $\beta_0=0$ 对应均匀分布（无需任何结构即可制备），$\beta_f$ 是终端逆温度，要大到让非最优构型的总质量足够小（定量条件在 2.4 节推导）。

(detailed-balance-discriminant)=
### 2.2 转移矩阵与 detailed balance

对每个温度 $\beta_i$，选一个转移矩阵 $P_i$，满足两条性质：

- **稳态正确**：$\pi_i P_i=\pi_i$，即 $\sum_x\pi_i(x)P_i(x,y)=\pi_i(y)$，其中 $\pi_i:=\pi_{\beta_i}$；
- **可逆性（detailed balance）**：

$$
\pi_i(x)P_i(x,y)
=\pi_i(y)P_i(y,x).
$$

detailed balance 的物理含义是：稳态下从 $x$ 流向 $y$ 的概率流等于从 $y$ 流回 $x$ 的概率流，系统处于"细致"平衡而非环流状态。Metropolis–Hastings 构造天然满足它。它的一个直接的数学推论是 $P_i$ 可以对称化：定义对角矩阵 $\Pi_i=\operatorname{diag}(\pi_i(x))$，则 **discriminant 矩阵**

$$
D_i=\Pi_i^{1/2}P_i\Pi_i^{-1/2}
$$

是对称矩阵。验证其 $(x,y)$ 元：

$$
D_i(x,y)=\sqrt{\frac{\pi_i(x)}{\pi_i(y)}}\,P_i(x,y)
=\frac{\pi_i(x)P_i(x,y)}{\sqrt{\pi_i(x)\pi_i(y)}},
$$

由 detailed balance，分子关于 $x,y$ 对称，故 $D_i(x,y)=D_i(y,x)$。对称矩阵有实本征值和正交本征向量——这就是 3.4 节把 $P_i$ 的谱与 walk 算子的相位联系起来的桥梁。另外 $D_i$ 与 $P_i$ 相似（差一个对角相似变换），所以二者本征值完全相同。

### 2.3 谱隙与 mixing

把 $P_i$ 的本征值写成 $1=\lambda_0>|\lambda_1|\ge\cdots$（Perron–Frobenius 定理保证最大本征值为 $1$，对应稳态；对可逆 chain 本征值都是实数）。谱隙定义为

$$
\delta_i=1-\max_{j\ge1}|\lambda_j|.
$$

每乘一次 $P_i$，分布与稳态的偏差在第二大本征值方向上只衰减 $|\lambda_1|=1-\delta_i$ 倍，所以要让偏差缩小到 $\varepsilon$ 需要约 $\frac{1}{\delta_i}\log\frac1\varepsilon$ 步（乘上 warm-start 与 $\pi_{\min}$ 带来的对数因子）。这就是 1.3 节 mixing time 估计的来源：经典退火每个温度的成本 $\propto 1/\delta_i$，全过程由 $\delta=\min_i\delta_i$ 卡住。

### 2.4 终端温度：需要多冷才够

记能量最低的构型集合为 $S_*$，最低能量为 $E_*$，并把能隙记作

$$
\Delta E=\min_{x\notin S_*}E(x)-E_*
$$

（假设 $S_*\neq\Omega$，否则无事可做）。能量整体平移不改变 Gibbs 分布（分子分母同乘一个因子），故不妨设 $E_*=0$。此时 $Z(\beta)\ge\sum_{x\in S_*}e^{0}=|S_*|\ge1$，于是非最优构型的总质量满足

$$
\sum_{x\notin S_*}\pi_\beta(x)
=\frac{\sum_{x\notin S_*}e^{-\beta E(x)}}{Z(\beta)}
\le\sum_{x\notin S_*}e^{-\beta E(x)}
\le|\Omega|\,e^{-\beta\Delta E},
$$

第一步是把定义展开，第二步用了 $Z(\beta)\ge1$（放缩分母只会把分数放大），第三步用了 $E(x)\ge\Delta E$（对所有非最优 $x$）以及 $|\Omega\setminus S_*|\le|\Omega|$。要让这个总质量不超过 $\eta$，只需

$$
|\Omega|\,e^{-\beta_f\Delta E}\le\eta
\quad\Longleftrightarrow\quad
\beta_f\Delta E\ \gtrsim\ \log\frac{|\Omega|}{\eta}.
$$

这就是终端温度的粗略要求：**$\beta_f$ 只需对数级地大**（$\log|\Omega|$ 对 $n$ 比特问题只是 $O(n)$）。所以冷却的"深度"不是瓶颈，瓶颈在 2.3 节的 mixing。这个对比值得记住：QSA 加速的正是 mixing，而不是降温本身。

## 3. Szegedy 量子化

本节回答核心问题：给定一个经典转移矩阵 $P_i$，怎样造出一个酉算子 $W_i$，使得 (a) Gibbs 稳态对应它的零相位本征态，(b) 经典谱隙 $\delta_i$ 变成相位隙 $\Theta(\sqrt{\delta_i})$。下文固定一个温度，省略下标 $i$。

(szegedy-walk-construction)=
### 3.1 从转移矩阵到 isometry

对每个构型 $x$，经典 chain 给出一步转移的条件分布 $P(x,\cdot)$。量子化的第一步是把这个分布做成振幅（概率的平方根）叠加：

$$
V|x\rangle|0\rangle
=|x\rangle\sum_y\sqrt{P(x,y)}\,|y\rangle
=: |x\rangle|\phi_x\rangle.
$$

$V$ 把第一个寄存器（保存当前构型）附上第二个寄存器（保存"下一步候选"）。因为 $\sum_y P(x,y)=1$，每个 $|\phi_x\rangle$ 都是归一化的，所以 $V$ 保持内积，是一个 **isometry**（等距嵌入）。记它的像为子空间

$$
\mathcal A=\operatorname{im}V
=\operatorname{span}\big\{\,|x\rangle|\phi_x\rangle : x\in\Omega\,\big\}.
$$

再定义交换两寄存器的算子 $\mathrm{SWAP}$，并令

$$
\mathcal B=\mathrm{SWAP}\,\mathcal A
=\operatorname{span}\big\{\,|\phi_x\rangle|x\rangle : x\in\Omega\,\big\}.
$$

直觉是：$\mathcal A$ 编码"从 $x$ 出发往哪走"，$\mathcal B$ 编码"从哪走来能到 $x$"。一个状态若同时属于两者，意味着"来路"与"去路"的分布一致——这正是稳态的相干版本，下一小节会验证。

### 3.2 两次反射合成的 walk

对两个子空间分别做反射：

$$
R_{A}=2\Pi_{A}-I,\qquad
R_{B}=2\Pi_{B}-I,
$$

其中 $\Pi_A,\Pi_B$ 是向 $\mathcal A,\mathcal B$ 的正交投影。这两个反射都可以在假定"能以 $\sqrt{P(x,y)}$ 为振幅相干地制备 $|\phi_x\rangle$"的前提下高效实现：例如 $\Pi_A=V\Pi_{\mathrm{first}}V^\dagger$ 形状的操作可由 $V$、$V^\dagger$ 与对 $|0\rangle$ 辅助寄存器的反射合成。Szegedy walk 算子定义为两次反射的复合

$$
W=R_{B}R_{A}.
$$

回忆一个几何事实（Grover 算法一章已用过）：两个反射的复合是一个旋转，旋转角等于两反射轴夹角的两倍。$\mathcal A$ 与 $\mathcal B$ 的"夹角"由 $P$ 的谱决定，这就是 3.4 节的主题。

(coherent-stationary-state)=
### 3.3 稳态是零相位本征态

定义**相干稳态（coherent stationary state）**

$$
|\pi\rangle
=\sum_x\sqrt{\pi(x)}\,|x\rangle\sum_y\sqrt{P(x,y)}\,|y\rangle
=\sum_x\sqrt{\pi(x)}\,|x\rangle|\phi_x\rangle.
$$

它显然属于 $\mathcal A$（就是 $V\big(\sum_x\sqrt{\pi(x)}|x\rangle\big)|0\rangle$ 的形状）。关键计算是它同时属于 $\mathcal B$，即交换两个寄存器之后它不变。交换后 $x$ 处的振幅是

$$
\sum_y\sqrt{\pi(y)}\sqrt{P(y,x)}
=\sum_y\sqrt{\pi(y)P(y,x)}
=\sum_y\sqrt{\pi(x)P(x,y)}
=\sqrt{\pi(x)}\sum_y\sqrt{P(x,y)}\cdot\frac{\sqrt{P(x,y)}}{\sqrt{P(x,y)}},
$$

这一步写得太绕，重新算一遍干净的：由 detailed balance（2.2 节），$\pi(y)P(y,x)=\pi(x)P(x,y)$，两边开平方得

$$
\sqrt{\pi(y)}\sqrt{P(y,x)}=\sqrt{\pi(x)}\sqrt{P(x,y)}.
$$

因此交换寄存器后的态

$$
\sum_{x,y}\sqrt{\pi(y)}\sqrt{P(y,x)}\,|x\rangle|y\rangle
=\sum_{x,y}\sqrt{\pi(x)}\sqrt{P(x,y)}\,|x\rangle|y\rangle
=|\pi\rangle,
$$

即 $|\pi\rangle$ 在 $\mathrm{SWAP}$ 下不变，所以 $|\pi\rangle\in\mathcal B$。于是 $|\pi\rangle\in\mathcal A\cap\mathcal B$，两次反射都保持它：

$$
W|\pi\rangle=R_BR_A|\pi\rangle=|\pi\rangle,
$$

本征相位为 $0$。物理图像：经典稳态"分布不再变化"的量子对应物，是 walk 算子下相位不转动的态。

(phase-gap-square-root)=
### 3.4 从谱隙到相位隙

现在处理非稳态方向的相位。结论是：

**Lemma（Szegedy 谱对应）.** 设可逆 chain 的 discriminant $D=\Pi^{1/2}P\Pi^{-1/2}$ 的本征值为 $\lambda_j=\cos\theta_j$（$\theta_j\in[0,\pi]$；$D$ 对称故本征值为实数，随机矩阵故 $|\lambda_j|\le1$，可以写成余弦）。则 $W$ 限制在 $\mathcal A+\mathcal B$ 上的非零本征相位为 $\pm2\theta_j$，每个 $j$ 给出一对共轭相位。

**证明概要.** 取 $D$ 的第 $j$ 个归一化本征向量 $v_j$，$Dv_j=\lambda_jv_j$。可以构造一对态

$$
|a_j\rangle=\sum_x v_j(x)\,|x\rangle|\phi_x\rangle\in\mathcal A,
\qquad
|b_j\rangle=\mathrm{SWAP}\sum_x v_j(x)\,\Pi^{1/2}\cdots
$$

更直接的说法是：$\mathcal A$ 的生成元 $|x\rangle|\phi_x\rangle$ 与 $\mathcal B$ 的生成元 $|\phi_{x'}\rangle|x'\rangle$ 的内积为

$$
\langle\phi_{x'}|\langle x'|x\rangle|\phi_x\rangle
=\delta_{x,x'}\sum_y\sqrt{P(x,y)P(y,x)}
=\delta_{x,x'}\,D\text{ 结构中的对称量},
$$

整理后两族生成元之间的 Gram 结构恰好由 $D$ 控制：对每个本征向量 $v_j$ 存在 $|a_j\rangle\in\mathcal A$ 与 $|b_j\rangle\in\mathcal B$ 满足

$$
\Pi_A|b_j\rangle=\lambda_j|a_j\rangle,\qquad
\Pi_B|a_j\rangle=\lambda_j|b_j\rangle,
$$

即 $\langle a_j|b_j\rangle=\lambda_j=\cos\theta_j$：两子空间沿第 $j$ 个方向的"夹角"是 $\theta_j$。于是二维平面 $\operatorname{span}\{|a_j\rangle,|b_j\rangle\}$ 在 $W=R_BR_A$ 下不变（两次反射各自把平面映回自身，与 Grover 一章的子空间论证相同），而平面内两次反射的复合是角度 $2\theta_j$ 的旋转，对应本征相位 $\pm2\theta_j$。$j=0$ 时 $\lambda_0=1$、$\theta_0=0$，退化为交 $\mathcal A\cap\mathcal B$ 中的零相位稳态。Q.E.D.（概要）

完整的严格证明需要处理 $\mathcal A+\mathcal B$ 的直和分解与 $\lambda_j=\pm1$ 的边界情形，这里略去；本教程只需要结论本身。

**Theorem（相位隙的平方根放大）.** 设 $P$ 的谱隙为 $\delta$（即第二大本征值绝对值 $1-\delta$），则 $W$ 的相位隙（零相位与最近非零相位的距离）满足

$$
\Delta=\Theta(\sqrt{\delta}\,).
$$

**证明.** 最接近 $1$ 的非平凡本征值是 $\lambda_1=1-\delta$（负本征值 $-(1-\delta)$ 对应 $\theta$ 接近 $\pi$，相位 $2\theta$ 接近 $2\pi$，离 $0$ 同样远，论证相同）。写 $\lambda_1=\cos\theta_1$，用半角恒等式 $1-\cos\theta=2\sin^2(\theta/2)$：

$$
\delta=1-\cos\theta_1=2\sin^2\frac{\theta_1}{2}
\quad\Longrightarrow\quad
\sin\frac{\theta_1}{2}=\sqrt{\frac{\delta}{2}}
\quad\Longrightarrow\quad
\theta_1=2\arcsin\sqrt{\frac{\delta}{2}}.
$$

由 Lemma，$W$ 最近的非零相位是 $\pm2\theta_1$，即

$$
\Delta=2\theta_1=4\arcsin\sqrt{\frac{\delta}{2}}.
$$

当 $\delta\ll1$ 时用 $\arcsin x=x+O(x^3)$：

$$
\Delta=4\sqrt{\frac{\delta}{2}}\,\big(1+O(\delta)\big)
=2\sqrt{2\delta}\,\big(1+O(\delta)\big)
=\Theta(\sqrt{\delta}\,).
$$

Q.E.D.

这个定理是整个 QSA 的引擎。值得停下来看清它"为什么是对的"：经典 chain 每步把偏差衰减 $1-\delta$，$\delta$ 小意味着衰减极慢；量子 walk 不直接跟踪"分布的衰减"，而是把同样的谱信息编码成**相位**，而相位 $2\theta_1\approx2\sqrt{2\delta}$ 比 $\delta$ 本身**大得多**（小数开方变大）。相位估计区分相位 $\varphi$ 与 $0$ 的成本是 $O(1/|\varphi|)$，所以：

### 3.5 相位检测的成本

**Corollary（稳态投影成本）.** 用相位估计把"处于 $|\pi\rangle$"与"处于任何非稳态本征方向"区分开，精度只需 $\Theta(\Delta)$，成本为

$$
\widetilde O\!\left(\frac{1}{\Delta}\right)
=\widetilde O\!\left(\frac{1}{\sqrt\delta}\right)
$$

次 $W$ 调用（$\widetilde O$ 隐藏估计置信度等带来的对数因子）。对比经典 mixing 的 $\widetilde O(1/\delta)$，这是平方改进。

具体地说，相位估计输出接近 $0$ 就接受（态塌缩/保留在 $|\pi\rangle$ 方向），输出明显非零就拒绝；把这个判决做成受控操作，就得到关于 $|\pi\rangle$ 的近似投影或反射。这正是第 5 节沿 schedule 逐级转移量子态所需的基本元件。

## 4. 小例子：两状态链

抽象的谱对应看一个能完全手算的例子最清楚。取 $\Omega=\{0,1\}$，对称的两状态链

$$
P=\begin{pmatrix}1-p & p\\ p & 1-p\end{pmatrix},
\qquad 0<p<\tfrac12.
$$

**第一步：经典谱。** 稳态是均匀分布 $\pi=(1/2,1/2)$（直接验证 $\pi P=\pi$；detailed balance 因 $P$ 对称且 $\pi$ 均匀而成立）。$P$ 的本征值：一行求和得 $\lambda_0=1$（本征向量 $(1,1)$）；另一本征向量 $(1,-1)$ 给出 $\lambda_1=1-2p$。所以谱隙

$$
\delta=2p.
$$

经典 mixing：偏差每步衰减 $1-2p$，收敛需 $\Theta(1/p)$ 步。

**第二步：量子相位。** 这里 $\pi$ 均匀，故 $D=\Pi^{1/2}P\Pi^{-1/2}=P$（对角因子 $\sqrt{(1/2)/(1/2)}=1$），$\lambda_1=1-2p=\cos\theta_1$，于是

$$
\theta_1=\arccos(1-2p)=2\arcsin\sqrt p,
$$

最后一步用了 $1-\cos\theta=2\sin^2(\theta/2)$ 代入 $\delta=2p$：$\sin(\theta_1/2)=\sqrt p$。$W$ 的非零相位为

$$
\pm2\theta_1=\pm4\arcsin\sqrt p.
$$

**第三步：对比。** $p\ll1$ 时 $\arcsin\sqrt p\approx\sqrt p$，相位隙 $\Delta\approx4\sqrt p$，相位检测成本 $\Theta(1/\sqrt p)$，而经典 mixing 是 $\Theta(1/p)$——指数 $1\to1/2$ 的平方加速在这个玩具模型里完全可见。取 $p=0.01$：经典约需 $\sim 1/(2p)=50$ 步量级，量子 walk 的相位 $2\theta_1=4\arcsin(0.1)\approx0.401$ rad，相位估计只需 $\sim 1/0.401\approx2.5$ 次 walk 量级的受控演化即可区分稳态与非稳态。

**第四步：稳态验证（可选但推荐动手）。** $|\pi\rangle=\frac{1}{\sqrt2}\big(|0\rangle|\phi_0\rangle+|1\rangle|\phi_1\rangle\big)$，其中 $|\phi_0\rangle=\sqrt{1-p}|0\rangle+\sqrt p|1\rangle$，$|\phi_1\rangle=\sqrt p|0\rangle+\sqrt{1-p}|1\rangle$。交换两寄存器后系数矩阵仍是同一个对称矩阵 $\sqrt{P(x,y)}/\sqrt2$，故态不变，$W|\pi\rangle=|\pi\rangle$，与 3.3 节的一般论证一致。

## 5. 沿 schedule 移动：相邻 Gibbs 态的 overlap 与 Quantum Zeno

有了"投影到某个温度的相干稳态"的元件，还需要回答：怎样从 $\beta_0$ 的态一路转移到 $\beta_f$ 的态，总成功率与总成本是多少。

### 5.1 单寄存器记号

为书写简洁，本节把相干 Gibbs 态缩写为单寄存器形式（振幅仍是概率平方根）：

$$
|\Pi_i\rangle=\sum_x\sqrt{\pi_i(x)}\,|x\rangle.
$$

所有 overlap 计算在这个记号下进行；回到完整双寄存器形式 $|\pi_i\rangle$ 时 overlap 数值相同，因为第二寄存器的部分只依赖于 $x$ 而不改变内积结构（对本节的估计而言足够）。

(overlap-quantum-zeno)=
### 5.2 相邻 overlap 的精确公式

**Lemma.** 相邻两个温度的相干 Gibbs 态的内积为

$$
\langle\Pi_i|\Pi_{i+1}\rangle
=\frac{Z\!\left(\frac{\beta_i+\beta_{i+1}}{2}\right)}
{\sqrt{Z(\beta_i)\,Z(\beta_{i+1})}}.
$$

**证明.** 从内积定义出发逐步计算：

$$
\langle\Pi_i|\Pi_{i+1}\rangle
=\sum_x\sqrt{\pi_i(x)\,\pi_{i+1}(x)}
=\sum_x\sqrt{\frac{e^{-\beta_i E(x)}}{Z(\beta_i)}\cdot\frac{e^{-\beta_{i+1}E(x)}}{Z(\beta_{i+1})}}.
$$

第一步是 $\langle\Pi_i|\Pi_{i+1}\rangle=\sum_x\sqrt{\pi_i(x)}\sqrt{\pi_{i+1}(x)}$（振幅非负，无需取复共轭的顾虑）；第二步代入 Gibbs 分布定义。合并根号内的指数：$\sqrt{e^{-\beta_i E}e^{-\beta_{i+1}E}}=e^{-(\beta_i+\beta_{i+1})E/2}$，于是

$$
\langle\Pi_i|\Pi_{i+1}\rangle
=\frac{\displaystyle\sum_x e^{-\frac{\beta_i+\beta_{i+1}}{2}E(x)}}{\sqrt{Z(\beta_i)Z(\beta_{i+1})}}
=\frac{Z\!\left(\frac{\beta_i+\beta_{i+1}}{2}\right)}{\sqrt{Z(\beta_i)Z(\beta_{i+1})}},
$$

最后一步只是认出分子正是中点逆温度 $\bar\beta=(\beta_i+\beta_{i+1})/2$ 处的配分函数定义。Q.E.D.

两个直接的推论：

- **overlap 总是 $\le1$**。配分函数的对数 $\log Z(\beta)$ 是 $\beta$ 的凸函数（其二阶导数是能量的方差 $\operatorname{Var}_\beta(E)\ge0$，见练习 6 第 3 题），故 $\log Z(\bar\beta)\le\frac12(\log Z(\beta_i)+\log Z(\beta_{i+1}))$，即分子不超过分母。
- **schedule 越细，overlap 越接近 1**。把 $\log Z$ 在中点做二阶 Taylor 展开，可得（启发式近似）

$$
\langle\Pi_i|\Pi_{i+1}\rangle
\approx\exp\!\left(-\frac{(\Delta\beta_i)^2}{8}\,\operatorname{Var}_{\bar\beta}(E)\right),
\qquad \Delta\beta_i=\beta_{i+1}-\beta_i,
$$

即 overlap 与 1 的偏差是二阶小量，系数由该温度下的能量涨落 $\operatorname{Var}(E)$ 控制。这正是"$L$ 的具体取值依赖能量方差与 cooling schedule"这一说法的定量来源：能量涨落大的温区（例如相变附近）需要更密的 schedule。

### 5.3 Quantum Zeno：逐级投影

QSA 的主循环是：

1. 制备 $|\Pi_0\rangle$（$\beta_0=0$ 即均匀叠加，Hadamard 即可完成）；
2. 对 $i=0,1,\ldots,L-1$：用第 3.5 节的相位检测，把当前态近似投影到 $|\Pi_{i+1}\rangle$ 方向（具体地，用 $W_{i+1}$ 的零相位检测）；
3. 输出 $|\Pi_L\rangle$。

每一步投影的理想成功概率是 $|\langle\Pi_i|\Pi_{i+1}\rangle|^2$。若相邻 overlap 与 $1$ 的偏差为 $\varepsilon_i^2$ 量级（即 $|\langle\Pi_i|\Pi_{i+1}\rangle|^2\ge1-\varepsilon_i^2$），则全程成功的概率

$$
\prod_{i=0}^{L-1}\big(1-\varepsilon_i^2\big)
\ge 1-\sum_i\varepsilon_i^2,
$$

只要 schedule 取得足够细，使 $\sum_i\varepsilon_i^2=O(1)$（例如每步 $\varepsilon_i^2=O(1/L)$），总成功率就保持常数。这种"频繁地测量一个缓慢漂移的态，态就被钉在漂移轨道上"的现象正是 **quantum Zeno 效应**：测量不再只是扰动，而是被用作引导态演化的工具。

### 5.4 总成本：逐项拆解

把各因子组装起来，全程的 walk 调用总量为

$$
\widetilde O\!\left(
\frac{L\cdot(\text{schedule factor})}
{\sqrt\delta}
\right).
$$

逐项解释：

- $1/\sqrt\delta$：每一次"投影到 $|\Pi_{i+1}\rangle$"由 $W_{i+1}$ 的相位检测实现，成本由最差温度的相位隙 $\sqrt\delta=\min_i\sqrt{\delta_i}$ 决定（3.5 节 Corollary）。**这就是平方加速所在的位置**——经典退火对应位置上是 $1/\delta$。
- $L$：schedule 的长度，即投影的次数。由 5.2 节的估计，它由能量方差沿 schedule 的积分决定：涨落越剧烈，需要的中间温度越多。
- schedule factor：每个投影步骤的额外开销，包括把"理想投影"做成高成功率酉操作的成本。朴素的投影-失败-重试会损失 Zeno 论证的成功率；更精细的做法是用 **fixed-point amplitude amplification**（不动点振幅放大）把每步投影做成任意接近确定性的操作，把失败/重复的开销压成对数或常数因子。这一项的具体形式依赖于实现细节，是 $\widetilde O$ 记号所隐藏的工程内容。

经典退火对应的总成本是 $\widetilde O(L\cdot(\text{schedule factor})/\delta)$。量子对经典的优势完全集中在谱隙因子上：$\delta^{-1}\to\delta^{-1/2}$。

(evolution-randomization)=
## 6. Evolution randomization 版本

完整相位估计在电路上较重（需要受控 $W$ 的幂次与 QFT）。Somma–Boixo–Barnum–Knill（Zoo 编号 177）给出了一个更轻的替代：**随机化演化时间**。

思想是：与其精确测量相位，不如随机选择一个演化时长 $t$（例如在 $[0,T]$ 中均匀取样），施加 $W_i^t$，然后丢弃关于 $t$ 的记录。考察它对 $W_i$ 的某个相位为 $\varphi$ 的本征分量的作用：演化 $t$ 步给该分量乘上 $e^{i\varphi t}$；对随机 $t$ 取平均后，该分量（在密度矩阵的意义上）被乘上退相干因子

$$
\left|\frac{1}{T}\int_0^T e^{i\varphi t}\,dt\right|
=\left|\frac{e^{i\varphi T}-1}{i\varphi T}\right|
=O\!\left(\frac{1}{|\varphi|T}\right).
$$

也就是说：非零相位 $\varphi$ 的分量被随机演化平均掉了（去相干），而零相位的稳态分量（$\varphi=0$，$e^{i\varphi t}\equiv1$）完全不受影响。净效果近似于"向稳态投影"这一非酉操作的随机实现。

要压低相位 $|\varphi|\ge\theta$ 的所有分量，需要 $|\varphi|T\gtrsim1$，即随机时间的范围取

$$
T=O\!\left(\frac{1}{|\theta|}\right)=O\!\left(\frac{1}{\sqrt\delta}\right),
$$

其中第二步用了相位隙 $\theta=\Theta(\sqrt\delta)$（第 3.4 节 Theorem）。反复执行"随机时长演化——把温度稍微调低一点"，就产生一连串有效的 Zeno 投影，把态沿 schedule 拖到低温。**gap 的平方优势完整保留**，因为 $T$ 依然由 $\sqrt\delta$ 而非 $\delta$ 决定。这就是 Somma–Boixo–Barnum–Knill 版本与早期相位估计版本（Zoo 编号 84）的主要实现差异：用随机化去相干换掉相干相位测量，电路更浅，分析更偏物理，渐近成本相同。

(readout-and-limitations)=
## 7. 读出最优解

得到 $|\Pi_L\rangle$ 后在计算基上测量，结果 $x$ 服从低温 Gibbs 分布 $\pi_{\beta_f}$。设最优集合的概率质量为

$$
p_*=\sum_{x\in S_*}\pi_{\beta_f}(x).
$$

分两种情形：

- **$p_*$ 是常数**（由 2.4 节的估计，取 $\beta_f\Delta E\gtrsim\log(|\Omega|/\eta)$ 即可让 $p_*\ge1-\eta$）：一次或常数次重复测量即可以高概率拿到最优构型。
- **$p_*$ 小但已知下界**：用振幅放大。把"制备 $|\Pi_L\rangle$ 并测量是否为最优"看作成功概率 $p_*$ 的子过程，振幅放大（第 3 章）把它降到

$$
O\!\left(\frac{1}{\sqrt{p_*}}\right)
$$

次 state preparation / reflection 调用。注意这里的 $1/\sqrt{p_*}$ 与 Grover 搜索的 $1/\sqrt{p}$ 是同一个平方根，来源完全相同。

最后一个诚实的提醒：输出候选 $x$ 之后，经典地计算 $E(x)$ 验证它能量低是容易的；但如果事先不知道全局最优值，要验证"$x$ **确为**最优"可能本身就很困难。退火类算法（无论经典还是量子）通常给出的是"以高概率找到低能/最优解"的承诺，而不是一个可供快速核查的 NP 式最优性证书。这一点在把 QSA 当作优化器使用时必须牢记。

## 8. 与绝热量子优化的区别

QSA 与绝热量子算法（adiabatic quantum optimization）共享"沿一条缓慢变化的路径走"的语言，但二者的输入、gap 与正确性定理完全不同，不能混用。对照如下：

**QSA：**

- 输入是一组经典 Markov chain 的转移矩阵 $P_i$（每个温度一个）；
- 加速的来源是谱隙到相位隙的映射 $\delta^{-1}\to\delta^{-1/2}$（第 3.4 节 Theorem）；
- 中间态是相干 Gibbs 态，振幅为经典 Gibbs 概率的平方根，测量即得经典分布的样本。

**绝热量子算法：**

- 输入是一条 Hamiltonian 路径 $H(s)$（从易制备的初态 Hamiltonian 插值到编码目标函数的末态 Hamiltonian）；
- 复杂度由路径上的最小 Hamiltonian 能隙与 $\|dH/ds\|$ 控制（绝热定理）；
- 中间的瞬时基态不必对应任何经典 Markov chain 的稳态，一般也没有"振幅 = 经典概率平方根"的解释。

特别地，**不能**把 QSA 的"经典谱隙开方"结论搬运到绝热算法上，也不能反过来用绝热能隙的下界去声称 QSA 的性能。两个 gap 是不同的数学对象：一个是经典随机矩阵 $1-\lambda_1$，一个是量子 Hamiltonian 的 $E_1-E_0$。

## 9. 何时没有实际优势

平方加速是真定理，但它的适用范围有明确的边界，三条主要限制如下。

**指数小的谱隙。** 若能量景观存在指数高的势垒（典型的受挫/玻璃型景观），任何局部更新的 Metropolis chain 的谱隙都是

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

QSA 把成本从 $e^{\Theta(n)}$ 降到 $e^{\Theta(n/2)}$——相对经典是实打实的平方改善，但**仍然指数**。QSA 不是 NP-hard 优化的普适多项式算法。

**walk oracle 的成本。** Szegedy walk 假定能相干高效地实现 $V|x\rangle|0\rangle=|x\rangle\sum_y\sqrt{P(x,y)}|y\rangle$，即计算一步转移概率并开方作为振幅。如果转移概率或能量差本身不能被高效地相干计算（例如 $E(x)$ 来自一个昂贵的经典子程序且没有可逆电路），walk oracle 的实现开销可能吃掉谱隙带来的全部收益。

**schedule 的权衡。** schedule 太细，则 $L$ 大，总成本里的 $L$ 因子膨胀；太粗，则相邻 overlap $|\langle\Pi_i|\Pi_{i+1}\rangle|$ 小，Zeno 论证失效（5.3 节的成功率估计不再成立，被迫放大重试次数）。5.2 节的估计表明最优粗细由能量方差决定，而能量方差沿 schedule 的行为往往事先未知——这是实际使用中的模型依赖点：渐近定理不替你做 schedule 设计。

总结这一节：**QSA 是对一组给定经典退火 chain 的通用二次加速**，它把 mixing 瓶颈开方，但不改变问题景观本身的难度结构。

## 10. 小结

**小结。**

- 经典模拟退火的瓶颈是每个温度处 Markov chain 的 mixing time $\widetilde O(1/\delta)$，而非降温深度（$\beta_f$ 只需 $O(\log|\Omega|)$ 量级）。
- Szegedy walk 把转移矩阵 $P$ 量子化为酉算子 $W=R_BR_A$；相干 Gibbs 稳态是 $W$ 的零相位本征态。
- 谱对应 $\lambda_j=\cos\theta_j\Rightarrow$ 相位 $\pm2\theta_j$，把 Markov 谱隙 $\delta$ 映成相位隙 $\Theta(\sqrt\delta)$，投影成本获得平方改进。
- 相邻温度的相干 Gibbs 态 overlap 由配分函数在中点的取值给出；schedule 足够细时 overlap 接近 1，quantum Zeno 效应保证逐级投影的总成功率为常数。
- 随机时长演化（evolution randomization）可以替代完整相位估计，同样保留 $\sqrt\delta$ 优势。
- 读出靠测量或振幅放大（$O(1/\sqrt{p_*})$）；指数小的谱隙开方后仍然指数，QSA 是通用二次加速而非 NP-hard 的多项式算法。

## 练习题

**练习 1【经典退火的瓶颈：mixing 与谱隙】**（→ [1.3 节](#mixing-spectral-gap)）

1. 写出逆温度 $\beta$ 下的 Gibbs 分布 $\pi_\beta$ 与配分函数 $Z(\beta)$ 的定义，并说明 $\beta_0=0$ 对应什么分布、为何无需任何结构即可制备。
2. 设可逆 Markov chain 的第二大本征值绝对值为 $1-\delta$。每乘一次转移矩阵 $P$，分布与稳态的偏差衰减多少？要把偏差缩小到 $\varepsilon$ 以内大约需要多少步？
3. 设 $\Omega$ 中只有一个基态（能量 $0$），其余 $|\Omega|-1$ 个态能量均为 $\Delta$。求保证非最优构型总质量 $\le\eta$ 的最小 $\beta$，并与 2.4 节的一般界 $\beta\Delta\gtrsim\log(|\Omega|/\eta)$ 比较：精确解与一般界相差多少？这说明一般界是否已经本质最优？

> 提示：写出 $Z(\beta)=1+(|\Omega|-1)e^{-\beta\Delta}$ 与非最优总质量的精确分式，再解不等式。

**练习 2【detailed balance 与 discriminant 对称化】**（→ [2.2 节](#detailed-balance-discriminant)）

1. 写出"稳态正确"条件 $\pi_iP_i=\pi_i$ 与 detailed balance 条件，并解释二者为何不同（环流型 chain 可以满足前者而不满足后者）。
2. 证明 discriminant $D=\Pi^{1/2}P\Pi^{-1/2}$ 的 $(x,y)$ 元等于 $\pi(x)P(x,y)/\sqrt{\pi(x)\pi(y)}$，从而由 detailed balance 推出 $D$ 对称；再说明 $D$ 与 $P$ 相似、本征值完全相同。

> 提示：$D=\Pi^{1/2}P\Pi^{-1/2}$ 本身就是一个对角相似变换。

**练习 3【Szegedy 量子化：isometry 与两次反射】**（→ [3.1 节](#szegedy-walk-construction)）

1. 写出 isometry 的定义 $V|x\rangle|0\rangle=|x\rangle\sum_y\sqrt{P(x,y)}|y\rangle$，验证每个 $|\phi_x\rangle$ 都归一化，并说明 $V$ 为什么保持内积。
2. 写出子空间 $\mathcal A$、$\mathcal B$ 与反射 $R_A=2\Pi_A-I$、$R_B=2\Pi_B-I$ 的定义，解释 $\mathcal A$ 与 $\mathcal B$ 各自编码的直觉（"从 $x$ 出发往哪走"与"从哪走来能到 $x$"），并说明 $W=R_BR_A$ 为何是两次反射合成的旋转。

> 提示：旋转角等于两反射轴夹角的两倍，即 Grover 算法一章用过的几何事实。

**练习 4【相干稳态的零相位】**（→ [3.3 节](#coherent-stationary-state)）

1. 写出相干稳态 $|\pi\rangle=\sum_x\sqrt{\pi(x)}|x\rangle\sum_y\sqrt{P(x,y)}|y\rangle$ 的定义，并验证它属于子空间 $\mathcal A$。
2. 设 $P$ 满足 detailed balance。逐步验证 $\mathrm{SWAP}|\pi\rangle=|\pi\rangle$，并由此说明 $W|\pi\rangle=|\pi\rangle$、本征相位为 $0$。

> 提示：关键是等式 $\sqrt{\pi(y)P(y,x)}=\sqrt{\pi(x)P(x,y)}$（对 detailed balance 两边开平方）。

**练习 5【谱隙到相位隙的平方根放大】**（→ [3.4 节](#phase-gap-square-root)）

1. 从 $\cos\theta=1-\delta$ 出发，用半角公式推导 $\theta=2\arcsin\sqrt{\delta/2}$，并验证 $\delta\to0$ 时 $\theta=\sqrt{2\delta}\,(1+O(\delta))$，从而 $\theta=\Theta(\sqrt\delta)$。
2. 对两状态链 $P=\begin{pmatrix}1-p & p\\ p & 1-p\end{pmatrix}$（$0<p<\tfrac12$，见第 4 节）计算谱隙 $\delta$ 与 walk 算子的非零相位，并取 $p=0.01$ 比较经典 mixing 步数与相位检测成本的数值量级。

> 提示：$\sin(\theta_1/2)=\sqrt p$，即 $\theta_1=2\arcsin\sqrt p$，非零相位为 $\pm2\theta_1$。

**练习 6【相邻 Gibbs 态 overlap 与 quantum Zeno】**（→ [5.2 节](#overlap-quantum-zeno)）

1. 设每步投影的理想成功概率满足 $|\langle\Pi_i|\Pi_{i+1}\rangle|^2\ge1-\varepsilon_i^2$。写出全程成功率的下界，并给出使总成功率为常数的 schedule 条件。
2. 推导 $\langle\Pi_i|\Pi_{i+1}\rangle=Z\big(\tfrac{\beta_i+\beta_{i+1}}{2}\big)/\sqrt{Z(\beta_i)Z(\beta_{i+1})}$，并对两能级系统 $E\in\{0,1\}$、$(\beta_i,\beta_{i+1})=(0,\ln3)$ 算出数值（参考值：约 $0.966$）。
3. 利用 $\frac{d^2}{d\beta^2}\log Z(\beta)=\operatorname{Var}_\beta(E)\ge0$ 说明 $\log Z$ 是凸函数，从而证明上一题中的 overlap 恒 $\le1$。这个结论的物理含义是什么？

> 提示：凸性给出 $\log Z\big(\tfrac{\beta_i+\beta_{i+1}}{2}\big)\le\frac12\big(\log Z(\beta_i)+\log Z(\beta_{i+1})\big)$。

**练习 7【Evolution randomization 替代相位估计】**（→ [第 6 节](#evolution-randomization)）

1. 对 $W$ 的相位为 $\varphi$ 的本征分量，计算随机时长演化（$t$ 在 $[0,T]$ 均匀取样后丢弃记录）的平均保留因子 $\big|\frac{1}{T}\int_0^T e^{i\varphi t}\,dt\big|$，并说明 $\varphi=0$ 的稳态分量为何完全不受影响。
2. 说明要把所有 $|\varphi|\ge\Theta(\sqrt\delta)$ 的分量压低，随机时间范围 $T$ 应取什么量级，并解释它为何与相位估计版本一样保住了 $\sqrt\delta$ 的平方加速。

> 提示：$|e^{i\varphi T}-1|=2|\sin(\varphi T/2)|$。

**练习 8【读出与适用边界】**（→ [第 7 节](#readout-and-limitations)）

1. 写出最优集合概率质量 $p_*$ 的定义，并说明为什么取 $\beta_f\Delta E\gtrsim\log(|\Omega|/\eta)$ 后一次或常数次测量即可以高概率读到最优构型。
2. 设 $p_*$ 小但已知下界。说明振幅放大能把整个读出流程的重复次数降到多少（以 $p_*$ 表示），并指出它与 Grover 搜索的平方根为何来源相同。
3. QSA 的复杂度由经典 Markov 谱隙 $\delta$ 控制，绝热优化由 Hamiltonian 能隙控制。各举一个"一个 gap 大、另一个 gap 可以任意小"的直观场景，说明为什么两套结论不能互相搬运；并据此解释为什么 QSA 的二次加速定理不构成 NP-hard 问题的多项式时间算法。

> 提示：两个 gap 是不同的数学对象——随机矩阵的 $1-\lambda_1$ 与 Hamiltonian 的 $E_1-E_0$。

## 参考文献

- Zoo 编号 84：Somma、Boixo 与 Barnum, [Quantum Simulated Annealing](https://arxiv.org/abs/0712.1008).
- Zoo 编号 177：Somma、Boixo、Barnum 与 Knill, [Quantum Simulations of Classical Annealing Processes](https://arxiv.org/abs/0804.1571).
- Zoo 编号 85、135：Szegedy quantized Markov chains 与 $\sqrt{\delta\epsilon}$ rule。
- Zoo 编号 265：Montanaro 的量子 Monte Carlo 加速。