量子模拟退火

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

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

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 )},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}$ 的样本。

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）。那么混合到距离稳态 $\epsilon$ 以内大约需要

$$t_{\mathrm{mix}}=O\left(\frac{1}{\delta }\log \frac{1}{\epsilon {\pi }_{\min }}\right)$$

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

$$\delta =\underset{i}{\min }{\delta }_i.$$

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

1.4 量子加速的历史线索

Szegedy 在 2004 年前后给出了任意经典 Markov chain 的相干量子化（Zoo 编号 85、135），其 walk 算子的相位隙是经典谱隙的平方根量级，并由此得到”$\sqrt{\delta ϵ}$ 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 )},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 节推导）。

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=\mathrm{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-\underset{j\ge 1}{\max }|{\lambda }_j|.$$

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

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

记能量最低的构型集合为 $S_{\ast }$，最低能量为 $E_{\ast }$，并把能隙记作

$$\Delta E=\underset{x\notin S_{\ast }}{\min }E(x)-E_{\ast }$$

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

$$\sum _{x\notin S_{\ast }}{\pi }_{\beta }(x)=\frac{{\sum }_{x\notin S_{\ast }}{e}^{-\beta E(x)}}{Z(\beta )}\le \sum _{x\notin S_{\ast }}{e}^{-\beta E(x)}\le |\Omega |e^{-\beta \Delta E},$$

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

$$|\Omega |e^{-{\beta }_f\Delta E}\le \eta ⟺{\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$。

3.1 从转移矩阵到 isometry

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

$$V|x⟩|0⟩=|x⟩\sum _y\sqrt{P(x,y)}|y⟩=:|x⟩|{\varphi }_x⟩.$$

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

$$\mathcal{A}=\mathrm{im}V=\mathrm{span}\{|x⟩|{\varphi }_x⟩:x\in \Omega \}.$$

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

$$\mathcal{B}=\mathrm{SWAP}\mathcal{A}=\mathrm{span}\{|{\varphi }_x⟩|x⟩:x\in \Omega \}.$$

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

3.2 两次反射合成的 walk

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

$$R_A=2{\Pi }_A-I,R_B=2{\Pi }_B-I,$$

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

$$W=R_B{R}_A.$$

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

3.3 稳态是零相位本征态

定义相干稳态（coherent stationary state）

$$|\pi ⟩=\sum _x\sqrt{\pi (x)}|x⟩\sum _y\sqrt{P(x,y)}|y⟩=\sum _x\sqrt{\pi (x)}|x⟩|{\varphi }_x⟩.$$

它显然属于 $\mathcal{A}$（就是 $V({\sum }_x\sqrt{\pi (x)}|x⟩)|0⟩$ 的形状）。关键计算是它同时属于 $\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⟩|y⟩=\sum _{x,y}\sqrt{\pi (x)}\sqrt{P(x,y)}|x⟩|y⟩=|\pi ⟩,$$

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

$$W|\pi ⟩=R_B{R}_A|\pi ⟩=|\pi ⟩,$$

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

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|\le 1$，可以写成余弦）。则 $W$ 限制在 $\mathcal{A}+\mathcal{B}$ 上的非零本征相位为 $\pm 2{\theta }_j$，每个 $j$ 给出一对共轭相位。

证明概要. 取 $D$ 的第 $j$ 个归一化本征向量 $v_j$，$D{v}_j={\lambda }_j{v}_j$。可以构造一对态

$$|a_j⟩=\sum _x{v}_j(x)|x⟩|{\varphi }_x⟩\in \mathcal{A},|b_j⟩=\mathrm{SWAP}\sum _x{v}_j(x){\Pi }^{1/2}\cdots$$

更直接的说法是：$\mathcal{A}$ 的生成元 $|x⟩|{\varphi }_x⟩$ 与 $\mathcal{B}$ 的生成元 $|{\varphi }_{x^{\prime }}⟩|x^{\prime }⟩$ 的内积为

$$⟨{\varphi }_{x^{\prime }}|⟨x^{\prime }|x⟩|{\varphi }_x⟩={\delta }_{x,x^{\prime }}\sum _y\sqrt{P(x,y)P(y,x)}={\delta }_{x,x^{\prime }}D\text{ 结构中的对称量},$$

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

$${\Pi }_A|b_j⟩={\lambda }_j|a_j⟩,{\Pi }_B|a_j⟩={\lambda }_j|b_j⟩,$$

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

完整的严格证明需要处理 $\mathcal{A}+\mathcal{B}$ 的直和分解与 ${\lambda }_j=\pm 1$ 的边界情形，这里略去；本词条只需要结论本身。

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}⟹\sin \frac{{\theta }_1}{2}=\sqrt{\frac{\delta }{2}}⟹{\theta }_1=2\arcsin \sqrt{\frac{\delta }{2}}.$$

由 Lemma，$W$ 最近的非零相位是 $\pm 2{\theta }_1$，即

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

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

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

Q.E.D.

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

3.5 相位检测的成本

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

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

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

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

4. 小例子：两状态链

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

$$P=\left(\begin{array}{cc}1-p& p\\ p& 1-p\end{array}\right),0<p<\frac{1}{2}.$$

第一步：经典谱。 稳态是均匀分布 $\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$ 的非零相位为

$$\pm 2{\theta }_1=\pm 4\arcsin \sqrt{p}.$$

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

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

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

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

5.1 单寄存器记号

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

$$|{\Pi }_i⟩=\sum _x\sqrt{{\pi }_i(x)}|x⟩.$$

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

5.2 相邻 overlap 的精确公式

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

$$⟨{\Pi }_i|{\Pi }_{i+1}⟩=\frac{Z\left(\frac{{\beta }_i+{\beta }_{i+1}}{2}\right)}{\sqrt{Z({\beta }_i)Z({\beta }_{i+1})}}.$$

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

$$⟨{\Pi }_i|{\Pi }_{i+1}⟩=\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})}}.$$

第一步是 $⟨{\Pi }_i|{\Pi }_{i+1}⟩={\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}$，于是

$$⟨{\Pi }_i|{\Pi }_{i+1}⟩=\frac{\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 总是 $\le 1$。配分函数的对数 $\log Z(\beta )$ 是 $\beta$ 的凸函数（其二阶导数是能量的方差 ${\mathrm{Var}}_{\beta }(E)\ge 0$，见习题 5），故 $\log Z(\bar{\beta })\le \frac{1}{2}(\log Z({\beta }_i)+\log Z({\beta }_{i+1}))$，即分子不超过分母。
• schedule 越细，overlap 越接近 1。把 $\log Z$ 在中点做二阶 Taylor 展开，可得（启发式近似）

$$⟨{\Pi }_i|{\Pi }_{i+1}⟩\approx \exp \left(-\frac{(\Delta {\beta }_i{)}^2}{8}{\mathrm{Var}}_{\bar{\beta }}(E)\right),\Delta {\beta }_i={\beta }_{i+1}-{\beta }_i,$$

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

5.3 Quantum Zeno：逐级投影

QSA 的主循环是：

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

每一步投影的理想成功概率是 $|⟨{\Pi }_i|{\Pi }_{i+1}⟩{|}^2$。若相邻 overlap 与 $1$ 的偏差为 ${\epsilon }_i^2$ 量级（即 $|⟨{\Pi }_i|{\Pi }_{i+1}⟩{|}^2\ge 1-{\epsilon }_i^2$），则全程成功的概率

$$\prod _{i=0}^{L-1}(1-{\epsilon }_i^2)\ge 1-\sum _i{\epsilon }_i^2,$$

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

5.4 总成本：逐项拆解

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

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

逐项解释：

• $1/\sqrt{\delta }$：每一次”投影到 $|{\Pi }_{i+1}⟩$“由 $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（不动点振幅放大）把每步投影做成任意接近确定性的操作，把失败/重复的开销压成对数或常数因子。这一项的具体形式依赖于实现细节，是 $\tilde{O}$ 记号所隐藏的工程内容。

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

6. Evolution randomization 版本

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

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

$$\left|\frac{1}{T}{\int }_0^T{e}^{i\phi t}dt\right|=\left|\frac{e^{i\phi T}-1}{i\phi T}\right|=O\left(\frac{1}{|\phi |T}\right).$$

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

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

$$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）的主要实现差异：用随机化去相干换掉相干相位测量，电路更浅，分析更偏物理，渐近成本相同。

7. 读出最优解

得到 $|{\Pi }_L⟩$ 后在计算基上测量，结果 $x$ 服从低温 Gibbs 分布 ${\pi }_{{\beta }_f}$。设最优集合的概率质量为

$$p_{\ast }=\sum _{x\in S_{\ast }}{\pi }_{{\beta }_f}(x).$$

分两种情形：

• $p_{\ast }$ 是常数（由 2.4 节的估计，取 ${\beta }_f\Delta E\gtrsim \log (|\Omega |/\eta )$ 即可让 $p_{\ast }\ge 1-\eta$）：一次或常数次重复测量即可以高概率拿到最优构型。
• $p_{\ast }$ 小但已知下界：用振幅放大。把”制备 $|{\Pi }_L⟩$ 并测量是否为最优”看作成功概率 $p_{\ast }$ 的子过程，振幅放大把它降到

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

次 state preparation / reflection 调用。注意这里的 $1/\sqrt{p_{\ast }}$ 与 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 能隙与 $\Vert dH/ds\Vert$ 控制（绝热定理）；
• 中间的瞬时基态不必对应任何经典 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⟩|0⟩=|x⟩{\sum }_y\sqrt{P(x,y)}|y⟩$，即计算一步转移概率并开方作为振幅。如果转移概率或能量差本身不能被高效地相干计算（例如 $E(x)$ 来自一个昂贵的经典子程序且没有可逆电路），walk oracle 的实现开销可能吃掉谱隙带来的全部收益。

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

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

10. 小结与习题

小结。

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

习题。

1. （谱隙到相位隙）从 $\cos \theta =1-\delta$ 出发，用半角公式推导 $\theta =2\arcsin \sqrt{\delta /2}$，并验证 $\delta \to 0$ 时 $\theta =\sqrt{2\delta }(1+O(\delta ))$，从而 $\theta =\Theta (\sqrt{\delta })$。
2. （稳态的零相位）设 $P$ 满足 detailed balance，$|\pi ⟩={\sum }_x\sqrt{\pi (x)}|x⟩{\sum }_y\sqrt{P(x,y)}|y⟩$。逐步验证 $\mathrm{SWAP}|\pi ⟩=|\pi ⟩$，并由此说明 $W|\pi ⟩=|\pi ⟩$。（提示：关键是等式 $\sqrt{\pi (y)P(y,x)}=\sqrt{\pi (x)P(x,y)}$。）
3. （overlap 公式）推导 $⟨{\Pi }_i|{\Pi }_{i+1}⟩=Z(\frac{{\beta }_i+{\beta }_{i+1}}{2})/\sqrt{Z({\beta }_i)Z({\beta }_{i+1})}$，并对两能级系统 $E\in \{0,1\}$、$({\beta }_i,{\beta }_{i+1})=(0,\ln 3)$ 算出数值（参考值：约 $0.966$）。
4. （终端温度）设 $\Omega$ 中只有一个基态（能量 $0$），其余 $|\Omega |-1$ 个态能量均为 $\Delta$。求保证非最优总质量 $\le \eta$ 的最小 $\beta$，并与 2.4 节的一般界 $\beta \Delta \gtrsim \log (|\Omega |/\eta )$ 比较：单基态情形可以省掉哪个因子？
5. （overlap 的上界）利用 $\frac{d^2}{d{\beta }^2}\log Z(\beta )={\mathrm{Var}}_{\beta }(E)\ge 0$ 说明 $\log Z$ 是凸函数，从而证明习题 3 中的 overlap 恒 $\le 1$。这个结论的物理含义是什么？
6. （概念辨析）QSA 的复杂度由经典 Markov 谱隙 $\delta$ 控制，绝热优化由 Hamiltonian 能隙控制。各举一个”一个 gap 大、另一个 gap 可以任意小”的直观场景，说明为什么两套结论不能互相搬运；并据此解释为什么 QSA 的二次加速定理不构成 NP-hard 问题的多项式时间算法。

参考文献

• Zoo 编号 84：Somma、Boixo 与 Barnum, Quantum Simulated Annealing.
• Zoo 编号 177：Somma、Boixo、Barnum 与 Knill, Quantum Simulations of Classical Annealing Processes.
• Zoo 编号 85、135：Szegedy quantized Markov chains 与 $\sqrt{\delta ϵ}$ rule。
• Zoo 编号 265：Montanaro 的量子 Monte Carlo 加速。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch13-topology-statistical-physics/quantum-simulated-annealing
• 内容遵循 CC BY-NC-SA 4.0 许可协议