⚛️ quantum physics

Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization

该论文介绍了 SamBa-GQW，这是一种非变分量子算法，它利用离线经典采样协议来引导连续时间量子行走向组合优化问题的高质量解靠近，展示了在无需经典优化器的情况下，其性能可与 QAOA 等变分方法相媲美。

原作者： Ugo Nzongani, Dylan Laplace Mermoud, Giuseppe Di Molfetta, Andrea Simonetto

发布于 2026-10-02

📖 1 分钟阅读🧠 深度阅读

原作者： Ugo Nzongani, Dylan Laplace Mermoud, Giuseppe Di Molfetta, Andrea Simonetto

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

在计算领域，有些问题就像是在试图于沙滩中寻找一颗特定的沙粒，而这片沙滩每当你迈出一步时就会扩大一倍。这些被称为组合优化问题，计算机必须从海量的可能性中选择出最佳的排列方式，例如送货卡车最有效的路线，或是投资组合中最优的股票配置。随着选项数量的增长，传统计算机检查每一个选项所需的时间会迅速增加，以至于即使是最强大的超级计算机也需要比宇宙年龄还要长的时间才能找到答案。量子计算机利用物理学的奇特规则来处理信息，为我们提供了一个潜在的捷径。它们可以同时探索许多可能性，但目前的机器存在噪声且并不完美，通常需要复杂的调优才能正常工作。这促使研究人员寻找新的方法，在无需人类不断调整设置的情况下引导这些量子机器。

一个研究小组引入了一种名为 SamBa-GQW 的新方法，这是一种旨在解决这些难题的技术，它不依赖于经典计算机来微调量子过程。该方法并非采用一种需要经典计算机不断检查并纠正量子机器设置的试错法，而是使用了一种智能的一次性准备步骤。研究人员首先在常规计算机上对问题的景观进行一个规模较小、易于处理的采样。这个样本就像一张地图，揭示了解决方案空间的总体形状以及最佳答案可能隐藏的位置。利用这张地图，他们设定量子机器运行一段特定的旅程——一种概率的连续流动，这种流动会自然而然地向着最佳解漂移。随后，量子机器会遵循这条预先计算好的路径，并伴随着一种在接近最优解时逐渐减慢的变化节奏进行运行，从而有效地让系统的物理特性承担起主要的计算任务。

研究人员在各种具有挑战性的问题上测试了这种方法，包括寻找将网络拆分为两个组的最佳方式、选择互不冲突的最大项目组，以及优化投资组合。他们在涉及多达三十个变量的问题上模拟了这个过程，对于目前的量子技术而言，这是一个具有重要意义的规模。结果显示，该方法始终能找到高质量的解，通常能落在最佳答案或非常接近最佳答案的位置。在许多情况下，量子态会高度聚焦于正确的解，这意味着如果你测量计算机的输出，你会有很高的概率得到正确答案。团队发现，他们只需要采样总决策空间中极小的一部分，就足以构建出一张有效的地图，这证明了无需对问题的景观进行全面的穷举搜索即可引导量子行走者。

在与其他流行的量子方法（如量子近似优化算法，QAOA）进行比较时，这项新技术表现出了竞争力，尽管其权衡取向有所不同。标准的 QAOA 方法依赖于经典计算机反复调整量子机器的设置以寻求最佳性能，这一过程可能很慢，且容易陷入局部陷阱。相比之下，SamBa-GQW 方法不需要这种调优；它运行的是一个单一的、预先确定的序列。虽然标准方法在给予极深、极复杂的电路时通常能获得稍好的结果，但当允许电路深度足够增长时，新方法的表现也同样出色。这表明，对于未来的、更强大的量子计算机，这种非变分方法可能是一种高效解决复杂问题的方式，能够绕过目前限制许多量子算法的那些困难且耗时的优化循环。

该研究还探讨了这种方法在面对不同类型问题和不同难度等级时的表现。对于某些问题，例如最大化逻辑谜题中满足条件的数量，即使是复杂版本的题目，该方法也能以高概率找到最佳解。对于其他问题，如旅行商问题，量子机器完成旅程所需的时间取决于城市之间的具体距离，但该方法仍能成功引导系统找到最优路径。研究人员观察到，量子态会自然地向最佳答案聚集，从广泛的可能性分布收缩成围绕解的一个紧密簇。这种定域化在许多情况下发生得很快，表明该方法具有鲁棒性和可靠性。

最终，这项工作为下一代量子计算提供了一个充满前景的替代方案。通过用简单的离线采样协议取代对经典优化器的需求，研究人员为量子机器解决难题创造了一条精简的路径。该方法并不声称能瞬间解决这些问题或使用某种魔术，而是提供了一种实用的、有数学依据的方法，用于在庞大的组合优化搜索空间中进行导航。随着量子硬件的持续改进并超越当前的噪声时代，这种方法可能会成为应对那些目前令经典计算机无法承受的大规模物流和科学挑战的标准工具。研究结果表明，只要有正确的引导，量子系统可以高效地找到通往最佳解的路径，而无需人类在每一步都亲手操纵。

技术摘要：基于采样的引导量子行走 (SamBa–GQW)

问题陈述

本文旨在解决在量子计算机上解决任意阶二元组合优化问题的挑战。这些问题通常是 NP 难的，涉及寻找一个二元向量 $x^* \in \{0, 1\}^n$ ，以最小化代价函数 $C(x)$ （可能带有约束条件）。虽然量子计算机为探索指数级解空间提供了天然优势（仅需线性数量的量子比特资源），但目前的噪声中等规模量子（NISQ）设备在处理诸如量子近似优化算法（QAOA）等变分算法时仍面临困难。这些变分方法依赖于经典优化器来调整参数，而这一过程往往受到“贫瘠高原”（梯度消失）以及随着问题规模增大所需的量子电路评估次数呈指数级增长的困扰。

现有的非变分替代方案，如引导量子行走（GQW），试图通过使用源自问题哈密顿量谱的随时间变化的跳跃率来避免经典优化。然而，计算精确谱的成本是指数级的，且之前使用参数曲线（例如贝塞尔曲线）的近似方法仍然需要经典优化，导致迭代次数随规模呈指数级增长。

方法论：SamBa–GQW

作者提出了 SamBa–GQW（基于采样的引导量子行走），这是一种非变分量子算法，它消除了在量子执行阶段对经典优化器的需求。该算法分为两个不同的阶段运行：

1. 经典离线采样协议

该协议不再计算代价哈密顿量 $H_C$ 的精确谱（这需要 $2^n$ 次评估）或优化参数曲线，而是采用了一种高效的采样协议。

采样： 协议从 $2^n$ 个解空间中随机选择多项式数量的候选状态， $q = \text{poly}(n)$ （经验发现 $q=n^2$ 已足够）。
能隙估计： 对于每个采样的状态，算法计算该状态与其邻居（由混合器连通性定义，例如 X-mixer 的超立方体结构）之间的能量间隔。
谱近似： 算法计算特定能量层最大能量间隔的平均值。这提供了对函数 $\Gamma(E)$ 的近似，该函数描述了跳跃率与能量间隔的关系，正如之前的 GQW 文献中所推导的那样。
调度构建： 利用这些采样点，算法通过插值法构建一个连续、平滑且随时间变化的跳跃率 $\Gamma(t)$ 调度表。该调度旨在平衡混合哈密顿量 $H_M$ 和代价哈密顿量 $H_C$ ，从而实现振幅从高能态向低能态的最大化转移。

2. 量子在线执行

一旦确定了跳跃调度 $\Gamma(t)$ ，量子计算机便根据该调度执行连续时间量子行走（CTQW）。

哈密顿量： 系统在随时间变化的哈密顿量 $H(t) = \Gamma(t)H_M + H_C$ 下演化。
电路实现： 为了在基于门电路的量子计算机上运行，作者提出了一个两级离散化策略。首先将时间间隔划分为跳跃率呈线性插值的周期，随后进一步细分这些周期以应用 Trotter-Suzuki 分解。这产生了一个由代价算符（ $U_C$ ）和混合器算符（ $U_M$ ）幺正变换交替组成的量子电路，其结构类似于 QAOA，但参数是预先确定的而非优化的。
测量： 算法执行一组计算基下的测量。从测量结果中选取最优解。

核心贡献

非变分框架： SamBa–GQW 是一种“一发即中”（one-shot）算法，不需要经典优化器来调整量子参数，从而避免了贫瘠高原以及与变分循环相关的指数级扩展问题。
高效采样： 本文证明了多项式数量的样本（ $q \approx n^2$ ）足以近似最优跳跃率，从而避免了精确谱分析带来的指数级成本。
电路实现： 作者提供了一种将连续时间演化离散化为相对于量子比特数和采样数呈多项式深度的门电路的具体方法。
广泛适用性： 该算法在多种问题上进行了测试，包括：
- 二次问题： MaxCut、最大独立集（MIS）和投资组合优化（带约束）。
- 高阶问题： 低自相关二进制序列（LABS）、MAX-k-SAT 以及旅行商问题（TSP）的四次项改写形式。

结果

作者展示了针对高达 $n=30$ 个量子比特的问题规模的数值模拟（包括哈密顿量模拟和基于电路的模拟）。

性能： SamBa–GQW 能够稳定地找到高质量的近似解。对于许多实例，测量到最优解或处于前 5% 排名内的解的概率非常高。
与 GQW 的比较： 与使用贝塞尔曲线进行参数拟合的变分 GQW 相比，SamBa–GQW 达到了相当的近似比。至关重要的是，由于避免了迭代式的经典优化循环，SamBa–GQW 将执行时间缩短了至少一个数量级。
与 QAOA 的比较：
- 浅层电路（NISQ 阶段）： 当限制在浅层电路深度（例如 $p < 20$ ）时，QAOA 通常优于 SamBa–GQW，特别是在加权 MaxCut 和 MIS 问题上。这归功于 QAOA 能够利用经典优化来针对特定问题实例微调参数。
- 深层电路（超越 NISQ）： 当允许增加电路深度（达到 $p \approx 100$ 或更高）时，SamSamBa–GQW 在近似比方面与 QAOA “旗鼓相当”。论文指出，与 QAOA 的浅层饱和相比，SamBa–GQW 需要更深的电路才能达到其峰值性能，但它能在没有变分开销的情况下实现类似的最终质量。
可扩展性： 该算法随量子比特数的增加表现出合理的扩展性。对于 MaxCut 和 MIS 等问题，只要适当调整采样参数 $q$ 和电路深度，近似比即使在 $n$ 增加时也能保持在高水平。

意义与主张

本文将 SamBa–GQW 定位为解决超越 NISK 阶段组合优化问题的有力启发式算法。其主要意义在于提供了一种非变分替代方案，该方案对贫瘠高原具有鲁棒性，并且不会受到变分方法中经典优化迭代所导致的指数级扩展问题的困扰。

作者声称，虽然 SamBa–GQW 可能需要比 QAOA 更深的电路才能获得最优结果，但通过消除在经典优化循环中重复进行量子电路评估的需求，它在解质量与计算成本之间提供了有利的权衡。该算法并非被视为解决 NP 难问题的多项式时间解法，而是一种通过多项式资源（在采样和电路深度方面）即可有效地引导搜索向高质量状态进行的方法。这项工作表明，随着量子硬件的改进和更深层电路的可行性提高，SamBa–GQW 有望成为大规模组合优化的竞争性、可扩展的方法。