技术摘要：具有采样反馈的耗散量子多权重算法

1. 问题陈述

本文探讨了在近期待用量子硬件上实现真正的计算优势所面临的挑战。虽然已经提出了量子多权重（MMW）算法，但许多算法依赖于期望值（这在经典上是可高效模拟的）或需要对量子算子进行相干访问。作者识别出了一个差距：现有的提议往往未能利用量子态制备固有的复杂性。

核心问题在于构建一种在线学习原语，其反馈机制本身在经典上是不可计算的。具体而言，作者旨在将从常温吉布斯态（Gibbs state）中进行采样的计算困难性（Bergamaschi, Chen, 和 Liu [BCL] 最近证明了这一问题的难度）提升到一种物理可实现的学习算法中。挑战在于如何设计开放系统动力学，以制备这些困难的吉布斯态，同时保持对硬件噪声的鲁棒性，并证明这种物理实现能够产生相对于经典学习者的学习理论上的分离。

作者引入了具有采样反馈的耗散量子多权重算法（DQMW-Sample）。该方法集成了三个不同的领域：

• 工程化耗散动力学： 系统并非进行幺正演化，而是在随时间变化的 Davies 生成器（一种 Lindblad 耗散器）下演化。系统-环境耦合经过设计，使得动力学的唯一稳态为吉布斯态 $\rho_{Gibbs}(t) \propto \exp(-\beta_{eff}(t) H_{eff}(t))$，其中 $H_{eff}(t)$ 是累积损失哈密顿量。
• 采样反馈： 与基于期望值的变体不同，DQMW-Sample 在每一轮对制备好的吉布斯态进行单次计算基测量。测量结果 $|i_t\rangle$ 为乘法更新提供损失反馈。这一采样步骤是所提出的计算困难性的来源。
• 复杂度理论归约： 作者通过将 BCL 困难性结果（针对特定 $O(1)$-局部哈密顿量的常温吉布斯采样问题）归约为 DQMW-Sample 的反馈循环。他们定义了一个“困难窗口”，其中累积损失对应于一个 BCL 困难实例。
• 噪声分析： 理论分析界定了由硬件噪声引起的遗憾（regret）。作者证明了工程化耗散器的谱隙（$\gamma_0$）可以收缩偏离目标态的偏差。他们引入了一种“平衡耗散调度”，其中 $\gamma_0 = \Theta(\sqrt{T})$，以确保在假设噪声强度（$\delta$）和耗散率可以独立控制的前提下，实现亚线性的噪声诱导遗憾。

2. 方法论

作者引入了 DQMW-Sample。该方法集成了三个不同的领域：

• 工程化耗散动力学： 系统并非进行幺正演化，而是在随时间变化的 Davies 生成器（一种 Lindblad 耗散器）下演化。系统-环境耦合经过设计，使得动力学的唯一稳态为吉布斯态 $\rho_{Gibbs}(t) \propto \exp(-\beta_{eff}(t) H_{eff}(t))$，其中 $H_{eff}(t)$ 是累积损失哈密顿量。
• 采样反馈： 与基于期望值的变体不同，DQMW-Sample 在每一轮对制备好的吉布斯态进行单次计算基测量。测量结果 $|i_t\rangle$ 为乘法更新提供损失反馈。这一采样步骤是所提出的计算困难性的来源。
• 复杂度理论归约： 作者通过将 BCL 困难性结果（针对特定 $O(1)$-局部哈密顿量的常温吉布斯采样问题）归约为 DQMW-Sample 的反馈循环。他们定义了一个“困难窗口”，其中累积损失对应于一个 BCL 困难实例。
• 噪声分析： 理论分析界定了由硬件噪声引起的遗憾（regret）。作者证明了工程化耗散器的谱隙（$\gamma_0$）可以收缩偏离目标态的偏差。他们引入了一种“平衡耗散调度”，其中 $\gamma_0 = \Theta(\sqrt{T})$，以确保在假设噪声强度（$\delta$）和耗散率可以独立控制的前提下，实现亚线性的噪声诱导遗憾。

3. 核心贡献

理论贡献

1. 将 BCL 困难性提升至在线学习： 本文证明了 DQMW-Sample 的逐轮采样反馈在明确的机制下是经典不可计算的（引理 A.5）。这是通过显式地从常温吉布斯采样问题进行归约来建立的。
2. 学习理论层面的分离： 作者展示了一个在线学习实例（“解码游戏”），在该实例中，DQMW-Sample 实现了渐近亚线性的遗憾（$O(\sqrt{T} \log d)$），而每一个高效的经典学习者都承受着常数平均遗憾（$\Omega(1)$）。这种分离是计算性的，依赖于经典算法无法高效重建困难样本负载。
3. 多项式层级的自适应坍缩： 针对全自适应交互，该研究强化了其硬度结果。作者证明，如果存在一个能够高效模拟整个 $T$ 轮反馈过程的经典模拟器，将会导致多项式层级的坍缩（定理 A.19）。这解决了自适应性挑战：经典模拟器无法简单地引导轨迹远离困难窗口，因为联合转录分布（joint transcript distribution）必然包含困难样本。
4. 噪声鲁棒性定理： 定理（定理 A.9）表明，在平衡耗散调度以及噪声强度与耗散率可独立控制的假设下，噪声诱导的遗憾是亚线性的（$O(\delta \sqrt{T})$）。

实验与实践贡献

1. 硬件特性表征： 作者报告了在 IBM Heron r2 (ibm_kingston) 处理器（156 个量子比特）上的初步硬件特性表征。他们测量了在不同耗散强度下，通过工程化耗散（通过中途测量和条件重置实现）产生的有效误差成本。
2. Lindblad 模型仿真： 利用已发表的校准数据，他们进行了数值仿真，以验证噪声鲁棒性模型。这些仿真证实，如果噪声和耗散是可独立控制的，则稳态偏差底限随 $1/\gamma_0$ 降低。
3. 应用演示： DQMW-Sample 被应用于在线投资组合优化，使用了标普 500 指数的历史数据。与经典基准（UCRP, FTRL, CMW）相比，该算法在噪声损失反馈下表现出更具竞争力的或更优的遗憾，说明了耗散采样原语的实际效用。

4. 结果

• 理论分离： 本文建立了一个严格的条件分离：如果 BCL 困难性假设成立且满足实现性假设，则 DQMW-Sample 在特定实例上优于所有高效的经典学习者。
• 硬件可行性： 在 ibm_kingston 上的硬件实验得出了一个轮预算比率（round-budget ratio）约为 1.8（95% 置信区间 [1.4, 2.3]）。该比率比较了高耗散强度与低耗散强度下的可用时长。显著大于 1 的比率表明，增加耗散强度并不会按比例增加噪声（支持了“平衡调度”机制），尽管作者指出这些统计数据仍处于初步阶段（3 个量子比特，1024 次采样）。
• 噪声缩放： 理论分析表明，在当前的硬件上，由于中途测量（MCM）误差占主导地位，可用的轮预算 $T^*$ 被限制在约 $10^2$ 轮左右（相比之下，假设在门控受限的实现中为 $10^4$ 轮）。
• 应用性能： 在投资组合优化中，基于采样的更新与基于期望值的经典更新相比，对损失向量的扰动表现出更强的鲁棒性。

5. 意义与声明

本文将 DQMW-Sample 定位为通往在线学习中实现计算优势的一条具体路径，其基础是复杂度理论，而非仅仅是查询复杂度或相干性假设。

• 对优势的适度声明： 作者明确指出，在损失向量可以被精确且高效评估的任务上，并不预期能超越经典方法。优势专门产生于损失反馈源自一个经典采样困难的分布时。
• 实现性假设： 作者透明地阐述了其中的“承重”假设。具体而言，他们依赖于假设 E.2，即特定的工程化耗散器（通过 MCM + 重置实现）能够足够好地近似 Davies 生成器，从而保留 BCL 分布的硬度。他们指出，虽然 Davies 生成器的存在是严谨的，但在硬件上的物理近似是一个建模假设，仍需进一步验证。
• 噪声独立性： 噪声鲁棒性保证关键取决于假设 (R2)：即噪声强度 $\delta$ 和耗散热率 $\gamma_0$ 是可以独立控制的。作者承认，在近期待用硬件上，实现耗散的操作（MCM）本身就是一个噪声源，这使得该假设并非显而易见。其硬件实验旨在测试这种特定的耦合关系。
• 未来工作： 本文并未声称已经实现了确定性的量子优势。相反，它提供了一个理论框架和一个协议，用于进行明确的真实设备验证（附录 D），并呼吁进行跨多个量子比特和设备的更高统计量实验，以确认噪声-耗散耦合机制。

总之，这项工作架起了吉布斯采样理论难度与实际在线学习之间的桥梁，提供了一个物理上可实现的、其潜在优势严格受限于复杂度理论障碍的程序，同时对当前超导硬件上的可行性进行了谨慎且基于数据的评估。