⚛️ quantum physics

Quantum-echo Markov process for combinatorial optimization

本文介绍了一种用于组合优化的量子回声马尔可夫过程，该过程利用量子动力学来设计结构化转移核，并证明了将量子驱动的探索与贪婪开发相结合，能有效平衡汉明空间去局域化与能量空间局域化，从而提升优化性能。

原作者： Tatsuhiko Shirai

发布于 2026-10-01

📖 1 分钟阅读🧠 深度阅读

原作者： Tatsuhiko Shirai

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

解决复杂的谜题是我们在导航世界中的基本方式，从组织配送路线到安排医院的手术室。这些都是组合优化问题，其目标是在海量的可能性中找到唯一的最佳排列。几十年来，科学家们一直寻求量子力学的帮助，希望量子粒子的奇异行为能够比任何经典计算机更快地探索这些庞大的搜索空间。两种著名的路径，即量子退火和量子近似优化算法，利用受控的量子运动来引导系统趋向于解。然而，最近的研究表明，当这些量子工具在有限资源（即运行时间短或步数固定）的情况下使用时，它们往往会陷入困境。它们倾向于只观察附近的选项，从而错过了那些位于远处的更优解；或者它们的跳跃过于剧烈，导致解的代价发生过大的变化，从而变得毫无用处。

早稻田大学的一位研究人员提出了一种新的方法，旨在利用这些有限的量子资源，其目的不是直接寻找最终答案，而是作为搜索过程的一个高级引导器。他们开发了一种名为“量子回声马尔可夫过程”（quantum-echo Markov process）的方法。想象一位旅行者试图在一片广袤且多雾的山脉中寻找最低点。一个简单的步行者可能只检查脚下紧邻的地面，从而面临陷入小山谷的风险。一个鲁莽的跳跃者可能会横跨整个山脉，但他们落在高耸的山峰上的概率与落在低洼的山谷中的概率一样大。研究人员想要一种能够让旅行者远离当前位置，却又不会将其送往更高、更差海拔的方法。为了实现这一点，他们使用了一个特定的量子序列：向前推进时间，施加一个微小的局部扰动，然后向后推进时间。这种“回声”技术允许系统在保持整体代价变化微小且可控的同时，探索搜索空间中遥远的配置。

研究人员在两种不同类型的数学景观上测试了这种方法。第一种是随机伊辛模型（random Ising model），它模拟了一个复杂系统，其中各部分以特定方式相互作用，创造出起伏不定的地形。第二种是随机能量模型（random energy model），这是一个更加混沌的景观，其地形高度与位置无关，是对该方法在不存在自然结构的情况下寻找结构能力的严格测试。通过在最多包含十四个变量的系统中进行模拟，他们观察到，随着增加量子运动的持续时间或算法中的步数，该过程变得异常有效。它开始触及与起始点截然不同的配置，然而这些新配置的代价仍与原始配置接近。这是一种罕见的结合：具备了在不付出沉重代价的前提下走得很远的能力。

研究人员发现，这种成功源于两种截然不同的机制共同作用。能够到达远方位置的能力源于量子信息传播的方式，它有效地连接了搜索空间中遥远的各个部分。而能够保持代价接近的能力则源于量子过程在系统位置与其能量之间产生的微妙相关性。在随机伊辛模型中，这种相关性是系统演化足够缓慢以尊重其底层结构的自然结果。在更加混沌的随机能量模型中，这种相关性是通过仔细调整量子电路的参数而创建的。研究人员发现这种平衡是微妙的：如果过程过于专注于保持低代价，它就会失去探索能力，从而导致搜索停滞。

为了将这一量子引导投入实际应用，研究人员将其应用于一种迭代优化策略。他们让量子过程建议一个新的配置，但只有当该移动能改善或维持解的质量时，才会接受该移动。当他们在简单的磁链和复杂的随机伊辛模型上测试此方法时，他们发现量子回声法优于标准的随机搜索，尤其是在寻找高质量解时。然而，他们也注意到一个限制：如果量子过程变得过于严苛，它将无法逃离局部陷阱。为了解决这个问题，他们将量子回声步骤与一种被称为“贪婪下降”（greedy descent）的经典技术相结合。在量子过程建议了一个新位置后，经典计算机会立即执行一系列微小的下坡步骤，以从该新起点找到最佳的局部极小值。

这种混合方法被证明是最强大的。量子动力学提供了跳出局部山谷所需的探索能力，而贪婪下降则确保了系统一旦降落在新区域，就能利用每一次改进的机会。在模拟中，加入这个贪婪步骤显著提高了寻找最优解的成功率和速度，甚至在量子过程本身难以应对的情况下也是如此。研究结果表明，当经过正确设计时，有限的量子资源可以作为迭代优化的强大原语。与其试图通过一次量子跃迁解决整个问题，不如使用量子动力学来生成智能且有结构的移动，随后由经典计算机进行精细化处理。这项研究表明，这种在“远距离探索”与“保持近距离”之间的平衡，是解锁量子计算机解决现实世界优化问题潜力的关键，为利用当今有限的量子硬件来应对未来的最难谜题提供了一条充满前景的路径。

技术摘要：用于组合优化的量子回声马尔可夫过程

问题陈述
本文探讨了利用有限资源量子动力学（具体为量子退火 (QA) 和量子近似优化算法 (QAOA)）进行组合优化的挑战。尽管 QA 和 QAOA 具有前景，但近期的研究表明，在有限时间或固定深度机制下，它们表现出有效的局部性结构。具体而言，它们的动力学往往受限于底层图的有限邻域内，这阻碍了它们有效地跳出局部极小值；或者反之，如果探索过广，则会演变为本质上的随机采样。核心问题在于如何设计用于迭代搜索过程的转移核，使其在汉明空间（Hamming space）中是非局部的（以探索遥远的配置），但在能量空间（energy space）中是局部的（以避免产生巨大且有害的能量变化），从而在不使搜索随机化的前提下，实现对局部极小值的有效逃逸。

方法论
作者提出了一种**量子回声马尔可夫过程（Quantum-Echo Markov Process）**来构建此类转移核。该过程由一个酉算符 $\hat{U}$ （源自 QA 或 QAOA）和一组局部厄米酉算符 $\{\hat{V}_i\}$ （选定为单自旋翻转 $\hat{\sigma}^x_i$ ）定义。

量子回声动力学： 转移由序列 $\hat{U} \hat{V}_i \hat{U}^\dagger$ 生成。从计算基态 $|z\rangle$ 开始，系统通过 $\hat{U}^\dagger$ 进行前向演化，经历局部扰动 $\hat{V}_i$ ，然后通过 $\hat{U}$ 进行后向演化。
转移矩阵： 从配置 $z$ 到 $z'$ 的转移概率由在计算基下测量状态 $|\psi_i(z)\rangle = \hat{U} \hat{V}_i \hat{U}^\dagger |z\rangle$ 来确定。
局部性度量： 作者定义了两个指标来表征转移特性：
- 汉明空间局部性 ( $d_H$ )： 当前配置与候选配置之间的平均汉明距离。
- 能量空间局部性 ( $d_E$ )： 转移引起的平均平方能量变化 ( $\Delta C^2$ )。
模型： 该框架在随机伊辛模型（Random Ising Model）（其中能量与汉明结构相关）和随机能量模型（REM）（其中两者不相关）上进行了测试。
优化策略： 提出了两种迭代优化算法：
- 量子回声局部优化： 仅当 $\Delta C \leq 0$ 时接受候选配置。
- 带有贪婪下降的量子回声局部优化： 在量子回声转移后，执行贪婪的单自旋翻转下降，以到达局部极小值，然后再进行下一次迭代。

关键贡献与机制

工程化结构化转移： 本文证明了增加 QA 中的退火时间 $\tau$ 或 QAOA 中的层数 $p$ ，会同时增加汉明空间的非局部性（去局域化）。然而，能量空间的局部性行为因模型而异：在随机能量模型 (REM) 中，随着 $\tau$ 或 $p$ 的增加， $d_E$ 会减小（改善局部性）；而在随机伊星模型中， $d_E$ 几乎与 $p$ 或 $\tau$ 无关。值得注意的是，在 REM 中，这些转移在能量空间中可能比简单的单自旋翻转更具局部性，尽管它们在汉明空间中更具非局部性。
汉明去局域化机制： 这源于算符扩散（operator spreading）。随着 $\tau$ 或 $p$ 的增加，海森堡绘景中的低阶泡利串演化为涉及多个自旋的高阶串，使得转移能够连接汉明空间中遥远的配置。
能量局域化机制： 这源于有效哈密顿量 $\hat{U}^\dagger \hat{C} \hat{U}$ $\hat{U}^{†} \hat{C} \hat{U}$ 的本征态与代价函数 ( $C_z$ ) 与汉明权重 ( $w_z$ ) 之间动态生成的关联。
- 在 QA 中，这种关联源于在解析指数级微小能级间距之前的粗粒度拟绝热动力学。
- 在 QAOA 中，这种关联是通过电路参数的变分优化产生的，它增强了有效哈密顿量中的低阶项，从而在 $C_z$ 与 $w_z$ 之间建立了线性相关性。
贪婪下降的作用： 研究发现，虽然量子动力学提供了必要的探索（非局部性），但过度的能量空间局域化会通过抑制必要的转移而降低性能。引入贪婪下降步骤（利用/Exploitation）显著提升了性能，凸显了量子动力学用于探索（Exploration）与经典贪婪步骤用于利用（Exploitation）之间的互补作用。

结果

局部性调节： 在随机伊辛模型和 REM 上的数值模拟显示， $d_H$ 随 $\tau$ 或 $p$ 的增加而增加。对于 REM， $d_E$ 随 $\tau$ 或 $p$ 的增加而减小，且随机相位近似（random-phase approximation）能很好地重现精确结果。对于随机伊辛模型， $d_E$ 几乎与 $\tau$ 和 $p$ 无关，且在较小的 $\tau$ 和 $p$ 时，精确结果与随机相位近似之间存在偏差。
铁磁链： 在铁磁伊辛链中，达到目标最优性间隙所需的迭代次数随系统规模 $N$ 线性缩放。量子回声过程在较小的最优性间隙时优于随机单自旋翻转。研究表明，动力学漂移（dynamical drift）近似为热漂移与“局部缺陷比”的乘积，而该比例在电路深度增加时趋于 1。
随机伊辛模型：
- 无贪婪下降： 成功概率 ( $p_{suc}$ ) 随 $\tau$ 或 $p$ 的增加最初会上升，但由于转移矩阵变为块对角（绝热极限），在较大的 $\tau$ （针对 QA）下可能会下降，从而导致系统被困。这表明过度的能量空间局域性是有害的。
- 有贪婪下降： 成功概率即使在较小的 $\tau$ 或 $p$ 下也能迅速趋于 1。至关重要的是，对于 QA，即使在非贪婪版本失效的大 $\tau$ 情况下，其成功概率仍保持为 1。命中时间（hit time）随 $p$ 或 $\tau$ 的增加而减少。
可扩展性： 指标 $\xi$ （能量空间局部性的指示器）在随机伊辛模型中随系统规模的变化几乎保持不变，表明该机制在更大规模系统中依然存在。

意义与主张
本文确立了量子回声马尔可夫过程作为一个框架，用于构建具有可调局部属性的结构化转移核。作者主张，有限资源的量子多体动力学可以作为迭代优化中的计算原语，前提是将其用于在混合量子-经典循环中生成提议，而非作为独立的优化器。

作者谦虚地指出，虽然在随机伊辛模型上的结果表明了可扩展性，但在 REM 中的渐近可扩展性以及 QAOA 参数在大规模系统下的可训练性（潜在的贫瘠高原问题）仍是开放性问题。作者还提到，针对更难的问题寻找最优的退火时间/深度，以及研究更复杂的接受规则（例如允许向上移动）需要进一步的研究。这项工作提供了一条路径，不仅将有限时间的量子动力学用于寻找最终解，还用于通过结构化探索系统地改进近似优化。

技术摘要：用于组合优化的量子回声马尔可夫过程

类似论文