技术摘要：量子增强型薛定谔桥采样

问题陈述

本文研究了有限状态空间 $\chi$（大小为 $N$）上的动态薛定谔桥问题。给定一个具有转移核 $P$ 的参考马尔可夫过程 $P$，以及预设的初始分布 $\mu_0$ 和终端分布 $\mu_T$，目标是寻找一个路径测度 $Q^*$，在满足边际约束 $Q_0 = \mu_0$ 和 $Q_T = \mu_T$ 的条件下，最小化相对熵（Kullback–Leibler 散度）$KL(Q \| P)$。

该问题被分解为两个截然不同的计算任务：

1. 端点耦合（Endpoint Coupling）： 计算端点 $(X_0, X_T)$ 的最优联合分布 $Q^*_{0,T}$。这可以简化为一个静态薛定岭桥问题，通过矩阵缩放（寻找薛定谔势函数 $\phi^\circ, \phi^*$）来解决。
2. 条件路径采样（Conditional Path Sampling）： 从给定特定端点对 $(a, b)$（来自 $Q^*_{0,T}$）的条件参考马尔可夫桥 $P(\cdot | X_0=a, X_T=b)$ 中采样轨迹 $x_{0:T}$。

本文还将该框架扩展到了包含**加性运行成本（additive running costs）**的情况，即目标函数中包含一个期望累积成本项 $\mathbb{E}_Q[\sum g(X_t)]$。

方法论

作者提出了一种混合量子-经典方法，针对分解后的每个组件利用特定的量子算法。

1. 用于端点耦合的量子矩阵缩放

为了计算薛定谔势函数，作者改编了一种量子有界盒牛顿法（基于 Gribling 和 Nieuwboer [14]）。

• 公式化： 该问题被转化为最小化一个涉及对数缩放变量的凸势函数 $f(x, y)$。
• 量子加速： 该算法利用量子振幅估计来近似梯度，并利用量子图稀疏化来构建稀疏 Hessian 近似。
• 访问模型： 该方法假设对参考端点矩阵 $P_{0,T}$ 和边际分布具有相干条目查询（coherent entry-query）访问权限。

2. 用于条件路径采样的量子吉布斯采样器

为了从条件马尔可夫桥 $P_{a,b}$ 中采样轨迹，作者开发了一种基于量子行走（quantum walks）的量子吉布斯采样器。

• 经典基准： 经典吉布斯采样器每次更新一个内部坐标，根据其邻居的条件分布进行重采样。其收敛速率取决于吉布斯核的谱隙 $\delta$。
• 量子构建：
  • 作者构建了吉布斯核 $K$ 的投影幺正编码（PUE）。
  • 他们在路径空间上定义了一个量子行走 $W$。由于量子行走的谱性质，经典核中的谱隙 $\delta$ 会转化为量子行走中量级为 $\sqrt{\delta}$ 的相位间隙。
  • 振幅放大： 通过模拟 $T-1$ 步的参考链并固定最终端点来准备初始状态。该状态与目标平稳态具有已知的重叠度。使用振幅放大技术来提升投影到平稳态的概率。
  • 投影算子近似： 使用量子奇异值变换（或量子信号处理）技术实现对平稳态投影算子的多项式近似。

3. 向加性成本的扩展

对于具有运行成本 $g$ 的问题，作者展示了如何将其转化为带有重加权参考律 $\tilde{V}$ 的标准薛定谔桥。

• 重加权涉及指数因子 $e^{-g(x_t)}$。
• 加权吉布斯核的谱隙分析经过调整，以考虑成本范围 $\Delta_g = \max g - \min g$，引入了一个 $e^{-\Delta_g}$ 因子来修正谱隙下界。

核心贡献与结果

1. 马尔可夫桥的谱隙界限

本文确定了马尔可夫桥在路径空间上经典吉布斯采样器的谱隙 $\delta$ 的下界：
$$\delta \geq \frac{\omega_-^4}{T^2 N^3}$$
其中 $\omega_-$ 是转移核的均匀正性参数。该界限是使用**规范路径法（canonical paths method）**推导出的。至关重要的是，尽管路径空间的大小是指数级的（$N^{T-1}$），该结果仍然成立，这为量子加速分析提供了必要的定量输入。

2. 采样复杂度的量子加速

量子吉布斯采样器实现了对时间跨度 $T$ 的线性依赖，而经典吉布斯采样器则是二次依赖。

• 经典复杂度： $O\left( \frac{T^2 N^3}{\omega_-^4} \log \frac{N}{\omega_- \epsilon} \right)$ 次更新。
• 量子复杂度： $O\left( \frac{T N^2}{\omega_-^{5/2}} \log \frac{N}{\omega_- \epsilon} \right)$ 次行走原语调用。
• 机制： 这种改进源于量子行走采样中对谱隙的平方根依赖（$\delta^{-1/2}$ 对比 $\delta^{-1}$）。

3. 矩阵缩放中的量子加速

在计算端点耦合时，量子有界盒牛顿法改善了对状态空间大小 $N$ 的依赖关系：

• 经典复杂度： $\tilde{O}(B N^2)$（其中 $B$ 是势函数的界）。
• 量子复杂度： $\tilde{O}(B^2 N^{3/2} / \epsilon^2)$。
• 机制： 这种改进来自于使用量子振幅估计和稀疏化技术，将矩阵缩放复杂度从二次方降低到在固定精度下的 $N^{3/2}$。

4. 处理运行成本

论文对加性成本如何影响采样过程进行了严格分析。虽然谱隙界限会因 $e^{-\Delta_g}$ 因子而退化，但作者强调了一个关键的初始化挑战：如果初始状态没有考虑到运行成本，则其与目标状态的重叠度可能会随 $T$ 指数级衰减。论文指出，虽然量子方法保留了对谱隙的平方根改进，但整体加速效果取决于初始重叠度 $c_g$ 和成本范围 $\Delta_g$。

重要性与主张

本文声称提供了一个完整的量子增强型动态薛定谔桥采样框架。其重要性在于：

1. 分解策略： 它成功地将问题分解为端点耦合和条件路径采样，并为每个部分应用了最合适的量子算法。
2. 显式的复杂度界限： 它为两个组成部分提供了显式的、非渐近的查询复杂度界限，区分了算子调用次数与总计算时间。
3. 适度的加速主张： 作者谨慎地指出，量子采样器对 $T$ 的线性依赖是对局部吉布斯（local Gibbs）经典采样器的特定改进。他们并未声称相对于所有经典桥采样器（例如，直接拒绝采样可能有不同的缩放特性）具有无条件的二次加速。同样，矩阵缩放的加速是以特定的输入访问模型（相干条目查询）以及端点核 $P_{0,T}$ 可被高效构建为前提的。
4. 初始化敏感性： 论文明确警告，对于具有运行成本的问题，如果初始状态准备是标准的，那么“量子加速”可能无法保证，因为与目标状态的重叠度会随 $T$ 指数级消失。这突出了该量子方法在成本敏感场景下的实际应用约束。

总之，本文证明了通过利用量子行走和量子矩阵缩放，可以利用马尔可夫结构的特性，在满足特定的访问假设和初始化条件的情况下，实现对状态空间大小（$N$）和时间跨度（$T$）依赖关系的多项式级改进。