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

经典 simulated annealing 缓慢提高逆温度，让 Markov chain 的稳态从易制备分布移动到低能量集中分布。量子 simulated annealing（QSA）不是把目标函数直接变成绝热 Hamiltonian，而是相干量子化**同一组经典转移矩阵**；Szegedy walk 将 spectral gap $\delta$ 变成 phase gap $\Theta(\sqrt\delta)$，使 mixing/投影成本获得平方改进。

## 1. 经典退火框架

有限状态空间 $\Omega$、能量 $E(x)$。在逆温度 $\beta$：

$$
\pi_\beta(x)=\frac{e^{-\beta E(x)}}{Z(\beta)}.
$$

选择 schedule

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

每步运行可逆 Markov chain $P_i$，满足 detailed balance

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

若第二大本征值绝对值为 $1-\delta_i$，mixing 需约 $1/\delta_i$（乘对数与 warm-start 因子）。整体瓶颈

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

温度最终要大到 ground set $S_*$ 有足够 Gibbs 质量；若能隙 $\Delta E$ 已知，粗略要求

$$
\beta_f\Delta E
\gtrsim\log(|\Omega|/\eta)
$$

才能让非最优总概率不超过 $\eta$。

## 2. Szegedy quantization

定义 isometry

$$
V_i|x\rangle|0\rangle
=|x\rangle
\sum_y\sqrt{P_i(x,y)}|y\rangle.
$$

令 $\mathcal A_i=\operatorname{im}V_i$，交换两寄存器得到 $\mathcal B_i$。对两子空间反射

$$
R_{A_i}=2\Pi_{A_i}-I,\qquad
R_{B_i}=2\Pi_{B_i}-I,
$$

Szegedy walk

$$
W_i=R_{B_i}R_{A_i}.
$$

Coherent stationary state

$$
|\pi_i\rangle
=\sum_x\sqrt{\pi_i(x)}|x\rangle
\sum_y\sqrt{P_i(x,y)}|y\rangle
$$

同时位于 $\mathcal A_i\cap\mathcal B_i$，故 $W_i$ 本征相位为 0。

若 $P_i$ 本征值为 $\lambda_j=\cos\theta_j$，$W_i$ 对应非零相位约 $\pm2\theta_j$。当 $\lambda_2=1-\delta_i$：

$$
\theta_2\approx\sqrt{2\delta_i},
$$

所以 phase gap

$$
\Delta_i=\Theta(\sqrt{\delta_i}).
$$

Phase detection 对零相位稳态做投影/反射只需 $\widetilde O(1/\sqrt{\delta_i})$ 次 walk，而经典 mixing 是 $\widetilde O(1/\delta_i)$。

## 3. 相邻 Gibbs 态 overlap

简化写单寄存器 coherent Gibbs state

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

相邻 overlap

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

若 schedule 足够细，该值接近 1。QSA 从易制备 $|\Pi_0\rangle$ 开始，依次近似测量/投影到 $|\Pi_1\rangle,\ldots,|\Pi_L\rangle$。

Quantum Zeno 原理：若每对态夹角小，连续成功投影的总概率保持常数。每个投影由 $W_i$ phase detection 实现，故总 walk cost 约

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

更精细的 fixed-point amplification 可减少失败/重复，具体 $L$ 依能量方差与 cooling schedule。

## 4. Evolution randomization 版本

不显式做高精度 phase estimation，也可随机选择演化时间 $t$ 并施加 $W_i^t$。对非零相位本征态，随机 $t$ 使相位平均去相干；零相位稳态不变。反复“随机演化--轻微改变温度”产生有效 Zeno 投影。

为压低相位 $\theta$ 的分量，随机时间范围需

$$
T=O(1/|\theta|)
=O(1/\sqrt\delta),
$$

仍保留 gap 平方优势。这是 Somma--Boixo--Barnum--Knill 版本与早期 phase-estimation 版本的主要实现差异。

## 5. 读出最优解

得到 $|\Pi_L\rangle$ 后在计算基测量，结果服从 $\pi_{\beta_f}$。若最优集合概率

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

为常数，一次/常数重复即可；若仅有已知小 $p_*$，可用 amplitude amplification 降到 $O(1/\sqrt{p_*})$ 次 state preparation/reflection。

输出候选后经典计算 $E(x)$ 验证其能量，但若不知道全局 optimum value，验证“确为最优”可能本身困难。退火算法通常给高概率找到低能/最优的承诺，而非短 NP-style 最优性证书。

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

QSA：

- 输入是经典 Markov chains $P_i$；
- 加速来自 $\delta^{-1}\to\delta^{-1/2}$；
- coherent state 振幅为经典 Gibbs 概率平方根。

绝热量子算法：

- 输入是 Hamiltonian 路径 $H(s)$；
- 复杂度由 Hamiltonian 能隙与导数控制；
- 中间 ground state 不必对应任何经典 Markov 稳态。

二者都使用“缓慢路径”语言，但 gap、oracle 与正确性定理不同，不能把 QSA 的平方 mixing 优势当作绝热能隙结果。

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

若能量景观有指数高 barrier，局部 Metropolis chain 的

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

QSA 变成 $e^{\Theta(n/2)}$：相对经典平方改善，但仍指数。若一步转移概率/能量差不能相干高效计算，walk oracle 也昂贵。Schedule 太细使 $L$ 大，太粗又使相邻 overlap 小。

因此 QSA 是对给定 classical annealing chain 的通用 quadratic acceleration，不是 NP-hard optimization 的普适多项式算法。

## 8. 小结与习题

- Szegedy walk 的零相位态编码 Gibbs 稳态。
- Markov eigen-gap $\delta$ 映成 phase gap $\Theta(\sqrt\delta)$。
- Zeno/随机演化沿 cooling schedule 转移 coherent Gibbs states。
- 最终测量/振幅放大输出低能解；指数小 gap 仍导致指数时间。

1. 从 $\cos\theta=1-\delta$ 推导 $\theta=\Theta(\sqrt\delta)$。
2. 推导相邻 coherent Gibbs states overlap。
3. 给两能级系统计算达到 ground probability $1-\eta$ 所需 $\beta$。
4. 比较 QSA Markov gap 与绝热 Hamiltonian gap。

## 参考文献

- 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 加速。