量子模拟退火：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\)。

本课知识点

  1. 经典退火的瓶颈：mixing 与谱隙——能写出 Gibbs 分布与冷却 schedule，由第二大本征值 \(1-\delta\) 解释 mixing time 为 \(\widetilde O(1/\delta)\)，并说明整个退火为何被 \(\delta=\min_i\delta_i\) 卡住。

  2. detailed balance 与 discriminant 对称化——能写出 detailed balance 条件，验证 discriminant \(D=\Pi^{1/2}P\Pi^{-1/2}\) 是与 \(P\) 同谱的对称矩阵，并说明它是连接经典谱与量子相位的桥梁。

  3. Szegedy 量子化：isometry 与两次反射——能写出 isometry \(V\) 与子空间 \(\mathcal A\)、\(\mathcal B\) 的定义，说明 walk 算子 \(W=R_BR_A\) 的构造及其与 Grover 型反射的几何联系。

  4. 相干稳态的零相位——能用 detailed balance 证明 \(\mathrm{SWAP}|\pi\rangle=|\pi\rangle\)，从而推出 \(W|\pi\rangle=|\pi\rangle\)、稳态对应零相位。

  5. 谱隙到相位隙的平方根放大——能由 \(\lambda_j=\cos\theta_j\) 推导非零本征相位 \(\pm2\theta_j\) 与相位隙 \(\Delta=\Theta(\sqrt\delta)\)，并计算稳态投影成本 \(\widetilde O(1/\sqrt\delta)\)。

  6. 相邻 Gibbs 态 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 替代相位估计——能计算随机时长演化对相位 \(\varphi\) 分量的退相干因子，并说明取 \(T=\Theta(1/\sqrt\delta)\) 时它与相位估计版本同样完成向稳态的投影。

  8. 读出与适用边界——能比较 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}\) 的样本。

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 节推导）。

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\)。

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 节的主题。

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 算子下相位不转动的态。

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\}\)，对称的两状态链

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

第一步：经典谱。 稳态是均匀分布 \(\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\) 而不改变内积结构（对本节的估计而言足够）。

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}\)。

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

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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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\)。

参考文献