🔬 应用物理

Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs

本文介绍了约束增强型量子近似优化算法（CE-QAOA），这是一种浅层、无辅助比特的混合求解器，它利用编码幺正设计和专门的 Block-XY 混合器，在受约束优化问题中实现了经验性的量子优势，包括多项式采样复杂度降低和指数级极小极大值分离，同时成功为小型旅行商问题实例找到了全局最优解。

原作者： Chinonso Onah, Roman Firt, Kristel Michielsen

发布于 2026-10-16

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Chinonso Onah, Roman Firt, Kristel Michielsen

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

在现代计算的广阔版图中，一个持久的挑战在于解决复杂的谜题，其中可能答案的数量增长得如此之快，以至于即使是最强大的超级计算机也无法检查每一个选项。这些被称为组合优化问题，这类问题支撑着从规划数千辆卡车的送货路线到设计高效药物分子的一切事物。几十年来，科学家们一直向量子计算机寻求突破迷宫的方法，希望量子物理学的奇异规律能让机器同时探索许多可能性。然而，目前的量子设备仍然规模较小且存在噪声，往往在误差淹没信号之前难以找到最佳答案。一个主要的障碍是，许多量子算法在探索不可能的解——即违反问题基本规则的答案——上浪费了时间，而不是将精力集中在有效的解上。

一组研究人员现在推出了一种旨在更高效地导航这些约束的新方法，为量子机器实现实际优势提供了一条更清晰的路径。他们的工作专注于一种特定类型的题目，即解必须遵循严格的模式，例如在不重复的情况下恰好访问每座城市一次。研究人员并没有让量子计算机在所有可能的组合中自由游荡，而是构建了一个专门的框架，迫使机器从一开始就保持在有效答案的范畴内。通过将问题编码成一种每个部分都代表单一选择的结构，他们创建了一个“感知约束”的算法，在受限空间内生成候选解。这种方法在模拟量子电路上的测试表明，该机器寻找旅行商的最优路径时，所需的尝试次数显著少于传统方法。这表明，这为使近期的量子计算机真正适用于现实世界的物流领域提供了一种途径。

这项新方法的核心——作者称之为“约束增强型量子近似优化算法”（Constraint-Enhanced Quantum Approximate Optimization Algorithm）——依赖于一种在搜索开始前设置量子计算机的巧妙方式。想象一个拼图，你必须排列一组物品，使得每个槽位恰好持有一个物品，且没有物品被重复使用。标准方法通常允许计算机尝试一些槽位为空或持有两个物品的排列，从而在纠正这些错误上浪费时间。然而，新技术将系统初始化在一个每个槽位都保证恰好有一个物品的状态，有效地将计算机锁定在正确解的“形状”中。这是通过一种特定的量子态制备实现的，它起到了精确过滤器的作用，确保机器只考虑有效的配置。一旦系统处于这种状态，算法就会使用一种专门的混合过程来重新排列物品，在探索不同有效排列的同时，绝不破坏规则。

研究人员发现，这种结构化方法不仅仅是节省了时间；它改变了搜索的基本行为。在许多量子算法中，找到正确答案的机会非常微小，以至于机器需要运行数百万次才有机会成功。通过将搜索限制在有效解中，并利用问题的对称性来引导过程，新方法创造了一种情况，使得正确答案变得更有可能出现。在涵盖最多十个位置的模拟中，该算法在每一种情况下都成功生成了最佳路径。值得注意的是，它在尝试次数随问题规模增加时增长缓慢，而不是像其他方法那样呈指数级爆炸式增长。这表明该算法不仅是一个理论上的奇想，而且是未来硬件的一种可行策略。

这一成功背后的关键洞察在于算法处理问题结构与量子搜索之间关系的方式。研究人员展示了，通过尊重问题的自然对称性——例如，城市的顺序很重要，但具体的标签并不重要——他们可以创建一个数学保证，即正确答案始终触手可及。他们证明了，如果以正确的设置运行算法，总会存在一种特定的量子态排列，能够导向最优解。此外，他们还证明了该算法产生了“重输出”（heavy outputs），这意味着正确答案出现的频率远高于随机猜测的预期。这种概率的集中正是允许系统即使在有限尝试次数下也能快速找到解决方案的原因。

为了将这些理论优势转化为实用的工具，团队将他们的量子电路与一个充当最终裁判的经典计算机程序相结合。量子部分生成候选解列表，而经典部分则检查每个解是否有效并计算其成本。由于量子部分在产生有效候选解方面表现出色，经典检查器只需评估极少数选项即可找到最优解。这种混合方法（作者称之为“多项式时间混合量子-经典求解器”）确保了整个过程保持高效。模拟显示，对于从四个到十个城市的问题，该系统可以使用可控且随问题规模合理扩展的尝试预算来恢复全局最优解。

该研究还强调了这种新方法与经典计算机在仅限于观察底层结构而非原始数据时的能力之间存在显著差距。当经典计算机被迫从所有可能的比特模式中进行盲目猜测时，寻找有效解所需的尝试次数增长极快，以至于在处理大型问题时变得不切实际。相比之下，新的量子方法通过理解问题的结构，完全避免了这种爆炸式增长。研究人员发现，对于某些类型的问题，量子方法的效率可能比缺乏这种结构洞察力的经典方法高出指数级。这种差异不仅是速度问题，更是可行性的问题，这表明对于特定类别的优化问题，量子计算机可以解决目前经典机器无法完成的任务。

虽然结果令人鼓舞，但研究人员谨慎地指出，他们的发现来自于在理想化、无噪声量子电路上的模拟。在现实世界中，量子计算机受到误差和噪声的影响，这些因素可能会破坏这些微妙的过程。然而，该算法即使在浅层深度和简单结构下也能在模拟中表现出色，这为未来的实验提供了坚实的基础。其设计足够稳健，不需要复杂的纠错即可运行，使其成为目前可用量子设备测试的首选方案。研究人员认为，随着硬件的改进，他们所识别出的优势将只会更加显著，从而可能解锁解决复杂物流和规划问题的新能力。

最终，这项工作代表了科学家在如何使用量子计算机进行优化方面的思维转变。与其试图强迫一个通用算法去处理特定问题，不如将量子机制量身定制于问题本身的独特形状。通过将约束直接构建在量子态的制备和操纵方式中，研究人员创建了一个既高效又可靠的系统。结果表明，量子优势的路径可能不在于构建更大、更强大的机器，而在于设计更聪明的算法，使其与我们面临的问题的自然结构相契合。随着该领域的推进，这种“感知约束”的策略为量子计算机如何开始兑现解决世界上最难优化挑战的承诺，提供了一个具体的蓝图。

技术摘要：通过编码酉设计实现受限优化中的经验量子优势

问题陈述
组合优化问题（COPs），如旅行商问题（TSP）、二次指派问题（QAP）和车辆路径问题（CVRP），是物流和人工智能领域的基础，但计算挑战巨大。诸如分支定界法之类的经典方法在利用问题结构方面表现出色，而近期的量子方法（特别是量子近似优化算法，QAOA）通常会探索整个希尔伯特空间。这种探索会导致高昂的测量成本、电路深度以及对贫瘠高原（barren plateaus）的敏感性。现有的保持约束的变体（QAOA+）虽然缓解了部分问题，但往往依赖于带有辅助比特开销的算子，或者缺乏对典型情况行为和采样复杂度（shot complexity）的严格保证。

方法论：CE-QAOA 与 PHQC
作者引入了约束增强型量子近似优化算法（CE-QAOA），这是一种浅层的、具备约束感知能力的拟设（ansatz），旨在原生运行于“单热积空间”（one-hot product space, $H_{OH}$ ）。该方法建立在一个问题-算法协同设计框架（即“CE-QAOA 内核”）之上，该框架利用了组合优化问题中特定的对称性。

编码流形与初始态：
- 算法将 $m$ 个各包含 $n$ 个量子比特的块进行编码，每个块被限制在单激发子空间（单热编码）内。对于具有 $n$ 个位置的 TSP，这对应于 $n$ 个大小为 $n$ 的块，将状态空间限制在 $n^n$ 个基向量内（它是 $2^{n^2}$ 个环境空间的子集）。
- 初始态： 系统初始化为 $W_n$ 态的乘积（每个块内单激发的均匀叠加态）。
- 编码器： 一个无辅助比特、深度最优的电路，通过每个块内恰好 $n-1$ 次保持激发的两量子比特旋转来准备 $W_n$ 态。
电路原语：
- 混合器（Mixer）： 使用了一个两局部、块级 XY 混合器（ $H_M$ ）。它保持单热流形，并在单激发扇区内被归一化，具有恒定的谱隙。在编码后的拟量子比特（qudit）图像中，该混合器的作用类似于完全图（ $K_n$ ）的邻接矩阵。
- 可控性： 块级 XY 混合器结合对角相位项确保了每个块内的李代数可控性（ $\mathfrak{su}(n)$ ），这意味着其具有近似通用性。
- 代价哈密顿量： 问题哈密顿量（ $H_C = H_{pen} + H_{obj}$ ）在计算基下是对角的。惩罚项 $H_{pen}$ 被设计为在块置换和符号重标记下保持不变。
理论分析（酉设计）：
- 1-设计： 作者证明，通过应用块置换轮转（随机置换块内的标签），可以在编码空间上产生精确的酉 1-设计。这确立了一个基准，即与任何目标基向量的平均重叠度为 $1/D$ （其中 $D = n^m$ 是编码维度）。
- 2-设计： 通过结合每块的 XY 演化与对角纠缠层（由全局约束生成），该电路在浅层深度下实现了 $\epsilon$ -近似酉 2-设计。这为二阶矩提供了界限，确保了反集中性（anticoncentration）和典型情况下的重叠统计特性。
- Paley-Zygmund 论证： 这些设计属性被用于推导有限采样次数的反集中性保证，确保采样到能量高于某一阈值的解的概率是显著的。
算法求解器 (PHQC)：
- 作者提出了多项式时间混合量子-经典求解器（PHQC）。该求解器将常数深度的量子采样（在粗略的参数网格上进行）与确定性的经典可行性检查器封装在一起。
- 经典检查器评估所有采样出的比特串的精确目标值，并返回找到的最佳可行解，无论其经验频率如何。这使得算法即使在仅采样到一次最优解时也能成功。

关键结果
论文展示了针对来自 QOPTLib 基准库、位置数 $n \in \{4, \dots, 10\}$ 的 TSP 实例的无噪声电路模拟。

最优恢复： 使用单层（ $p=1$ ）和粗略参数网格，PHQC 成功找回了所有测试实例的全局最优解。
采样复杂度： 所需的采样预算随问题规模呈多项式缩放（ $S = O(n^k)$ ，其中 $k \in \{3, 4, 5\}$ ），与隐含的全希尔伯特空间维度的指数缩放相比，这是一个显著的降低。
重输出（Heavy Outputs）： 在没有置换轮转的情况下，模拟显示了“重输出”现象——即在某些实例中，由于相长干涉，采样到最优解的概率显著高于 $1/D$ 的设计基准。
经典竞争力：
- 模型 A（结构化定义域）： 如果经典采样器也能高效地生成编码的单热空间，则量子优势仅限于 $\Theta(D/S)$ 的因子，这与经典基准相匹配。
- 模型 B（原始比特串）： 如果竞争对手被限制在采样原始比特串（长度 $N=n^2$ ）并检查可行性，则预期试验次数随 $\Theta(2^{n^2}/S)$ 缩放。相比之下，CE-QAOA 在编码空间（ $D=n^n$ ）中运行，产生了 $\exp(\Theta(n^2))$ 的极小极大分离（minimax separation）。
- 参数依赖优势： 当 CE-QAOA 固定 $r \ge 1$ 个位置（例如固定起始城市）时，作者报告称，与从可行集中均匀采样的经典采样器相比，采样复杂度减少了 $\Theta(n^r)$ 。论文指出这是基于模拟的经验观察，并认为锁定块减少了有效搜索空间的机制，但明确表示这一现象的严格证明留待未来工作。

意义与主张
本文声称提供了一个通过在量子和经典层面同时利用问题结构来实现经验量子优势的框架。

理论保证： 该工作确立了浅层 CE-QAOA 电路可以在编码子空间内实现酉 1-设计和 2-设计，从而在不需要深层电路的情况下，为表达能力和典型情况行为提供严谨的界限。
资源效率： 无辅助比特、深度最优的编码器以及保持约束的混合器，通过消除冗余的惩罚项，降低了电路深度和门计数。
混合求解器效率： PHQC 协议证明，结合浅层量子采样与确定性经典后处理可以实现多项式采样复杂度，避免了与全编码维度相关的指数缩放。
量子-经典分离： 作者认为，尽管量子优势可能取决于具体的经典访问模型（特别是经典采样器无法高效生成编码流形，或特定构造性干涉的存在），但这些结果代表了向具有可分析典型情况行为的、受对称性启发的浅层量子启发式算法迈出的一步。

作者对最坏情况下的保证保持谨慎，指出酉设计界限是保守的，且观察到的多项式采样复杂度依赖于依赖于实例的构造性干涉（“重输出”），他们认为这源于在参数优化过程中只有一小部分块保持未对齐的状态。他们假设未来的工作应致力于证明独立于编码维度 $D$ 的最坏情况采样复杂度。

技术摘要：通过编码酉设计实现受限优化中的经验量子优势

类似论文