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

参考文献