Generative Quantum Search for Combinatorial Optimization: Learning Shallow Quantum Samplers for Classically Refined Solution Subspaces

技术摘要：用于组合优化的生成式量子搜索

问题陈述
本研究调查了浅层量子采样器是否可以通过在“经典恢复盆地”（classical recovery basin）内放置更高的概率质量，从而在组合优化任务中超越经典采样器。该研究将最初为量子化学开发的 GQE+QSCI（生成式量子特征值求解器 + 量子选择构型相互作用）架构，适配到了图优化领域（具体为最大加权独立集，MWXIS）。其核心假设是：量子采样器生成的候选解分布，在经过经典修复与扩展算法的精炼后，其成功率能够高于经典采样器。

方法论
作者提出了 GQO+QSS（生成式量子优化 + 量子选择搜索） 框架，该框架遵循四个阶段的流水线：

1. 生成策略： 一个机器学习模型（图条件策略）生成量子线路程序（例如 QAOA 参数）。
2. 量子采样： 在模拟器或 QPU（Piast-Q）上执行这些线路，以产生位串（候选解）。
3. 经典恢复： 一个特定于问题的修复函数用于修复不可行解，随后进行局部扩展（例如 $r$-flip 邻域），以创建一个受限的搜索子空间。
4. 受限求解器： 在该受限子空间内寻找最优解的精确经典求解器。

关键理论公式化
论文通过 恢复盆地质量 ($p_r$) 将“量子优势”问题形式化：
$$p_r(q_\theta, G) = \Pr_{x \sim q_\theta} [x \in A_r(G)]$$
其中 $A_r(G)$ 是指在经过修复和 $r$-flip 扩展后，包含全局最优解的状态集合。在 $B$ 次抽样下的成功概率为 $P_{success} = 1 - (1 - p_r)^B$。研究指出，关键指标不是采样子空间相对于总空间的大小 ($|S_Q|/2^n$)，而是采样器在可恢复盆地中所放置的概率质量 $p_r$。

实验方案

• 数据集： 150 个 MWIS 实例，其基准真相（ground truths）通过 CBC + 暴力验证进行认证。
• 基准测试： 对九种采样器进行了比较，包括均匀随机、贪婪算法、模拟退火（SA）、禁忌搜索（Tablu search）、多起点局部搜索、Metropolis、热启动 QAOA、预言机 QAOA（基于 50 个最优配置）以及匹配的学习型经典策略。
• 约束条件： 一个预先注册且固定的协议，每个采样器的预算固定为 200 次抽样（shots）。
• 硬件： 实验包括在 Piast-Q 俘获离子处理器（20 个量子比特）上的模拟与执行。

关键结果

1. 经典占优： 在所有测试的问题规模（$n=16$ 至 $n=28$）下，禁忌搜索和模拟退火（SA）的表现均显著优于所有量子及学习型经典采样器。禁忌搜索实现的恢复盆地质量 ($p_r$) 在 $n=16$ 时为 0.822，在 $n=18$ 时为 0.944，在 $n=20$ 时为 0.878，在 $n=24$ 时为 0.943，在 $n=28$ 时为 0.901。SA 的值在这些规模下处于 0.088 到 0.428 之间。
2. 量子表现不佳： 在公平的、预先注册的协议下，所有量子采样器（热启动 QAOA、预言机 QAOA 及生成式策略）在每个问题规模上都输给了 SA 和禁忌搜索。
3. “预言机”伪影： 此前显示 QAOA 优于 SA 的积极结果被确定为由于逐实例配置选择而产生的伪影（即一种“预言机”上界）。当使用随机配置（一种可部署的方法）进行评估时，预言机 QAOA 在 $n=28$ 时的 $p_r$ 仅为 0.014，远低于 SA 的 0.088。
4. 学习型经典等效性： 一个学习型经典策略（140K 参数）实现了与预言机 QAOA 相当的性能（$p_r$ 为 0.005–0.101 对比 0.014–0.113），这表明在此设定下，量子线路相对于匹配的经典模型并不具备结构性优势。
5. 硬件鲁棒性： 在 Piast-Q 上的实验显示，QPU 与模拟器样本之间的恢复一致性为 93.4%，证实了硬件的鲁棒性，但也揭示了在优化质量上不存在量子优势。
6. 恢复转换： 研究绘制了一个“恢复转换”过程，即经典恢复对于 $n \le 16$ 是足够的，但对于 $n \ge 20$ 且采用 2-flip 扩展的情况，恢复开始失效。然而，即使在这种转换阶段，强大的经典基准（SA、禁忌搜索）仍保持着优越性能。

意义与主张
本文本身是一项 证伪研究。其主要主张是：在严格的、预先注册的评估以及匹配的学习基准下，浅层 QAOA 衍生的提议分布在捕捉 MWIS 经典恢复盆地方面，并不优于匹配的学习型经典提议模型。

• 无量子优势： 作者明确声称，在测试的范畴内，GQO+QSS 架构不存在量子优势。
• 对先前主张的反驳： 该研究将早期的积极结果归因于“预言机效应”，即针对每个实例选择最优配置，而这并非一种可部署的方法。
• 指标修正： 论文认为“子空间比例” ($|S_Q|/2^n$) 在固定抽样预算下是一个同义反复的指标，而 恢复盆地质量 ($p_r$) 才是衡量该问题的科学准确量。
• 未来方向： 作者建议，若要使量子采样产生价值，它必须在经典恢复失效的范畴（$n \ge 55$）内，持续比强力经典基准（如 SA）在恢复盆地中放置更多的质量，而目前的浅层线路尚未达到这一挑战。

研究结论认为，虽然 GQO+QSS 架构是混合优化的有效框架，但在针对 MWIS 恢复盆地捕获的具体任务中，当前的浅层量子采样器并不具备相对于强力经典随机搜索方法的结构性优势。